2
$\begingroup$

I'm reading the "Reinforcement learning: An introduction" by Sutton and Burto (http://incompleteideas.net/book/bookdraft2017nov5.pdf) The off-policy MC control algorithm puzzles me, please if anyone could help me to understand it better, I'd appreciate it.

tldr, my question: is the off-policy MC control (page 91) really off-policy? (my current understanding, it is not). Remaining post below - elaboration on that question.

Policy control commonly has two parts: 1) value estimation and 2) policy update. "off" in the "off-policy" means that we estimate values of one policy $\pi$ by Monte Carlo sampling another policy $b$. The book first introduces off-policy value estimation algorithm (p. 90). It totally makes to me (you can skip that screenshot below and just keep reading. The important thing that any arbitrary $\pi$ can be estimated by any arbitrary policy $b$)

enter image description here

then combined with the second step (policy update), the book introduces "policy control algorithm" (page 91).

enter image description here

This time however, there is a huge difference: $\pi$ is by design a deterministic policy. The line $b \leftarrow \text{any soft policy}$ in most cases will lead to the instantaneous exit from the loop. The algorithm will work effectively only when the loop is running, meaning that $A_t$ must equal to $\pi(S_t)$. It puts a lot of limitations on the $b$. It is not really any soft policy, but the policy, that produces the same actions (at least starting from some time $T$) as the policy $\pi$ with high probability. To me that violates the idea behind "off-policy" (that by definition allows to explore a variety of the policies).

From my current understanding, that algorithm could be turned to the true "off-policy" control if $\pi$ maintained to be non-deterministic. The concrete implementation in the book, however, puzzles me. It doesn't seem to be "off-policy" at all. Algorithm puzzles me in another way: it is simply super inefficient because the loop will not be running if we allow $b$ be any soft policy. Am I missing anything?

$\endgroup$

3 Answers 3

2
$\begingroup$

Can you allow $b$ to be any soft policy? Yes, it works from a theoretical stand-point, because a soft policy must have some probability of choosing each action, so there will always be some, maybe small, probability of matching the observed trajectory to a trajectory that the target policy would produce. Estimates can be made accurate in the long term using any soft policy as source data.

In practice, $b$ is often the $\epsilon$-greedy policy with respect to current Q, for the reasons you argue. Assuming $\epsilon$ is relatively low (maybe 0.1 or 0.01) that would mean that the loop typically does run for a range of useful trajectory lengths at the end of each episode. There is indeed a practical concern of choosing $b$ in some way close to $\pi$ for efficient learning.

This is also the case, for similar reasons, for all other off-policy algorithms. Some of them may appear to learn more from an inner loop when making exploratory actions, but they all learn most efficiently for some relatively low degree of exploration. Although many off-policy algorithms do process and update values from parts of trajectory that off-policy Monte Carlo Control does not, it is not always clear that the updates will be useful - for instance they might refine values in some part of the state space where an optimal agent would never find itself in practice. Or, perhaps more saliently when comparing with Monte Carlo Control, they might refine values in a biased way because there is no data available yet about what happens when acting under the target policy from a certain state.

$\endgroup$
2
$\begingroup$

I have encountered the same problem and it was bugging me too. At the end I've finished with the exploratory behavior policy being the same as the target policy but acting epsilon-greedy. It was still not converging though. In the 2nd edition of the book I don't remember some penalty for crash(all time steps were -1) but when introduced lower reward about that it did not help no matter the discounting factor or epsilon value. Here's how the visit map looks like(the numbers are the unsuccessful target policy which cycles in an infinite loop):

Race Track - Visits

It's cycling through all the actions without a chance to reach down the beginning of the episode to make some updates close to the starting states. Then I realized I can push that by changing the initial Q values which can be arbitrary and for me that was 0 for all. If I change them to -100(or -grid.size) then it can properly learn the last actions leading to a finish state and is chaining more meaningful updates:

Racetrack: initial Q values -100

These are the policies it found for the two pictures from the book after training for 50,000 episodes: enter image description here

$\endgroup$
1
$\begingroup$

Yes, your observation is right. Even though it is quite slow in training (exponentially slow), it is still an offpolicy algorithm. There is at least 1 update step at the tail of the episode that happens even if the sampled trajectory does not match the deterministic target policy's trajectory. This ensures that all the last Q(s,a) that are possible in our model are sampled and averaged quite often. It inevitably leads to update of our deterministic policy such that the last step taken by its (deterministic) trajectory is optimal. Similarly the second last step can be optimised provided the last step sampled using our behaviour policy is optimal and so on and so forth... So it gets exponentially more difficult to get the optimal action as we move up the trajectory. However, we do find a deterministic optimal policy in the limit.

$\endgroup$

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.