10
$\begingroup$

In AI literature, deterministic vs stochastic and being fully-observable vs partially observable are usually considered two distinct properties of the environment.

I'm confused about this because what appears random can be described by hidden variables. To illustrate, take an autonomous car (Russel & Norvig describe taxi driving as stochastic). I can say the environment is stochastic because I don't know what the other drivers will do. Alternatively, I can say that the actions of the drivers are determined by their mental state which I cannot observe.

As far as I can see, randomness can always be modeled with hidden variables. The only argument I came up with as to why the distinction is necessary is Bell's inequality, but I don't think that AI researchers had this in mind.

Is there some fundamental difference between stochasticity and partial observability or is this distinction made for practical reasons?

$\endgroup$
3
  • $\begingroup$ Going in slightly the other direction... it seems pretty easy to make a system that is only partially observable but not stochastic. Say, a Game of Life implementation where all the cells outside of the starting configuration are masked out. So the two can't be exact synonyms. $\endgroup$ Dec 26, 2021 at 4:42
  • $\begingroup$ @DanielWagner but the masked cells are in theory deducible from the other cells right? If not, then it is in fact stochastic $\endgroup$
    – John Jiang
    Dec 26, 2021 at 8:10
  • $\begingroup$ @JohnJiang Right, the masked cells are deducible. $\endgroup$ Dec 26, 2021 at 9:12

2 Answers 2

11
$\begingroup$

I think the distinction is made more for conceptual reasons, which has practical implications, so let me review the usual definitions of a stochastic and partially observable environment.

A stochastic environment can be modeled as a Markov Decision Process (MDP) or Partially Observable MDP (POMDP). So, an environment can be

  • stochastic and partially observable
  • stochastic and fully observable

The stochasticity refers to the dynamics of the environment and, more specifically, to how the environment stochastically moves from one state to the other after an action is taken (basically, a Markov chain with actions and rewards). In other words, in a stochastic environment, we have the distribution $p(s' \mid s, a)$ (or, in some cases, the reward is also included $p(s', r \mid s, a)$). If $p(s' \mid s, a)$ gave a probability of $1$ to one of the states and $0$ to all other states, we would have a deterministic environment.

The partial observability refers to the fact that we don't know in which state the agent is, so we can think of having or maintaining a probability distribution over states, like $b(s)$. So, in the case of POMDP, we not only are uncertain about what the next state $s'$ might be after we have taken $a$ in our current state $s$, but we are not even sure about what $s$ currently is.

So, the difference is made so that we can deal with uncertainties about different parts of the environment (dynamics and actual knowledge of the state). Think about a blind guy that doesn't have the full picture (I hope this doesn't offend anyone) and think about a guy that sees well. The guy that sees well still isn't sure about tomorrow (maybe this is not a good example as you can argue that this is also due to the fact that the guy that sees well doesn't know the full state, but I hope this gives you the intuition).

Of course, this has practical implications. For example, it seems that you cannot directly apply the solutions that you use for MDPs to POMDPs. More precisely, for an MDP, if you learn the policy $\pi(a \mid s)$, i.e. a probability distribution over actions given states, if you don't know the state you are in, this policy is quite useless.

To deal with the uncertainty about the state the agent is in, in POMDPs, we also have the concept of an observation, which is the information that the agent gathers from the environment about the current state (e.g., in the example of a blind guy, the observations would be the sounds, touch, etc.), in order to update its belief about the current state. In practice, some people tried to apply the usual RL algorithms for MDPs to POMDPs (see e.g. DQN or this), but they made a few approximations, which turned out to be useful and successful.

If the difference wasn't still clear, just take a look at the equation that can be used to relate the belief state and the transition model (dynamics) of the environment

$$ \underbrace{b^{\prime}\left(s^{\prime}\right)}_{\text{Next belief state}}=\alpha \underbrace{P\left(o \mid s^{\prime}\right)}_{\text{Probability of observation }o \text{ given }s'} \sum \underbrace{P\left(s^{\prime} \mid s, a\right)}_{\text{Transition}\\ \text{model}} \underbrace{b(s)}_{\text{Previous belief state}} $$

So, in a POMDP, the policy, as stated above, in theory, cannot depend on $s$, but needs to depend on $b(s)$, the belief state, i.e. a probability distribution over states.

If this answer wasn't still satisfactory, although you probably already did it, you should read the section 2.3.2 Properties of task environments of the AIMA book (3rd edition). Their description of stochastic and partially observable environment seems to be consistent with what I wrote here, but maybe their description of a stochastic environment is not fully clear, because they say

If the next state of the environment is completely determined by the current state and the action executed by the agent, then we say the environment is deterministic; otherwise, it is stochastic

The unclear part is completely determined. They should have said deterministically determined (which you can use for a rap song).

However, they later clarify their definition by saying

our use of the word "stochastic" generally implies that uncertainty about outcomes is quantified in terms of probabilities

In addition to that, they call an environment that is either stochastic or partially observable uncertain. It makes sense to do this because uncertainty makes the problems harder, so we can differentiate between certain and uncertain environments.

To be honest, I don't know if there's some kind of mathematical formalism that doesn't differentiate between stochastic or partially observable environments, but I am not sure how useful it might be.

$\endgroup$
3
  • 2
    $\begingroup$ I think there is cross-over between stochastic and partially observable where state knowledge is partial but revealed without any impact/bias within the system. A good example to use is the difference between card games Blackjack (effectively stochastic, and no need to model as POMDP, even though you cannot see the dealer's hand or the non-revealed cards) and Poker (where hidden state of opponent's hands radically impacts results of actions non-randomly) $\endgroup$ Dec 24, 2021 at 13:26
  • $\begingroup$ @NeilSlater I think if you elaborate on these examples (i.e. why they don't need to be modeled as POMDP), it may be a good answer, in addition to this canonical answer (let's say), which can be useful. $\endgroup$
    – nbro
    Dec 24, 2021 at 13:29
  • 1
    $\begingroup$ Dennis beat me to it and covered what I wanted to say :-) $\endgroup$ Dec 24, 2021 at 14:07
