Answers.Body: <p>If you are running self-play in a two player zero sum game, then you can do the following:</p>
  
  <ul>
  <li><p>Arbitrarily decide the reward scheme for winning, drawing, losing is +1, 0, -1 for <strong>Player A</strong>.</p></li>
  <li><p>Have <strong>Player A</strong>'s goal to <em>maximise</em> reward, and <strong>Player B</strong>'s goal to <em>minimise</em> reward.</p></li>
  </ul>
  
  <p>This means you can combine both players' view of the values of positions and plays into a single metric, which can be learned and/or searched depending on your algorithm. When searching, you can use MCTS and/or minimax algorithms. When using Q-learning, the only tweak to apply is instead of picking the maximising action, player B will want to pick the minimising action (so will use the <code>min</code> and <code>argmin</code> functions where player A would use <code>max</code> and <code>argmax</code>) - remember when calculating TD error that you are evaluating a position for one player, but will be using reward + max/min of next player's move. </p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-23T01:40:43.857Z
Answers.Text: Smart approach with Q-learning! Do you know if the following would work? Once the game ends, find the last experiences for player one and player two and replace rewards with -1, 0, 1 depending on the outcome for each player?
Answers.UserDisplayName: mark mark
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-23T08:03:31.637Z
Answers.Text: @markmark: If your value function is written from the perspective of current player, then yes that is fine. It is probably simpler to think of the "win immediately" as a special case (i.e. usually the other player gets to move as part of state transition, but a winning move prevents that), rather than "backup the value on loss" as special (i.e. generally backup the resulting value from next player's turn for one-step algorithms, except on a win). However, it works logically either way around.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-26T08:45:11.503Z
Answers.Text: And how would training need any modifications for the player who takes argmin action? (Q-values are calculated using max q value from next state)
Answers.UserDisplayName: mark mark
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-11-26T08:51:33.020Z
Answers.Text: @markmark That is in the answer - you will need to take min or max depending on whose turn the value is being calculated for - if it is Player A's turn on timestep $t$ and they get reward $r_t$ and the state changes to $s_{t+1}$ you have to use Player B's view of the Q table when looking at the Q value from $t+1$. That includes Q value update rules. So the update for Player A who wants max Q value is actually $Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha(r_t + \text{min}_{a'} Q(s_{t+1}, a') - Q(s_t, a_t) )$ - taking the minimum because $t+1$ is on Player B's turn, and Player B wants min Q.
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-31T20:25:16.787Z
Answers.LastActivityDate: 2018-05-31T20:43:21.903Z
Answers.LastEditDate: 2018-05-31T20:43:21.903Z
Answers.UserDisplayName: Neil Slater
Answers.Body: <p>When one agent makes a move, that move should be perceived as part of the "state transition" executed "by the environment" from the perspective of the other agent.</p>
  
  <p>For example, suppose that, as a "neutral third party" we view the game as follows, as a sequence of states, actions and a terminal reward. I use <code>A</code> to denote actions selected by the first player, and <code>B</code> to denote actions selected by the second player:</p>
  
  <p><code>S1 -&gt; A1 -&gt; S2 -&gt; B1 -&gt; S3 -&gt; A2 -&gt; S4 -&gt; B2 -&gt; S5 -&gt; A3 -&gt; Terminal Reward</code></p>
  
  <p>Then, the first player should only get the following observations:</p>
  
  <p><code>S1 -&gt; A1 -&gt; S3 -&gt; A2 -&gt; S5 -&gt; A3 -&gt; Terminal Reward</code></p>
  
  <p>note how states <code>S2</code> and <code>S4</code> are skipped entirely, they are not really states from the perspective of the first player, they're just halfway through the transition caused by the first player's action and are not interesting for the first player.</p>
  
  <p>Similarly, the second player should only get the following observations:</p>
  
  <p><code>S2 -&gt; B1 -&gt; S4 -&gt; B2 -&gt; Terminal Reward</code></p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2018-05-30T12:32:41.640Z
Answers.LastActivityDate: 2018-05-30T12:32:41.640Z
Answers.UserDisplayName: Dennis Soemers
Body: <p>There seems to be a major difference in how the terminal reward is received/handled in self-play RL vs &quot;normal&quot; RL, which confuses me.</p>
  <p>I implemented TicTacToe the normal way, where a single agent plays against an environment that manages the state and also replies with a new move. In this scenario, the agent receives a final reward of <span class="math-container">$+1$</span>, <span class="math-container">$0$</span> and <span class="math-container">$-1$</span> for a win, draw, and loss, respectively.</p>
  <p>Next, I implemented TicTacToe in a self-play mode, where two agents perform moves one after the other, and the environment only manages the state and gives back the reward. In this scenario, an agent can only receive a final reward of <span class="math-container">$+1$</span> or <span class="math-container">$0$</span>, because, after his own move, he will never be in a terminal state in which he lost (only agent 2 could terminate the game in such a way). That means:</p>
  <ol>
  <li><p>In self-play, episodes end in such a way that only one of the players sees the terminal state and terminal reward.</p>
  </li>
  <li><p>Because of point one, an agent can not learn if he made a bad move that enabled his opponent to win the episode. Simply because he does not receive a negative reward.</p>
  </li>
  </ol>
  <p>This seems very weird to me. What am I doing wrong?  Or if I'm not wrong, how do I handle this problem?</p>
  
Tags: <reinforcement-learning><game-ai><self-play><tic-tac-toe>
Title: How can both agents know the terminal reward in self-play reinforcement learning?
UserDisplayName: user3877351
ThreadText: # How can both agents know the terminal reward in self-play reinforcement learning?
  
  (Asked by: username_0 on 2018-05-30)
  
  There seems to be a major difference in how the terminal reward is received/handled in self-play RL vs "normal" RL, which confuses me.
  
  I implemented TicTacToe the normal way, where a single agent plays against an environment that manages the state and also replies with a new move. In this scenario, the agent receives a final reward of $+1$, $0$ and $-1$ for a win, draw, and loss, respectively.
  
  Next, I implemented TicTacToe in a self-play mode, where two agents perform moves one after the other, and the environment only manages the state and gives back the reward. In this scenario, an agent can only receive a final reward of $+1$ or $0$, because, after his own move, he will never be in a terminal state in which he lost (only agent 2 could terminate the game in such a way). That means:
  
  1. In self-play, episodes end in such a way that only one of the players sees the terminal state and terminal reward.
  2. Because of point one, an agent can not learn if he made a bad move that enabled his opponent to win the episode. Simply because he does not receive a negative reward.
  
  This seems very weird to me. What am I doing wrong? Or if I'm not wrong, how do I handle this problem?
  
  **Tags:** reinforcement-learning, game-ai, self-play, tic-tac-toe
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2018-05-31. Score: 3
  
  If you are running self-play in a two player zero sum game, then you can do the following:
  
  * Arbitrarily decide the reward scheme for winning, drawing, losing is +1, 0, -1 for **Player A**.
  * Have **Player A**'s goal to *maximise* reward, and **Player B**'s goal to *minimise* reward.
  
  This means you can combine both players' view of the values of positions and plays into a single metric, which can be learned and/or searched depending on your algorithm. When searching, you can use MCTS and/or minimax algorithms. When using Q-learning, the only tweak to apply is instead of picking the maximising action, player B will want to pick the minimising action (so will use the `min` and `argmin` functions where player A would use `max` and `argmax`) - remember when calculating TD error that you are evaluating a position for one player, but will be using reward + max/min of next player's move.
  
  > **Comments:**
  > **username_2**: Smart approach with Q-learning! Do you know if the following would work? Once the game ends, find the last experiences for player one and player two and replace rewards with -1, 0, 1 depending on the outcome for each player?  
  > **username_1**: @markmark: If your value function is written from the perspective of current player, then yes that is fine. It is probably simpler to think of the "win immediately" as a special case (i.e. usually the other player gets to move as part of state transition, but a winning move prevents that), rather than "backup the value on loss" as special (i.e. generally backup the resulting value from next player's turn for one-step algorithms, except on a win). However, it works logically either way around.  
  > **username_2**: And how would training need any modifications for the player who takes argmin action? (Q-values are calculated using max q value from next state)  
  > **username_1**: @markmark That is in the answer - you will need to take min or max depending on whose turn the value is being calculated for - if it is Player A's turn on timestep $t$ and they get reward $r_t$ and the state changes to $s_{t+1}$ you have to use Player B's view of the Q table when looking at the Q value from $t+1$. That includes Q value update rules. So the update for Player A who wants max Q value is actually $Q(s_t, a_t) \leftarrow Q(s_t, a_t) + \alpha(r_t + \text{min}_{a'} Q(s_{t+1}, a') - Q(s_t, a_t) )$ - taking the minimum because $t+1$ is on Player B's turn, and Player B wants min Q.  
  
  ---
  
  ### Answer by username_3 on 2018-05-30. Score: 3
  
  When one agent makes a move, that move should be perceived as part of the "state transition" executed "by the environment" from the perspective of the other agent.
  
  For example, suppose that, as a "neutral third party" we view the game as follows, as a sequence of states, actions and a terminal reward. I use `A` to denote actions selected by the first player, and `B` to denote actions selected by the second player:
  
  `S1 -> A1 -> S2 -> B1 -> S3 -> A2 -> S4 -> B2 -> S5 -> A3 -> Terminal Reward`
  
  Then, the first player should only get the following observations:
  
  `S1 -> A1 -> S3 -> A2 -> S5 -> A3 -> Terminal Reward`
  
  note how states `S2` and `S4` are skipped entirely, they are not really states from the perspective of the first player, they're just halfway through the transition caused by the first player's action and are not interesting for the first player.
  
  Similarly, the second player should only get the following observations:
  
  `S2 -> B1 -> S4 -> B2 -> Terminal Reward`
  
  
  ---
  
  