I started teaching myself about reinforcement learning a week ago and I have this confusion about the learning experience. Let's say we have the game Go. And we have an agent that we want to be able to play the game and win against anyone. But let's say this agent learn from playing against one opponent, my questions then are:

  1. Wouldn't the agent (after learning) be able to play only with that opponent and win? It estimated the value function of this specific behaviour only.
  2. Would it be able to play as good with weaker players?
  3. How do you develop an agent that can estimate a value function that generalizes against any behaviour and win? Self-play? If yes, how does that work?
up vote 5 down vote accepted

Reinforcement Learning (RL) at its core does not have anything directly to say about adversarial environments, such as board games. That means in a purely RL set up, it is not really possible to talk about the "strength" of a player.

Instead, RL is about solving consistent environments, and that consistency requirement extends to any opponents or adversarial components. Note that consistency is not the same as determinism - RL theory copes well with opponents that effectively make random decisions, provided the distribution of those decisions does not change based on something the RL agent cannot know.

Provided an opponent plays consistently, RL can learn to optimise against that opponent. This does not directly relate to the "strength" of an opponent, although usually strong opponents present a more challenging environment to learn overall.

  1. Wouldn't the agent (after learning) be able to play only with that opponent and win? since it estimated the value function of this specific behavior only.

If the RL has enough practice and time to optimise against the opponent, then yes the value function (and any policy based on it) would be specific to that opponent. Assuming, the opponent did not play flawlessly, then the RL would learn to play such it would win as often as possible against the opponent.

When playing against other opponents, the success of the RL agent will depend on how similar the new opponent was to the original that it trained against.

  1. would it be able to play as good with weaker players?

As stated above, there is not really a concept of "stronger" or "weaker" in RL. It depends on the game, and how general the knowledge is that strong players require in order to win.

In theory you could construct a game, or deliberately play strongly, but with certain flaws, so that RL would play very much to counter one play style, and would fail against another player that did not have the same flaws.

It is difficult to measure this effect, because human players learn from their mistakes too, and are unlikely to repeat the exact same game time after time, but with small variations at key stages. Humans do not make consistent enough opponents, and individual humans do not play enough games at each stage of their ability to study fine-grained statistics of their effective policies.

In practice it seems likely that the effect of weakening against new players would be there in RL, due to sampling error if nothing else. However, it seems that the "strength" of players as we measure them in any game of skill such as chess or go, does correlate with a generalised ability. In part this is backed up by consistent results with human players and Elo ratings.

Any game where you can form "rings" of winning players:

  • Player B consistently beats Player A
  • Player C consistently beats Player B
  • Player A consistently beats Player C

Could cause issues of the type you are concerned about when applying RL to optimise an artificial agent.

  1. How do you develop an agent that can estimate a value function that generalizes against any behavior and win?

If is possible to play perfectly, then a value function which estimated for perfect play would work. No player could beat it. Think of Tic Tac Toe - it is relatively easy to construct perfect play value functions for it.

This is not achievable in practice in more complex games. To address this, and improve the quality of its decisions, what AlphaGo does is common to many game-playing systems, using RL or not. It performs a look-ahead search of positions. The value function is used to guide this. The end result of the search is essentially a more accurate value function, but only for the current set of choices - the search focuses lots of computation on a tiny subset of all possible game states.

One important detail here is that this focus applies at run time whilst playing against any new opponent. This does not 100% address your concerns about differing opponents (it could still miss a future move by a different enough opponent when searching). But it does help mitigate smaller statistical differences between different opponents.

This search tree is such a powerful technique that for many successful game playing algorithms, it is possible to start with an inaccurate value function, or expert heuristics instead, which are fixed and general against all players equally. IBM's Deep Blue is an example of using heuristics.

self-play? if yes, how does that work?

Self-play appears to help. Especially in games which have theoretical optimal play, value functions will progress towards assessing this optimal policy, forming better estimates of state value with enough training. This can give a better starting point than expert heuristics when searching.

Most of your questions are already addressed very well by Neil's answer, so I won't address those again. I'd just like to clarify additionally on the following point:

But let's say this agent learn from playing against one opponent

Precisely that assumption of learning from against a single opponent causes many issues. In fact, even if that "single opponent" is changing/improving, you can still have an unstable learning process. For instance, two agents that are simultaneously learning (or a single agent and a copy of itself) can keep infinitely going around in circles as Neil also already hinted at in a game like Rock-Paper-Scissors.

In the original AlphaGo publication (2016), learning from self-play was done by randomly selecting one of a set of (relatively recent) copies of the learning agent every game, rather than always playing against an exact copy of the single most recent version of the agent. Adding more diversity to the "training partners" in that way can help to learn a more robust policy that can handle different opponents. Of course, we shouldn't go overboard with this kind of randomization; you still want to make sure to train against strong training partners (or opponents that have a roughly similar level of strength as the learning agent), an agent that already is quite strong won't be able to learn a lot from playing against an extremely weak agent anymore.

In 2017, a new paper appeared on AlphaGo Zero. In this paper, they no longer used such randomization as described above, but still had a stable learning process from self-play. As far as I'm aware, the most likely hypothesis to explain this stability is the fact that Monte-Carlo Tree Search was used during the self-play training process to improve the update targets. This is different from the use of lookahead search that Neil already described during gameplay, after training. By also incorporating lookahead search during the training process, and using it to improve update targets, the hypothesis is that you can reduce the risk of "overfitting" against the training partner. The lookahead search actually "thinks" a bit about other moves that the training partner could have selected other than what it actually did, and incorporates that in the update targets. A similar combination of MCTS and self-play reinforcement learning was also independently published (by different authors) to result in stable learning in different games.

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.