AdaptiveBandit, Methods, Multi-armed Bandit Problem

Multi-armed Bandit Problem

• The Multi-arm Bandit problem is a simplified reinforcement learning setting where one faces the exploration versus exploitation dilemma
• The problem is defined as a tuple $<\mathcal{A},\mathcal{R},\gamma >$, where
  • $\mathcal{A}$ is a set of $k$ actions $\mathcal{A}=\{a_1,a_2,\dots ,a_k\}$
  • and $\mathcal{R}$ is an unknown probability distribution ${\mathcal{R}}^a=\mathbb{P}[r|a]$ of rewards given the chosen action
• we choose $\gamma =0$ for totally discounted rewards
• at each time step $t$, the agent applies a policy ${\pi }_a=\mathbb{P}[a]$ to select an action $a_t\in \mathcal{A}$, based on previous actions taken and the respectively obtained rewards
• subsequently, the environment returns a reward $r_t\sim R^{a_t}$
• given that we set $\gamma =0$, we define the value of ac action $Q_{\pi }(a)$ as its instantaneous mean reward

$$Q_{\pi }(a)={\mathbb{E}}_{\pi }[r|a]Eq.3$$

• the goal is to find the optimal policy ${\pi }^{\ast }$ that maximized the cumulative rewards ${\sum }_{t=1}^T{r}_t$
• policies must take into account the exploration vs. exploitation dilemma and combine both explorative actions, to sample their associated unknown reward function to update their value estimates, and greedy actions, to increase the total cumulative reward by choosing the action with the highest value estimate
• the main advantage of describing adaptive sampling in terms of a multi-armed bandit is that we can benefit from the extensive literature on bandits to find solutions and replace heuristic policies with more mathematically sound ones