<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>

CC BY-SA 4.0
2023-05-05T17:41:56.293Z
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.
mikkola
CC BY-SA 4.0
2023-05-05T17:54:12.990Z
Isn't reinforcement learning bound to converge to a nash equilibrium through self-play though?
FluidMechanics Potential Flows
CC BY-SA 4.0
2023-05-05T18:05:29.190Z
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.
mikkola
CC BY-SA 4.0
2023-05-05T20:07:28.623Z
Oh in a MDP setting there is a set opponent who cannot try and exploit you, right? So no need to not be exploitable?
FluidMechanics Potential Flows
CC BY-SA 4.0
2023-05-06T08:26:19.143Z
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.
mikkola
CC BY-SA 4.0
2023-05-06T09:16:43.300Z
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?
FluidMechanics Potential Flows
CC BY-SA 4.0
2023-05-06T11:45:51.463Z
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).
mikkola
<reinforcement-learning><bellman-equations><game-theory>
Bellman optimality equation does not allow random policies?
FluidMechanics Potential Flows
# 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

