4
$\begingroup$

As part of my thesis, I'm working on a zero sum game with RL to train an agent.

The game is a real-time game, a derivation of pong, one could imagine playing pong with both sides being foosball rods.

As I see it, this is an MDP with perfect information, as I use the sensor data provided by the environment to know the exact linear and angular position of the rods and the position, direction and velocity of the ball.

These information will be used as a feature vector, which will be passed into the agents network.

I considered using self-play to improve training speed regarding wall clock time, and was now not so sure if the game is after all a perfect information MDP, as there are two players involved (the same network on both sides) and the strategies of the second player are not represented in the observations fed to the network.

So the game might be a perfect information MDP, but with two "players" involved, is this still the case? Or does the fact that multiple learners are involved only make the environment more non-stationary, rather than partially observable? I also found a somewhat related paper: https://www.researchgate.net/publication/220301660_The_world_of_Independent_learners_is_not_Markovian

$\endgroup$

1 Answer 1

1
$\begingroup$

Generally, "perfect information" is not a formal trait of MDPs. There is a concept of the Markov property, but it only loosely coincides with "perfect information". For instance it is OK for there to be unknown/hidden state, provided it behaves effectively randomly (when revealed, it is drawn from a consistent distribution). An example might be a solo card game - or one where the opponent has a fixed policy such as most implementations of blackjack - which is fine as an MDP, and would not be a POMDP.

A "perfect information" game is chess. The current state of the board gives all the information required to play, and there is no additional state. When played against an opponent with a fixed policy, then this also has the Markov property. When played in general against many different opponent, and you cannot rely on the opponents' policies being the same as the training, then effectively it is non-Markov, or a POMDP. The plays for maximising reward depend on the opponent.

In many games though, there is the concept of "perfect play", of forcing the best possible result from the current game state. Planning/search routines using minimax approaches can theoretically solve these games, and reinforcement learning agents can learn them by assuming the opponent is also trying to play in this game-theoretic optimal approach. This is not quite the same as playing optimally against any given opponent - by comparison it is very safe and risk-averse compared to trying to trigger a mistake in the opponent due to something that the opponent may do. However, it often leads to stable solutions and strong players in RL.

Self play RL will tend to converge on the same game theoretic perfect play, provided it is stable in the given environment. An agent that uses the same learning engine for both players will progress through one player or the other making a mistake, and its opponent model will take advantage of that until the losing player finds a move that corrects its mistake.

To avoid this mistake/fix scenario becoming a stagnant loop of learning and unlearning, it is common to train the agent against multiple versions of itself (and sometimes other agents) to help it progress. Again this works provided the environment supports a stable game theoretic policy where it is possible to avoid mistakes against all adversarial choices. Most (possibly all? I am not sure of the theory here) two-player games are like this. When you extend to three or more players I believe this becomes a lot harder to figure out.

$\endgroup$
3
  • 1
    $\begingroup$ Let's say that you model a multi-agent system as a single-agent system. In that case, what does it mean to play against multiple opponents? It means that $p$ changes over time. If you assume that the strategy of the opponent is non-stationary (which can also be the case when we're playing against different strategies/opponents), i.e. then you have a non-stationary MDP. So, I am not sure it's "correct" to say that, if the opponent's strategy changes, then it's non-Markov, i.e. $p(s_{t+1} \mid s_t, a_t) = p(s_{t+1} \mid s_t, a_t, s_{t-1:1}, a_{t-1:1})$ does not hold... $\endgroup$
    – nbro
    Jan 19, 2022 at 15:54
  • 1
    $\begingroup$ ...because, basically, you're really changing $p$. Also, POMDPs, as the name suggests, still assume the Markov property of the states, even if you don't know in which state you are. So, being non-Markov is not equivalent to being a POMDP. Or am I missing something? $\endgroup$
    – nbro
    Jan 19, 2022 at 15:55
  • 1
    $\begingroup$ @nbro: It's fiddly. You can model adversity as POMDP (not knowing the adversary's internal state and assuming it has one), but training with multiple learning models is closer to non-stationary as you suggest. So the best theoretical model may depend on whether you are considering a specific training environment or production environment. I will have a think about it, see if I can write something clearer. $\endgroup$ Jan 19, 2022 at 16:05

You must log in to answer this question.

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