Answers.Body: <p>A few points I'd like to add (without repeating the info already provided by <a href="https://ai.stackexchange.com/a/33889/1641">nbro's answer</a>):</p>
  <hr />
  <ol>
  <li>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; <strong>we can not always model any partially observable environment as a stochastic one</strong>!</li>
  </ol>
  <p>So we probably have a subset relation here, not an equivalence relation. Personally, I often find stochastic environments to be somehow &quot;easier&quot; 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.</p>
  <hr />
  <ol start="2">
  <li>In <strong>stochastic</strong> (but fully observable) environments, <strong>there always exists an optimal deterministic policy</strong>, but in <strong>partially observable</strong> environments an <strong>optimal policy may need to be non-deterministic</strong>. As a corollary, I would say that this indeed implies that there really is some fundamental difference between the two.</li>
  </ol>
  <p>If an environment is just stochastic, but fully observable, non-deterministic policies may still <em>also</em> be optimal, but there is also always guaranteed to be at least one fully deterministic policy; a policy <span class="math-container">$\pi$</span> that, for <em>any</em> state <span class="math-container">$s$</span> assigns a probability of <span class="math-container">$\pi(a \mid s) = 1$</span> to just one action <span class="math-container">$a$</span> (and <span class="math-container">$0$</span> 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 <em>required</em> for optimality.</p>
  <p>In a partially-observable environment, it is possible that an optimal policy <strong>must be non-deterministic</strong>. Consider this &quot;drawing&quot; of an environment, consisting of a few squares, with the current position of the agent labelled as <span class="math-container">$A$</span>, and the position of the goal labelled as <span class="math-container">$G$</span>. The possible actions are to move either left or right.</p>
  <p><span class="math-container">$$\square A \square \square G \square \square \square$$</span></p>
  <p>Suppose that this environment is partially observable to the extreme extent that the agent never has any idea where it is, i.e. <em>all states are aliased</em> (look the same to the agent). A deterministic policy would then <em>always</em> go left or <em>always</em> 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 <span class="math-container">$0.5$</span>, and go right with probability <span class="math-container">$0.5$</span>. 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.</p>
  <hr />
  <ol start="3">
  <li>In <strong>partially observable environments</strong>, we often consider the possibility that there can be <strong>actions that allow us to obtain new information</strong>. 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.</li>
  </ol>
  <hr />
  <ol start="4">
  <li>In <strong>multi-agent environments</strong> (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 <em>counterfactual reasoning</em> or even explicit communication, <strong>we may gain full information or at least update our beliefs with respect to unobservable (to us) parts of the state</strong>. 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.</li>
  </ol>
  <hr />
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-30T16:24:10.243Z
Answers.Text: 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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-07T01:11:14.333Z
Answers.Text: 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.
Answers.UserDisplayName: martinkunev
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-01-07T09:19:09.763Z
Answers.Text: @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).
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-01T02:29:14.350Z
Answers.Text: This answer is enlightening, but I have two follow ups: "We can not always model any partially observable environment as a stochastic one". Isn't the belief MDP a stochastic representation of the underlying POMDP (it just requires us to define the belief)? "As a corollary, I would say that this indeed implies that there really is some fundamental difference between the two." But the belief MDP does have a deterministic policy, in which case it actually suggests some equivalence? Can you help me square these issues?
Answers.UserDisplayName: Snowball
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-01T09:49:49.493Z
Answers.Text: @Snowball In the definition of a BMDP, we have the set of belief states $B$ replacing the set of states $S$. $B$ is typically much bigger than $S$ ($B$ is continuous and infinite even if $S$ is finite). In a POMDP the policy would still be defined like $\pi : S \times A \mapsto [0, 1]$, whereas in a BMDP it would be $\pi : B \times A \mapsto [0, 1]$. So, you're essentially assuming that you have a mechanism by which you are able to provide more detailed and fine-grained information as input to your policy, which recovers the ability to encode optimal deterministic policies.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-01T09:53:29.457Z
Answers.Text: That does assume that you actually have the ability to track and update belief states in a meaningful way though (which would typically consist of tracking and memorising relevant stuff from the history, as was discussed in previous comments above we could also do in POMDPs). In a pathological case where we gain no new information for our agent at all and deterministically map from observations to belief states, we would only actually use a small (discrete, probably finite) subset of $B$, and given this subset there may be no optimal deterministic policy.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-03T00:54:19.580Z
Answers.Text: @DennisSoemers It seems to me you're almost saying this comes down to an issue of intractability given practical computational limits (since B is the set of all distributions over S), and the distinction is relevant in an applied sense as we cannot just magically obtain correct beliefs. It does not seem like you're arguing that conceptually there is a meaningful difference between the two, would that be a fair characterization? i.e. If there was a powerful enough model to take histories to beliefs, would you agree the POMDP vs. stochastic MDP distinction would be less meaningful?
Answers.UserDisplayName: Snowball
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-03T10:04:07.680Z
Answers.Text: @Snowball No there still is a fundamental distinction. In the BMDP, which is no longer partially observable w.r.t. its belief state space $B$, we will indeed have a deterministic optimal policy. But that optimal policy is only optimal with respect to the beliefs. This will only map back to a policy that is optimal in the original POMDP if the beliefs are perfect (i.e. if beliefs have no uncertainty and assign full probability to the single correct state). If there is any uncertainty in beliefs at all, a policy that is optimal w.r.t. the BMDP may not be optimal w.r.t. the original POMDP.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2022-09-03T10:13:05.920Z
Answers.Text: And, if we assume that we are capable of building truly perfect belief states, I suppose it becomes debatable whether the original POMDP was ever really a POMDP instead of just an MDP to begin with.
Answers.UserDisplayName: Dennis Soemers
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-24T13:36:41.160Z
Answers.LastActivityDate: 2021-12-24T13:36:41.160Z
Answers.UserDisplayName: Dennis Soemers
Answers.Body: <p>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.</p>
  <p>A <strong>stochastic</strong> environment can be modeled as a Markov Decision Process (MDP) or <strong>Partially Observable</strong> MDP (POMDP). So, an environment can be</p>
  <ul>
  <li>stochastic and partially observable</li>
  <li>stochastic and fully observable</li>
  </ul>
  <p>The <strong>stochasticity</strong> refers to the <strong>dynamics of the environment</strong> 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 <span class="math-container">$p(s' \mid s, a)$</span> (or, in some cases, the reward is also included <span class="math-container">$p(s', r \mid s, a)$</span>). If <span class="math-container">$p(s' \mid s, a)$</span> gave a probability of <span class="math-container">$1$</span> to one of the states and <span class="math-container">$0$</span> to all other states, we would have a deterministic environment.</p>
  <p>The <strong>partial observability</strong> 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 <span class="math-container">$b(s)$</span>. So, in the case of POMDP, we not only are uncertain about what the next state <span class="math-container">$s'$</span> might be after we have taken <span class="math-container">$a$</span> in our current state <span class="math-container">$s$</span>, but we are not even sure about what <span class="math-container">$s$</span> currently is.</p>
  <p>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).</p>
  <p>Of course, this has <strong>practical implications</strong>. 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 <span class="math-container">$\pi(a \mid s)$</span>, i.e. a probability distribution over actions given states, if you don't know the state you are in, this policy is quite useless.</p>
  <p>To deal with the uncertainty about the state the agent is in, in POMDPs, we also have the concept of an <strong>observation</strong>, 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. <a href="https://www.cs.toronto.edu/%7Evmnih/docs/dqn.pdf" rel="noreferrer">DQN</a> or <a href="https://arxiv.org/pdf/1507.06527.pdf" rel="noreferrer">this</a>), but they made a few approximations, which turned out to be useful and successful.</p>
  <p>If the difference wasn't still clear, just take a look at the equation that can be used to relate the <strong>belief state</strong> and the <strong>transition model</strong> (dynamics) of the environment</p>
  <p><span class="math-container">$$
  \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}}
  $$</span></p>
  <p>So, in a POMDP, the policy, as stated above, in theory, cannot depend on <span class="math-container">$s$</span>, but needs to depend on <span class="math-container">$b(s)$</span>, the belief state, i.e. a probability distribution over states.</p>
  <p>If this answer wasn't still satisfactory, although you probably already did it, you should read the section <a href="https://cs.calvin.edu/courses/cs/344/kvlinden/resources/AIMA-3rd-edition.pdf#page=62" rel="noreferrer"><strong>2.3.2 Properties of task environments</strong></a> 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</p>
  <blockquote>
  <p>If the next state of the environment is <strong>completely determined</strong> by the current state and the action executed by the agent, then we say the environment is deterministic; otherwise, it is stochastic</p>
  </blockquote>
  <p>The unclear part is <strong>completely determined</strong>. They should have said <strong>deterministically determined</strong> (which you can use for a rap song).</p>
  <p>However, they later clarify their definition by saying</p>
  <blockquote>
  <p>our use of the word &quot;stochastic&quot; generally implies that uncertainty about outcomes is <strong>quantified in terms of probabilities</strong></p>
  </blockquote>
  <p>In addition to that, they call an environment that is either stochastic or partially observable <strong>uncertain</strong>. It makes sense to do this because uncertainty makes the problems harder, so we can differentiate between certain and uncertain environments.</p>
  <p>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.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-24T13:26:15.133Z
