Action-Value Methods

We denote the true (actual) value of action a as $q(a)$, and the estimated value on the $t$-th time step as $Q_t(a)$.

Action-Value methods

These approaches are repeatedly selecting an action and estimating their value.

value estimate

Sample average

We perform exploration and for every distinct action $a$, which was chosen $N_t(a)$ times. If individual rewards of the action $a$ are $R_i$, where $i\in \{1,\dots ,N_t(a)\}$, the average reward is estimated as

$$Q_t(a)=\frac{R_1+R_2+\cdots +R_{N_t(a)}}{N_t(a)}.$$

Due to the Law of large numbers, $Q_t(a)$ converges to $q(a)$.

To decrease memory requirement, we can only store $Q_k$ and $t$. The incremental average can be derived iteratively as

$$Q_{k+1}=Q_k+\frac{1}{k}\left[R_k-Q_k\right].$$

Weighted sample average

variant of this incremental sum, where recent actions have larger impact than the old ones, can have a constant step-size parameter $\alpha \in (0,1]$. This changes the formula to

$$Q_{k+1}=(1-\alpha {)}^k{Q}_1+\sum _{i=1}^k\alpha (1-\alpha {)}^{k-i}{R}_i.$$

• weight $\alpha (1-\alpha {)}^{k-i}$ decays exponentially for the constant, sometimes it is called exponential, recency-weighted average.
• it is suitable for non-stationary problems, where environment(the bandit) changes.

Step size ${\alpha }_k(a)=\frac{1}{k}$ results in basic sample average, which doesn’t decay and is more suitable for stationary bandits. Robbins-Monro theorem can be used to determine, whether the sequence with step-size ${\alpha }_k(a)$ converges to truth value $q(a)$ by satisfying following conditions

• ${\sum }_{k=1}^{\infty }{\alpha }_k(a)=\infty$
• ${\sum }_{k=1}^{\infty }{\alpha }_k^2(a)<\infty$

Non-convergance is not bad, it simply means that the the action value won’t stop changing. That is desirable for non-stationary problems.

action selecting

Greedy approach always selects the action with greatest value. Action selected at the step $t$ is given by

$$A_t=\underset{a}{\text{arg max }}{Q}_t(a).$$

This approach always exploits.

$\epsilon$-greedy approach has probability $\epsilon$ to explore, instead of exploit. As $N_t(a)\to \infty$, each action is sampled infinitely often, the convergence of $Q_t(a)$ is guaranteed if the sequence converges. Probability of selecting greedy action is at least $1-\epsilon$.