From the book Reinforcement learning: an introduction, I have two questions:

1) there is the following sentence: "If the environment's dynamics are completely known, then finding the optimal policy for the state-value function is a system of |S| simultaneous linear equations in |S| unknowns"

where |S| is the number of different states.

Does environment's dynamic means the different states, actions, probabilities and rewards?

2) Also, I was wondering how it was possible to select an optimal policy in a stochastic policy. Indeed, in a deterministic policy, of course, we decide which action to take in each state. However, in a stochastic policy, it's all about probabilities, right? So, what choices do we have to do? Aren't we subject to probabilities without the possibility to do anything more?

Thanks !!

  • $\begingroup$ A question per post, ideally, especially if they are not very related. $\endgroup$ – nbro Jan 25 '19 at 12:36

Does environment's dynamic means the different states, actions, probabilities and rewards?

Yes, not just a list of them, but some model of how the states and rewards behave on each time step, dependent on the current state and action. Sutton & Barto 2nd edition captures this in the probability distribution function $p(s', r| s, a)$ - the probability of transitioning to state $s'$ and receiving reward $r$ when starting in state $s$ and taking action $a$.

If you know this function completely accurately, then you could in theory calculate optimal behaviour in terms of $|S|$ simultaneous equations based on the Bellman optimality equation.

Also, I was wondering how it was possible to select an optimal policy in a stochastic policy.

Stochastic policies are a generalisation of deterministic policies, and have a few different roles to play in RL, covered in the Sutton & Barto book.

In terms of solutions to environments, it is relatively common to want to find a deterministic solution, and for the optimal policy to be deterministic. However, you want to explore alternative behaviour in order to discover the optimal policy. There are two basic approaches to that:

  • On-policy learning has a single stochastic policy that is "close to" optimal, typically $\epsilon$-greedy, and switches between different $\epsilon$-greedy policies - there is a proof in Sutton & Barto that generalises the policy improvement theorem to this case and shows that it still works. If you are searching for a fully optimal deterministic policy, then over time you can reduce $\epsilon$. The SARSA algorithm is in this category.

  • Off-policy learning has two policies - a behaviour policy that is stochastic and allows for exploration, and a target policy which is what the agent learns. There is some maths/rules to convert results seen in the behaviour policy to the values expected by the target policy. Q-learning is in this category (and the "some maths" in the simplest case is just taking maximum predicted value of next step).

Sometimes the optimal policy is stochastic. For example in two-player games when trying to be unpredictable is a goal, such as scissor-paper-stone. Those cases are more complex, require learning a policy more directly, and are covered in much later chapters of the book.

  • $\begingroup$ Have you got an example of a situation in which there are at least two different stochastic policies? $\endgroup$ – nolw38 Jan 25 '19 at 12:54
  • $\begingroup$ @nolw38: That would be a new question. You also need to clarify what you mean by "different" and what the other constraints are implied by your question - e.g. what kind of scenario are you thinking about and trying to understand? There are multiple different stochastic policies used whilst SARSA is learning for instance, but only one - the current policy - is active at any time. I don't think you want to know about that? $\endgroup$ – Neil Slater Jan 25 '19 at 14:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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