What exactly are partially observable environments?

Question

I have trouble understanding the meaning of partially observable environments. Here's my doubt.

According to what I understand, the state of the environment is what precisely determines the next state and reward for any particular action taken. So, in a partially observable environment, you don't get to see the full environment state.

So, now, consider the game of chess. Here, we are the agent and our opponent is the environment. Even here we don't know what move the opponent is going to take. So, we don't know the next state and reward we are going to get. Also, what we can see can't precisely define what is going to happen next. Then why do we call chess a fully observable game?

I feel I am wrong about the definition of an environment state or the definition of fully observable, partially observable. Kindly correct me.

Answer 1

First, note that the current state does not determine the next state. What determines the next state are the dynamics of the environment, which, in the context of reinforcement learning and, in particular, MDPs, are encoded in the probability distribution $p(s', r \mid s, a)$. So, if the agent is in a certain state $s$, it could end up in another state $s'$, but this is not only determined by being just in $s$, but also by $a$ (the action that you take in $s$) and $p$ (the dynamics of the environment).

Now, in their 3rd edition of the AIMA book, Russell and Norvig define fully observable environments as follows.

Fully observable vs. partially observable: If an agent's sensors give it access to the complete state of the environment at each point in time, then we say that the task environment is fully observable. A task environment is effectively fully observable if the sensors detect all aspects that are relevant to the choice of action; relevance, in turn, depends on the performance measure. Fully observable environments are convenient because the agent need not maintain any internal state to keep track of the world. An environment might be partially observable because of noisy and inaccurate sensors or because parts of the state are simply missing from the sensor data—for example, a vacuum agent with only a local dirt sensor cannot tell whether there is dirt in other squares, and an automated taxi cannot see what other drivers are thinking. If the agent has no sensors at all then the environment is unobservable.

This definition is also the common definition used in reinforcement learning. So, to determine whether an environment is fully or partially observable, you need to determine whether you have or not full access to a (Markovian) state or what constitutes a state in your case. You can consider chess fully observable because you have access to the configuration of the board, so, in theory, you can take optimal action by considering all possible moves of the opponent (but, of course, in practice, not even AlphaZero does this). See figure 2.6, p. 45, of the AIMA book (3rd edition) for more examples of fully and partially observable environments.

A partially observable MDP (POMDP) is a mathematical framework that can be used to model partially observable environments, where you maintain a probability distribution over the possible current (or next) state that the agent may be in.

Answer 2

You are correct in the question that in RL terms chess a game of chess where the agent is one player, and the other player has an unknown state is a partially observable environment. Chess played like this is not a fully observable environment.

I did not use the term "fully observable game" or "fully observable system" above , because that is not a reinforcement learning term. You may also read "game of perfect information" which is similar - it means there are no important hidden values in the state of the game which may impact optimal play. This is a different concern to understanding the state of your opponent.

Here is a counter-example showing that games of perfect information are not fully observable systems when you have an opponent with an unknown strategy:

• Optimal play in tic tac toe leads to a forced draw.

• Let's define a reward signal from the agent's perspective of +1 for a win, 0 for a draw, and -1 for a loss.

• If the agent's opponent always plays optimally, then a RL agent will learn to counter that optimal play and also play optimally. All action choices will have an expected return of 0 or -1, and the agent will choose the 0 options when acting greedily.

• If the agent's opponent can make a mistake that allows the agent to win, then there will be a trajectory through the game with a return of 1, or perhaps some other postive value in cases where the mistake is only made according to random chance.

• The value of states in the game therefore depends on the opponent's strategy.

• The opponent's strategy is however not observable - it is unknown and not encoded into the board state.

This should match your intuition when asking the question.

Why then, do many two player game-playing reinforcement agents for games like chess perform well, without using POMDPs?

This is because game theory on these environments supports the concept of "perfect play", and agents that assume their opponent will also attempt to play optimally - without mistakes - will usually do well. Game theory analyses choices leading to forms of the minimax theory - making a choice that your opponent is least able to exploit.

That does mean that such an agent may in fact play sub-optimally against any given opponent. For example, they could potentially turn some losing or draw situations into a win, but have little or no capability to do so unless trained against that kind of opponent. Also, playing like this may be a large risk against other opponents, it may involve playing sub-optimally at some earlier stage.

I have observed a related issue in Kaggle's Connect X competition. Connect 4 is a solved game where player one can force a win, and the best agents are all perfect players. However, they are not all equal. The best performers tweak their agent's choices for player two, to force the highest number of wins against other agents who have not coded a perfect player one. Different kinds of learning strategy lead to different imperfections, and the top of the leaderboard is occupied by the current best perfect agent that also manages to exploit the population of near-perfect agents below it in the rankings. This difference in the top-ranking agents is only possible due to the partially-observable nature of the Connect 4 game played against agents with unknown policies.

What exactly are partially observable environments?

They are environments where in at least some states, the agent does not have access to information that affects the distribution of next state or reward.

Chess played against an opponent where you have a model of their behaviour - i.e. their policy - is fully observable to the agent. This is implicitly assumed by self-play agents and systems, and can work well in practice.

Chess played against an opponent without a model of their behaviour is partially observable. In theory, you could attempt to build a system using a partially observable MDP model (POMDP) to account for this, in an attempt to try and force an opponent into states where they are more likely to make a decision that is good for the agent. However, simply playing optimally as possible in response to all plays by the opponent - i.e. assuming their policy is the same near optimal one as yours even after observing their mistake - is more usual in RL.

The original Alpha Go actually had a separate policy network for its own choices and modelling those of humans. This was selected experimentally as performing slightly better than assuming human opponents used the same policy as the self-play agent.

Answer 3

A partially observable environment means it is from the agent's perspective that the agent observes the environment partially. At every time step, the agent takes action based on this partial observation. Based on the agent's action, the state of the environment changes, but the agent may not know all the changes.