7
$\begingroup$

A few points I'd like to add (without repeating the info already provided by nbro's answer):


  1. I think you're half-right, in that indeed we can probably always model randomness as hidden information (e.g., as the hidden random seed in a software implementation of an environment). However, the other way around does not work; we can not always model any partially observable environment as a stochastic one!

So we probably have a subset relation here, not an equivalence relation. Personally, I often find stochastic environments to be somehow "easier" to handle than partially observable ones. So, it is generally beneficial to simply treat them as such, rather than unnecessarily casting them into the often-more-difficult format of partially observable environments.


  1. In stochastic (but fully observable) environments, there always exists an optimal deterministic policy, but in partially observable environments an optimal policy may need to be non-deterministic. As a corollary, I would say that this indeed implies that there really is some fundamental difference between the two.

If an environment is just stochastic, but fully observable, non-deterministic policies may still also be optimal, but there is also always guaranteed to be at least one fully deterministic policy; a policy $\pi$ that, for any state $s$ assigns a probability of $\pi(a \mid s) = 1$ to just one action $a$ (and $0$ to any other action for that same state). Sometimes it may be fine to be indifferent (and distribute the probability mass over more than a single action), but this is never strictly required for optimality.

In a partially-observable environment, it is possible that an optimal policy must be non-deterministic. Consider this "drawing" of an environment, consisting of a few squares, with the current position of the agent labelled as $A$, and the position of the goal labelled as $G$. The possible actions are to move either left or right.

$$\square A \square \square G \square \square \square$$

Suppose that this environment is partially observable to the extreme extent that the agent never has any idea where it is, i.e. all states are aliased (look the same to the agent). A deterministic policy would then always go left or always go right, but, depending on whether the agent is currently to the left or to the right of the goal, one of those two deterministic policies would never reach the goal. And the agent has no way at all to tell which one would be the bad policy. The optimal policy in this environment is to simply go left with probability $0.5$, and go right with probability $0.5$. Eventually, the agent will get lucky and end up in the goal position. The partially observable nature of this environment really makes it necessary to follow a stochastic policy.


  1. In partially observable environments, we often consider the possibility that there can be actions that allow us to obtain new information. These are not necessarily actions that directly lead to any rewards or future returns, but really only allow us to observe things that we could not observe before (and hence possibly allow us to, with more certainty, follow a better policy afterwards). This idea does not really exist in fully observable stochastic environments.

  1. In multi-agent environments (consider, for example, many card games), other agents (often opponents but could also be agents with similar goals to our own) may have access to different information/observations from our own agent. This means that, for example through counterfactual reasoning or even explicit communication, we may gain full information or at least update our beliefs with respect to unobservable (to us) parts of the state. For example, based on the actions of an opponent in a card game, we may infer that it is very likely or very unlikely for them to have certain cards, because otherwise they very likely would not have acted in the way that they did. This sort of reasoning does not apply to fully observable stochastic environments.

$\endgroup$
3
  • $\begingroup$ Just one remark about your example of the POMDP. The agent still gets an observation from the environment in a POMDP. So, even if the policy is deterministic, it doesn't necessarily always go right or left, it can go right or left, depending on the observation it receives (if you define a policy as $\pi(a \mid o)$). However, if the observations are not informative, yes, I guess a deterministic policy has no way of saying "ok, now I need to go right, after I went left". In other words, in your explanation, it seems that you don't define a policy to be conditioned on $o$ or the belief state. $\endgroup$
    – nbro
    Dec 30, 2021 at 16:24
  • $\begingroup$ For the POMDP example, the agent can look at the history of its moves - its actions can be 1 square left, 2 squares right, 3 squares left, etc. I suppose in a more complicated environment the movement can be noisy so that the agent doesn't know how much it moved exactly. Then some form of randomness is necessary. $\endgroup$ Jan 7 at 1:11
  • $\begingroup$ @martinkunev Sure, adding knowledge about the history can often help a little bit to deal with imperfect observations. For instance, in environments with pixel/image/camera-based observations (like Atari games), it is also common to augment the states with a few of the previous frames, because multiple frames combined can tell you about the velocities/directions in which objects are moving. But this may not always suffice (imagine a card game, or the blocks example above with an incredibly long chain of blocks such that after $100$ moves to the left you still don't know where you might be). $\endgroup$
    – Dennis Soemers
    Jan 7 at 9:19

You must log in to answer this question.

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