3
$\begingroup$

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?

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
3
$\begingroup$

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

Improve this answer
$\endgroup$
0
3
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • $\begingroup$ 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? $\endgroup$
    – mark mark
    Nov 23, 2020 at 1:40
  • $\begingroup$ @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. $\endgroup$
    – Neil Slater
    Nov 23, 2020 at 8:03
  • $\begingroup$ 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) $\endgroup$
    – mark mark
    Nov 26, 2020 at 8:45
  • 1
    $\begingroup$ @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. $\endgroup$
    – Neil Slater
    Nov 26, 2020 at 8:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .