k-armed bandit

The simplest reinforcement learning setting: $k$ actions (“arms”), each giving stochastic reward from its own fixed distribution.

There are no states or consequences beyond the immediate reward.
It isolates the exploration vs exploitation problem: estimate each action’s value from the rewards received, and balance exploiting the best-looking arm against gathering information about the others.

$Q_n$ … estimate of an action’s value after it was selected $n-1$ times (the average of those rewards)
$R_i$ … reward received after the $i$th selection of this action

$$Q_n\doteq \frac{R_1+R_2+\cdots +R_{n-1}}{n-1}$$

computed incrementally as an error-driven update with step size $\frac{1}{n}$:

$$Q_{n+1}=Q_n+\frac{1}{n}\left[R_n-Q_n\right]$$

Simple epsilon greedy bandit algorithm

Initialize, for $a=1$ to $k$:
$Q(a)\leftarrow 0$
$N(a)\leftarrow 0$
Loop forever:

$$\begin{array}{rl}& A\leftarrow \{\begin{array}{ll}\arg {\max }_{a}Q(a)& \text{with probability }1-ϵ\text{ (breaking ties randomly)}\\ \text{a random action}& \text{with probability }ϵ\end{array}\\ & R\leftarrow \text{bandit}(A)\\ & N(A)\leftarrow N(A)+1\\ & Q(A)\leftarrow Q(A)+\frac{1}{N(A)}[R-Q(A)]\end{array}$$

Optimistic initial values

Set the initial value estimates high for all actions: even a purely greedy agent then explores every arm at first, since each real reward disappoints relative to the estimate and untried arms keep looking best. Works well on stationary problems. But as soon as the optimal actions change a little, you’re out of luck, like with all tricks that focus on initial values:

The beginning of time occurs only once, and thus we should not focus on it too much