Answers.Body: <blockquote>
  <blockquote>
  <p>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.</p>
  </blockquote>
  <p>As soon as I think about continuous state and action spaces with stochastic environment dynamics, computing the <span class="math-container">$\text{argmax}$</span> seems to be become very complicated and impractical.</p>
  </blockquote>
  <p>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 <span class="math-container">$|\mathcal{A}(s)|$</span> calls to <span class="math-container">$Q(s,*)$</span> you will need to make roughly <span class="math-container">$|\mathcal{S'}(s)| \times |\mathcal{A}(s)|$</span> calls to <span class="math-container">$V(s')$</span> where <span class="math-container">$\mathcal{S'}(s) \in \mathcal{S}$</span> are all possible states that might result from the starting state. In the worst case this is <span class="math-container">$|\mathcal{S}| \times |\mathcal{A}|$</span></p>
  <p>Despite the additional work here, you have been more efficient earlier. By only evaluating <span class="math-container">$V(s)$</span>, 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.</p>
  <p>For continuous states, this might still be practical, if both action choices and possible transitions are still discrete.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2019-02-15T13:25:20.850Z
Answers.LastActivityDate: 2019-02-15T13:31:32.073Z
Answers.LastEditDate: 2020-06-17T09:57:20.710Z
Answers.UserDisplayName: Neil Slater
Body: <p>In section "<em>5.2 Monte Carlo Estimation of Action Values</em>" of the second edition of the reinforcement learning book by Sutton and Barto, this is stated:</p>
  
  <blockquote>
    <p>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.</p>
  </blockquote>
  
  <p>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 <span class="math-container">$\pi(s) = \underset{a}{\text{argmax}}\ V(\text{step}(s, a))$</span> 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 <span class="math-container">$\text{argmax}$</span> 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 <span class="math-container">$\text{argmax}$</span> becomes easier (I'm especially thinking of the approach taken in deep Q learning). </p>
  
  <p>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?</p>
  
Tags: <reinforcement-learning><value-functions>
Title: Why is the state value function sufficient to determine the policy if a model is available?
UserDisplayName: yewang
ThreadText: # Why is the state value function sufficient to determine the policy if a model is available?
  
  (Asked by: username_0 on 2019-02-15)
  
  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?
  
  **Tags:** reinforcement-learning, value-functions
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2019-02-15. Score: 2
  
  > > 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.
  
  
  ---
  
  