n-armed bandit_Gittins index

本文主要是介绍n-armed bandit_Gittins index，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

The complexity of solving MAB (multi-armed bandit) using Markov decision theory increases exponentially with the number of bandit processes.
Instead of solving the n-dimensional MDP with the state-space $\prod_{i=1}^n \chi^i$, the optimal solution(Gittins Index) is obtained by solving n 1-dimensional optimization problems.
The index is given as,

$$\nu^i(x^i)=sup_{\tau>0}\frac {E[\sum_{t=0}^\tau \beta^tr^i(X_t^i)|X_0^i=x^i]}{E[\sum_{t=0}^\tau \beta^t|X_0^i=x^i]}$$

Off-Line Algorithm for computing Gittins Index

1. Largest-Remaining-Index Algorithm

Initialization: identify the state $\alpha_1$ with the highest Gittins index.
$S(\alpha_1)=\chi$,$\nu(\alpha_1)=r(\alpha_1)=r_{\alpha_1}$
choose: $\alpha_1=argmax_{\alpha\in\chi}\quad r_{\alpha}$
corresponding Gittins index is: $\nu(\alpha_1)=r_{\alpha_1}$
Recursion step:
Define the $m\times m$ matrix by $\forall a,b\in\chi$

$$Q_{a,b}^{(k)}= \begin{cases} P_{a,b}& \text{if b$\in C(\alpha_k)$}\\ 0& \text{otherwise} \end{cases}$$
and define the $m\times 1$ vectors:
d

这篇关于n-armed bandit_Gittins index的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---