2
$\begingroup$

In section "5.2 Monte Carlo Estimation of Action Values" of the second edition of the reinforcement learning book by Sutton and Barto, this is stated:

If a model is not available, then it is particularly useful to estimate action values (the values of state– action pairs) rather than state values. With a model, state values alone are sufficient to determine a policy; one simply looks ahead one step and chooses whichever action leads to the best combination of reward and next state, as we did in the chapter on DP.

However, I don't see how this is true in practice. I can see how it'd work trivially for discrete state and action spaces with deterministic environment dynamics, because we could compute $\pi(s) = \underset{a}{\text{argmax}}\ V(\text{step}(s, a))$ by just looking at all possible actions and choosing the best one. As soon as I think about continuous state and action spaces with stochastic environment dynamics, computing the $\text{argmax}$ seems to be become very complicated and impractical. For the particular case of continuous states and discrete actions, I think estimating an action value might be more practical to do even if a forward model of the environment dynamics is available, because the $\text{argmax}$ becomes easier (I'm especially thinking of the approach taken in deep Q learning).

Am I correct in thinking this way or is it true that if a model is available it's not useful to estimate action values if state values are already available?

$\endgroup$
1
$\begingroup$

With a model, state values alone are sufficient to determine a policy; one simply looks ahead one step and chooses whichever action leads to the best combination of reward and next state, as we did in the chapter on DP.

As soon as I think about continuous state and action spaces with stochastic environment dynamics, computing the $\text{argmax}$ seems to be become very complicated and impractical.

For stochastic dynamics the calculations would be more complex, but will often be quite tractable. It depends on size of the distribution, and ease of calculating probabilities to make the correct weighted sums. Instead of $|\mathcal{A}(s)|$ calls to $Q(s,*)$ you will need to make roughly $|\mathcal{S'}(s)| \times |\mathcal{A}(s)|$ calls to $V(s')$ where $\mathcal{S'}(s) \in \mathcal{S}$ are all possible states that might result from the starting state. In the worst case this is $|\mathcal{S}| \times |\mathcal{A}|$

Despite the additional work here, you have been more efficient earlier. By only evaluating $V(s)$, you have removed the action dimension, which otherwise splits up your estimates. Your value function estimates will, all else being equal, converge faster because of this. So this is sometimes a compromise you might be willing to make.

For continuous states, this might still be practical, if both action choices and possible transitions are still discrete.

Once either action space is continuous, or transitions are continuous over some probability density function, then finding the maximising action via the model becomes impractical.

$\endgroup$

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.