In one of the recent blog post by Deepmind, they have used game theory in Alpha Star algorithm. Deep Mind Alpha-Star:
Mastering this problem requires breakthroughs in several AI research challenges including:
- Game theory: StarCraft is a game where, just like rock-paper-scissors, there is no single best strategy. As such, an AI training process needs to continually explore and expand the frontiers of strategic knowledge.
Where the game theory is applied when it comes to reinforcement learning?
Where the game theory is applied when it comes to reinforcement learning?
It is not used directly in this case, and AlphaStar makes no breakthroughs in game theory. The blog's wording here is not super precise.
The point of the quote was to explain the extra challenge, which occurs in many games where opponents can react to each other's choices and there is often a counter-strategy to any given policy. Rock-paper-scissors is the simplest game that has this challenge, but it is common in many strategy games, as the game designers typically don't want a single best strategy to dominate the game, often going to some lengths to balance options in the game so that more of their game content is used and to keep a level of uncertainty and excitement in the game-playing community.
The actual breakthroughs in regards to the quote in your question, are in finding ways to perform the kinds of long-term exploration that allow for different high-level strategies. Many RL algorithms perform relatively local exploration which would be too weak to keep track of entirely different strategies and decide when to use them.
The way that Deep Mind team approached this is explained in their blog:
To encourage diversity in the league, each agent has its own learning objective: for example, which competitors should this agent aim to beat, and any additional internal motivations that bias how the agent plays. One agent may have an objective to beat one specific competitor, while another agent may have to beat a whole distribution of competitors [ . . . ]
So Deep Mind have not resolved any of that at a theoretical level, and have not used game theory in any direct sense. However, they have identified the kind of game theory scenario that applies, and have used that in the design, making steps in an engineering sense towards practical solutions.
Other solutions in RL might also apply, such as hierarchical RL for capturing high-level actions as strategies to inform lower-level decisions, or using slow changing noise functions to drive exploration (as opposed to something which changes faster such as epsilon-greedy).
In general, game theory is related to reinforcement learning, in that both construct a formal view of optimising utility:
Game theory is useful for analysing multi-agent scenarios, but generally analyses optimal policies for relatively simple single-step or repeated games.
Reinforcement learning is well-described for single agents, and deals well with sequential decision making, but does not have much quite as much material for dealing with competitive and co-operative multi-agent environments - typically treating other agents as "part of the environment".
There is enough cross-over between the two theories that they can be used to inform each other in an intuitive way, as Deep Mind have done here.
In more tractable game environments, game theory is able to determine stable and effective policies - for instance in rock-paper-scissors, the Nash equilibrium policy (one which players will be punished for moving away from) is randomly selecting each action with 1/3 probability. Note this is not necessarily the optimal policy - that depends on the opponent's behaviour - but it is an expected stable outcome for two rational and capable opponents to arrive at.
If you develop a rock-player-scissor learning bot using RL, and it learns this strategy through self play, then you can be relatively happy that your learning algorithm worked. That would be one way of using RL and game theory together.
Deep Mind don't know the Nash equilibrium of Star Craft strategies, and in fact the strategies are only loosely defined in terms of low-level actions, so it is not clear whether it is possible. The analysis of strategies supplied in the blog (e.g. a "rushing" strategy) are based on observations of the game and adding a human narrative to help understand what is going on. In practice, it is the sampling of opponents each preferring a different strategy or set a particular goal in the game, that trains a single neural-network based bot that has experience of countering multiple strategies and can express actions that optimally beat any strategy that matches patterns it has learned in self-play and observes an opponent using.
