Body: <p>I'm reading the Sutton &amp; Barto's book <code>&quot;Reinforcement Learning: An Introduction&quot; (2nd Edition)</code>. There is something I don't understand (p.63):</p>
  <blockquote>
  <p>Intuitively, the Bellman optimality equation expresses the fact that the value of a state under an optimal policy must equal the expected return for the best action from that state:
  <a href="https://i.sstatic.net/4P2t8.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/4P2t8.png" alt="enter image description here" /></a></p>
  </blockquote>
  <p>This suggests that in a given state, there is an optimal action that <em>is not</em> &quot;take a random action between 3 actions&quot;. However, this is the case in the <code>rock, paper, scissors</code> game where the Nash Equilibrium is obviously <code>play one of the three with equal probability</code> otherwise you are a target for exploitation.</p>
  <p>Why is the Bellman optimality equation not taking this into account by just replacing pi by pi* in the Bellman equation:
  <a href="https://i.sstatic.net/rspcV.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/rspcV.png" alt="enter image description here" /></a></p>
  <p>With this, I could say that the optimal policy is to play action <code>rock</code> with probability <code>1/3</code>, <code>scissors</code> with probability <code>1/3</code> and <code>paper</code> with probability <code>1/3</code>.</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-05T17:41:56.293Z
Comments.Text: You might be conflating Markov decision processes, where Bellman equation characterizes an optimal solution, and game theory, where different solution concepts (such as Nash equilibrium) are relevant.
Comments.UserDisplayName: mikkola
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-05T17:54:12.990Z
Comments.Text: Isn't reinforcement learning bound to converge to a nash equilibrium through self-play though?
Comments.UserDisplayName: FluidMechanics Potential Flows
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-05T18:05:29.190Z
Comments.Text: Perhaps, though I have to say I have a hard time understanding how the Bellman equations in your question relate to that. As I recall the Sutton & Barto book also heavily focuses on the MDP setting rather than game theory, so some clarifying edits to the question might be needed.
Comments.UserDisplayName: mikkola
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-05T20:07:28.623Z
Comments.Text: Oh in a MDP setting there is a set opponent who cannot try and exploit you, right? So no need to not be exploitable?
Comments.UserDisplayName: FluidMechanics Potential Flows
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-06T08:26:19.143Z
Comments.Text: Yes, MDPs are often referred to as "games against nature". The "opponent" is not actively choosing the worst outcomes for the agent, any uncertainty is packed into the next state-reward distribution $p(s',r|s,a)$ and the policy is optimized with that in mind.
Comments.UserDisplayName: mikkola
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-06T09:16:43.300Z
Comments.Text: I see. I confused both. Thanks! I’m currently at chapter 6 of Sutton and Barto but my goal is to learn to build agents that learn through self-play. Should I start reading other resources or are the basics of games against nature important to learn games against other opponents trying to exploit the main agent?
Comments.UserDisplayName: FluidMechanics Potential Flows
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2023-05-06T11:45:51.463Z
Comments.Text: In my subjective opinion, understanding the MDP can certainly make it easier to make the leap to game theory, but you can't get all the way there only studying the Sutton & Barto book. I think what you are aiming at eventually are partially observable stochastic games. MDPs are a special case, as shown in the [nice diagram here](http://rbr.cs.umass.edu/camato/decpomdp/overview.html).
Comments.UserDisplayName: mikkola
Tags: <reinforcement-learning><bellman-equations><game-theory>
Title: Bellman optimality equation does not allow random policies?
UserDisplayName: FluidMechanics Potential Flows
ThreadText: # Bellman optimality equation does not allow random policies?
  
  (Asked by: username_0 on 2023-05-05)
  
  I'm reading the Sutton & Barto's book `"Reinforcement Learning: An Introduction" (2nd Edition)`. There is something I don't understand (p.63):
  
  > Intuitively, the Bellman optimality equation expresses the fact that the value of a state under an optimal policy must equal the expected return for the best action from that state:
  > [![enter image description here](https://i.sstatic.net/4P2t8.png)](https://i.sstatic.net/4P2t8.png)
  
  This suggests that in a given state, there is an optimal action that *is not* "take a random action between 3 actions". However, this is the case in the `rock, paper, scissors` game where the Nash Equilibrium is obviously `play one of the three with equal probability` otherwise you are a target for exploitation.
  
  Why is the Bellman optimality equation not taking this into account by just replacing pi by pi\* in the Bellman equation:
  [![enter image description here](https://i.sstatic.net/rspcV.png)](https://i.sstatic.net/rspcV.png)
  
  With this, I could say that the optimal policy is to play action `rock` with probability `1/3`, `scissors` with probability `1/3` and `paper` with probability `1/3`.
  
  **Tags:** reinforcement-learning, bellman-equations, game-theory
  
  > **Comments:**
  > **username_1**: You might be conflating Markov decision processes, where Bellman equation characterizes an optimal solution, and game theory, where different solution concepts (such as Nash equilibrium) are relevant.  
  > **username_0**: Isn't reinforcement learning bound to converge to a nash equilibrium through self-play though?  
  > **username_1**: Perhaps, though I have to say I have a hard time understanding how the Bellman equations in your question relate to that. As I recall the Sutton & Barto book also heavily focuses on the MDP setting rather than game theory, so some clarifying edits to the question might be needed.  
  > **username_0**: Oh in a MDP setting there is a set opponent who cannot try and exploit you, right? So no need to not be exploitable?  
  > **username_1**: Yes, MDPs are often referred to as "games against nature". The "opponent" is not actively choosing the worst outcomes for the agent, any uncertainty is packed into the next state-reward distribution $p(s',r|s,a)$ and the policy is optimized with that in mind.  
  > **username_0**: I see. I confused both. Thanks! I’m currently at chapter 6 of Sutton and Barto but my goal is to learn to build agents that learn through self-play. Should I start reading other resources or are the basics of games against nature important to learn games against other opponents trying to exploit the main agent?  
  > **username_1**: In my subjective opinion, understanding the MDP can certainly make it easier to make the leap to game theory, but you can't get all the way there only studying the Sutton & Barto book. I think what you are aiming at eventually are partially observable stochastic games. MDPs are a special case, as shown in the [nice diagram here](http://rbr.cs.umass.edu/camato/decpomdp/overview.html).  
  
  ---
  
  ## 0 answers
  
  