Answers.Text: 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)
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-24T13:29:12.623Z
Answers.Text: @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.
Answers.UserDisplayName: nbro
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-24T14:07:33.280Z
Answers.Text: Dennis beat me to it and covered what I wanted to say :-)
Answers.UserDisplayName: Neil Slater
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-12-24T11:50:29.507Z
Answers.LastActivityDate: 2021-12-25T22:02:11.213Z
Answers.LastEditDate: 2021-12-25T22:02:11.213Z
Answers.UserDisplayName: nbro
Body: <p>In AI literature, deterministic vs stochastic and being fully-observable vs partially observable are usually considered two distinct properties of the environment.</p>
  <p>I'm confused about this because what appears random can be described by hidden variables. To illustrate, take an autonomous car (Russel &amp; 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.</p>
  <p>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.</p>
  <p>Is there some fundamental difference between stochasticity and partial observability or is this distinction made for practical reasons?</p>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-26T04:42:08.217Z
Comments.Text: 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.
Comments.UserDisplayName: Daniel Wagner
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-26T08:10:21.590Z
Comments.Text: @DanielWagner but the masked cells are in theory deducible from the other cells right? If not, then it is in fact stochastic
Comments.UserDisplayName: John Jiang
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2021-12-26T09:12:16.790Z
Comments.Text: @JohnJiang Right, the masked cells are deducible.
Comments.UserDisplayName: Daniel Wagner
Tags: <comparison><markov-decision-process><environment><pomdp>
Title: Is there a fundamental difference between an environment being stochastic and being partially observable?
UserDisplayName: martinkunev
ThreadText: # Is there a fundamental difference between an environment being stochastic and being partially observable?
  
  (Asked by: username_0 on 2021-12-24)
  
  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?
  
  **Tags:** comparison, markov-decision-process, environment, pomdp
  
  > **Comments:**
  > **username_1**: 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.  
  > **username_2**: @username_1 but the masked cells are in theory deducible from the other cells right? If not, then it is in fact stochastic  
  > **username_1**: @username_2 Right, the masked cells are deducible.  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_4 on 2021-12-24. Score: 13 | Accepted answer
  
  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](https://www.cs.toronto.edu/%7Evmnih/docs/dqn.pdf) or [this](https://arxiv.org/pdf/1507.06527.pdf)), 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**](https://cs.calvin.edu/courses/cs/344/kvlinden/resources/AIMA-3rd-edition.pdf#page=62) 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.
  
  > **Comments:**
  > **username_6**: 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)  
  > **username_4**: @username_6 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.  
  > **username_6**: username_3 beat me to it and covered what I wanted to say :-)  
  
  ---
  
  ### Answer by username_3 on 2021-12-24. Score: 8
  
  A few points I'd like to add (without repeating the info already provided by [username_4's answer](https://ai.stackexchange.com/a/33889/1641)):
  
  ---
  
  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.
  
  ---
  
  2. 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.
  
  ---
  
  3. 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.
  
  ---
  
  4. 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.
  
  ---
  
  > **Comments:**
  > **username_4**: 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.  
  > **username_0**: 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.  
  > **username_3**: @username_0 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).  
  > **username_5**: This answer is enlightening, but I have two follow ups: "We can not always model any partially observable environment as a stochastic one". Isn't the belief MDP a stochastic representation of the underlying POMDP (it just requires us to define the belief)? "As a corollary, I would say that this indeed implies that there really is some fundamental difference between the two." But the belief MDP does have a deterministic policy, in which case it actually suggests some equivalence? Can you help me square these issues?  
  > **username_3**: @username_5 In the definition of a BMDP, we have the set of belief states $B$ replacing the set of states $S$. $B$ is typically much bigger than $S$ ($B$ is continuous and infinite even if $S$ is finite). In a POMDP the policy would still be defined like $\pi : S \times A \mapsto [0, 1]$, whereas in a BMDP it would be $\pi : B \times A \mapsto [0, 1]$. So, you're essentially assuming that you have a mechanism by which you are able to provide more detailed and fine-grained information as input to your policy, which recovers the ability to encode optimal deterministic policies.  
  > **username_3**: That does assume that you actually have the ability to track and update belief states in a meaningful way though (which would typically consist of tracking and memorising relevant stuff from the history, as was discussed in previous comments above we could also do in POMDPs). In a pathological case where we gain no new information for our agent at all and deterministically map from observations to belief states, we would only actually use a small (discrete, probably finite) subset of $B$, and given this subset there may be no optimal deterministic policy.  
  > **username_5**: @username_3 It seems to me you're almost saying this comes down to an issue of intractability given practical computational limits (since B is the set of all distributions over S), and the distinction is relevant in an applied sense as we cannot just magically obtain correct beliefs. It does not seem like you're arguing that conceptually there is a meaningful difference between the two, would that be a fair characterization? i.e. If there was a powerful enough model to take histories to beliefs, would you agree the POMDP vs. stochastic MDP distinction would be less meaningful?  
  > **username_3**: @username_5 No there still is a fundamental distinction. In the BMDP, which is no longer partially observable w.r.t. its belief state space $B$, we will indeed have a deterministic optimal policy. But that optimal policy is only optimal with respect to the beliefs. This will only map back to a policy that is optimal in the original POMDP if the beliefs are perfect (i.e. if beliefs have no uncertainty and assign full probability to the single correct state). If there is any uncertainty in beliefs at all, a policy that is optimal w.r.t. the BMDP may not be optimal w.r.t. the original POMDP.  
  > **username_3**: And, if we assume that we are capable of building truly perfect belief states, I suppose it becomes debatable whether the original POMDP was ever really a POMDP instead of just an MDP to begin with.  
  
  ---
  
  