3
$\begingroup$

I'm reading the online draft of "reinforcement learning: an introduction". At section 2.8(Page 59), it introduces gradient bandit algorithm and defines the preference update rule as below (I rewrite it in a slightly different way, but the meaning should stay the same.)

$$H(A)=H(A) +\alpha(R_t-\bar R_t)(\mathbb {1}_{|A=a}-\pi(A))$$

where $a$ is the action just taken. What makes me very uncomfortable is the last term, $\mathbb 1_{|A=a}-\pi(A)$. I've read the inference at the end of the section and have some sense of how those $\mathbb 1_{|A=a}-\pi(A)$ is derived. Although that has explained a lot theoretically, I still want to get some intuitive explanations behind this.

Thanks in advance!

$\endgroup$

1 Answer 1

5
$\begingroup$

First, it's good to observe the "behaviour" of the quantity $(R_t - \bar{R}_t)$. Whenever our most recent reward $R_t$ is greater than the average reward $\bar{R}_t$ we've obtained so far ($R_t > \bar{R}_t$), this will be positive, and it will be negative otherwise.

Intuitively, whenever this quantity is possible, we'll want to encourage our most recent action a bit, and discourage all other actions a little bit. In other words, whenever $(R_t - \bar{R}_t)$ is positive, we want to increase $H(a)$ a bit, and decrease all $H(A)$ where $A \neq a$. The opposite holds whenever our most recent reward was lower than our average reward, e.g. when $(R_t - \bar{R}_t)$ is negative.

So, let's consider an update equation of the form \begin{equation} H(A) \gets H(A) + \alpha (R_t - \bar{R}_t) X. \end{equation} Now we want to figure out what $X$ should look like. We know, based on the intuition above, that it should be positive for $A = a$, and negative for $A \neq a$.

The most obvious solution would perhaps be to simply take $X = 1$ if $A = a$, and $X = -1$ if $A \neq a$. A "problem" with this would be that we encourage or discourage every action by exactly the same magnitude. This means that we actually learn very little. Imagine that we sort all actions according to our preferences $H(A)$:

\begin{equation} A_1, A_2, A_3, A_4, A_5, \dots \end{equation}

Suppose action $A_3$ was selected and is now encouraged by a magnitude of $\alpha (R_t - \bar{R}_t)$, and all other actions are discouraged by that same magnitude. We know that $A_3$ will move to the left a bit (higher priority), but that's also the only thing we learn; all other actions get discouraged by exactly the same magnitude, so they'll all shift to the right a bit, but all by exactly the same amount; their distances to each other in terms of preferences $H(A)$ do not change.

This observation leads to the question; do we want to discourage all non-selected actions by an equal amount? Or do we somehow want to shift them to the right by different magnitudes? Recall that our decision to discourage these actions is based on the observation that $(R_t - \bar{R}_t) > 0$. We want to encourage the action that leads to $R_t$, and discourage the actions that historically led to our historic average reward $\bar{R}_t$.

Consider the action $A_5$ all the way at the end of the sequence of sorted actions. It already has a very low preference $H(A_5)$, and therefore already has a low probability $\pi(A_5)$ of being selected. Should we really put a large amount of the "blame" for a lower empirical average reward $\bar{R}_t$, and discourage it even more? Probably not. It already has a low probability of being selected, so it probably didn't contribute much to the low average reward $\bar{R}_t$, so we probably don't have to "punish" it as much either. Actions such as $A_1$ and $A_2$, which currently have high probabilities of being selected, have probably contributed much more to our empirical average reward $\bar{R}_t$, so we should "punish" those actions much more for their contribution to that average reward which is lower than $R_t$.

This leads to the intuition that the magnitude of change, the extent to which we "reward" or "punish" actions, should depend on (for example, be proportional to) the extent to which they're "to blame" (or "deserve credit") for the rewards we've been observing. This intuition can be matched with $X = (1_{\vert A=a} - \pi(A))$.

Consider the case where we want to encourage $A = a$. If $H(A)$ (and therefore $\pi(A)$) is already very high (close to $1$), $A$ should not only get credit for our high new reward $R_t$, but it probably also contributed a lot, and should get "punished" for, the lower empirical average reward $\bar{R}_t$. So, we don't want to reward it too enthusiastically. If, on the other hand, $H(A)$ was very low, we want to "reward" it for two reasons: first because it led to a high new reward $R_t$, but also secondly because it should not get blamed for the empirical average reward $\bar{R}_t$. So, we encourage it by a higher magnitude.

Similar intuitive reasoning works for the case where $A \neq a$. $(1_{\vert A=a} - \pi(A))$ will be close to $0$ (low discencouragement/punishment) for actions that were already unlikely to be picked, and it will be close to $-1$ (high disencouragement/punishment) for actions that were very likely to be picked.

$\endgroup$
1
  • $\begingroup$ Thank you for such a thorough and intuitive explanation :) $\endgroup$
    – Maybe
    Apr 30, 2018 at 10:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.