Asymptotically efficient adaptive allocation rules for the multiarmed bandit problem with switching cost (Q3835405)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 4112521
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | Asymptotically efficient adaptive allocation rules for the multiarmed bandit problem with switching cost |
scientific article; zbMATH DE number 4112521 |
Statements
Asymptotically efficient adaptive allocation rules for the multiarmed bandit problem with switching cost (English)
0 references
1988
0 references
multiarmed bandit problems
0 references
switching costs
0 references
resource allocation problems
0 references
asymptotic performance
0 references
0.9017823338508606
0 references
0.857903003692627
0 references
0.8579029440879822
0 references
0.8483725190162659
0 references
The paper considers multiarmed bandit problems with the additional feature of switching costs. The multiarmed bandit problem, which falls within the class of resource allocation problems, can in its simplest form be described as follows. There are \(p\geq 2\) statistical populations whose distributions are parametrized by an unknown \(\theta\). How should \(x_ 1,x_ 2,..\). sequentially be sampled from the p populations in order to maximize the expected value of \(J_ n=\sum^{n}_{i=1}x_ i\) as \(n\to \infty ?\) The information on which the choice of population \(\phi_ i=j\in \{1,...,p\}\), which will lead to the outcome \(x_ i\), is based on the previous choices of \(\phi_ k\), \(k=0,...,i-1\) and the corresponding outcomes \(x_ k\), \(k=0,...,i-1.\) Whenever \(\phi_ i\neq \phi_{i-1}\) there is a switching cost \(C>0\). The total switching cost is deducted from \(J_ n\). It is this difference which should be maximized, or, equivalently, the total regret, should be minimized. All these concepts are defined properly in the problem formulation section of the paper. Subsequently an allocation scheme is given which achieves the same asymptotic performance as the optimal solutions for the case without switching cost. This is made possible by grouping together samples into blocks of increasing sizes, thereby reducing the number of switches to \(\sigma\) (log n). The block lengths are prescribed in advance and are not generated adaptively from the data.
0 references