3
$\begingroup$

This corresponds to Exercise 1.1 of Sutton & Barto's book (2nd edition), and a discussion followed from this answer.

Consider the following two reward functions

  • Win = +1, Draw = 0, Loss = -1
  • Win = +1, Draw or Loss = 0

Can we say something about the optimal Q-values?

$\endgroup$
1
  • 1
    $\begingroup$ If you are working through the book in detail, it is possible to compile your work and send to the author. Then you should receive a few weeks later some detailed and correct answers for chapters that you have completed. $\endgroup$ Commented Jan 21, 2019 at 19:24

1 Answer 1

1
$\begingroup$

Chapter 1 of Sutton & Barto, doesn't introduce the full version Q learning, and you are probably not expected to explain the full distribution of values at that stage.

Probably what you are expected to notice is that the maximum Q values out of possible next states - after training/convergence - should represent the agent's best choice of move. What the actual optimal values are depends on how the opponent plays. In self-play it is possible to find optimal play for both players in the game, and thus the Q values represent true optimal play. However what "optimal play" means is dependent on the goals you have set the agent implied by the reward values.

Any move which leads to a guarantee that a player can force a win regardless of what the opponent does, would have a Q value of +1. If the agent or opponent can force a draw at best, then it will have the Q value of the draw, and if the opponent can force a win (i.e. the current agent would lose), then the move will have the Q value of a loss. This happens because the learning process copies best case values backwards from the end game states to earlier game states that lead to them.

In a game with two perfect players, and +1, 0, -1 reward system, then each player will on its turn only see the 0 and -1 moves available. That is because there is no way to force a win in tic-tac-toe, and the perfect opponent will always act to block winning moves. The best choice out of 0 or -1 is 0: each player, when acting under its value estimates, will force a draw. There will be states defined that have a value of +1, but they will never appear as a choice to either player.

What happens if you don't make a difference in rewards between drawing and losing? In the extreme case of having win +1, lose or draw 0 against a perfect opponent, then all of the agent's available Q values will always be 0. The agent would then be faced with no way to choose between defensive plays that force a draw and mistake plays that allow the opponent to win. In turn that means some chance that the opponent will win, even when the agent had learned optimal play.

When two agents learn through self-play using the +1, 0, 0 reward scheme it gets more complicated. That is because the opponent's behaviour is part of the Q value system. Some positions will have more opportunities for the opponent to make mistakes, and score more highly. A mistake that allows an opponent to force a win will actually score worse, because the opponent will not make mistakes once it has a sure route to a +1 score. So even though the agent apparently cannot tell the difference between a loss and a draw, it should still at least partially learn to avoid losses. In fact, without running the experiment, I am not sure whether this would be enough to still learn optimal play.

Intuitively, I think it would be possible for the +1, 0, 0 agent to still learn optimal play, although maybe more slowly than the +1, 0, -1 system, because any situation that gave an opponent a chance of winning would allow it to pick the move with best score, reducing the first agents score for a move that arrived there - and this difference will be backed up to earlier positions. However, the learning would become unstable as described above, as against a perfect opponent the difference disappears as all the best options are draws or losses, and the agent will start to make mistakes again.

$\endgroup$

You must log in to answer this question.

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