Sutton-Barto, page 102 (second edition).

How does the Belman optimality with altered transition probabilities in the second equation follow? The point which confuses me is the first part inside the summation in second equation where the action variable is $a$ (the one over which max is taken) but the variable in the second part in the summation is $a^\prime$ which is independent of the variable over which max is taken. This second part is understandable because the actions are random. But why is still the variable in the first part of the summation in the second equation $a$ which is the variable over which max is taken?

enter image description here


1 Answer 1


Your second equation is the BOE (Bellman optimality equation) of the altered transition probabilities for the new environment where any $\epsilon$-soft policy is moved inside as explained in the same page:

The new environment has the same action and state set as the original and behaves as follows. If in state $s$ and taking action $a$, then with probability $1-\epsilon$ the new environment behaves exactly like the old environment. With probability $\epsilon$ it repicks the action at random, with equal probabilities, and then behaves like the old environment with the new, random action... Let $\overset{\sim}{v}_*$ and $\overset{\sim}{q}_*$ denote the optimal value functions for the new environment. Then a policy $\pi$ is optimal among $\epsilon$-soft policies if and only if $v_\pi=\overset{\sim}{v}_*$

Therefore the max operator needs to range over the action $a$ in the first part of your second equation for learning the general (non-$\epsilon$-soft) optimal policy of the new environment. The uniformly repicked random actions $a'$ are summed out in the second part of your second equation, thus they're not really variables but placeholders.

  • $\begingroup$ but why is it "a" in the first part which is the same variable as the variable over which max is taken? $\endgroup$ Apr 16 at 20:19
  • 1
    $\begingroup$ As stated in my answer here the first part action $a$ is the real single non-dummy variable to be applied by max operator of BOE, it's the action of a general non-ϵ -soft/greedy optimal policy of the new environment, as in any generic model-based value iteration dynamic programming method. The possible confusing part is the transition probability $p$ here belongs to the old environment, you have to use the altered form to express the new environment's transition probability based on the said given $p$. $\endgroup$
    – cinch
    Apr 16 at 21:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .