Tag Info

11

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 ...

7

A few points I'd like to add (without repeating the info already provided by nbro's answer): 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 ...

4

The usual (as presented in Reinforcement Learning: An Introduction) $Q$-learning and SARSA algorithms use (and update) a function of a state $s$ and action $a$, $Q(s, a)$. These algorithms assume that the current state $s$ is known. However, in POMDP, at each time step, the agent does not know the current state, but it maintains a "belief" (which, ...

4

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 ...

3

An MDP is just a POMDP where the states are observable. So, we can formulate an MDP as POMDP such that the observation space is equal to the state space. We also need to take care of the observation function. Formally, an MDP can be defined as a tuple $M_\text{MDP} = (S, A, T, r, \gamma)$, where $S$ is the state space $A$ is the action space $T = p(s' \mid ... 3 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'$, ... 3 The game of TIC-TAC-TOE can be modelled as a non-deterministic Markov decision process (MDP) if, and only if: The opponent is considered part of the environment. This is a reasonable approach when the goal is to solve playing against a specific opponent. The opponent is using a stochastic policy. Stochastic policies are a generalisation that include ... 3 I will attempt to provide an answer to your questions based on the information you can find in the papers A Heuristic Variable Grid Solution Method for POMDPs (1997) by Ronen I. Brafman and Point-based value iteration: An anytime algorithm for POMDPs (2003) by Joelle Pineau et al. A grid-based approximate solution to a POMDP attempts to estimate a value ... 3 There is indeed a close parallel here, but the concepts are distinct. Every perfect information game is fully observable, but not every fully observable game is a game of perfect information. A game of imperfect information is one in which you lack knowledge of any of the following: The state of the game (e.g. current market prices). The rewards you will ... 3 I think that the normalisation factor is assumed to be non-zero. So, in practice, I guess, you must eventually check that$P(z \mid b, a)$is non-zero (even though, I guess, it will likely never be zero because of round-off errors in computers). The formula to calculate$b'(s')$comes from its definition, which is based on Bayes' theorem, where the ... 2$O(a, s', z) = \mathbb{P}(z \mid a, s')$is a conditional probability distribution, so it always needs to sum up to$1$. You should interpret$O(a, s', z)$as the probability of observation$z$, given that the agent took action$a$and landed in state$s'$.$O(a, s', z)$is thus not a joint distribution, even though the notation$O(a, s', z)$might suggest ... 2 Is it possible for value-based methods to learn stochastic policies? Yes, but only in a limited sense, due to the ways it is possible to generate stochastic policies from a value function. For instance, the simplest exploratory policy used by SARSA and Monte Carlo Control,$\epsilon$-greedy, is stochastic. SARSA natually learns the optimal$\epsilon$-... 2 What could happen if we wrongly assume that the POMDP is an MDP and do reinforcement learning with this assumption over the MDP? It depends on a few things. The theoretical basis of reinforcement learning needs the state descriptions to have the Markov property for guarantees of convergence to optimal or approximately optimal solutions. The Markov property ... 2 Both Belief-MDPs and Bayes-Adaptive MDPs (BAMDPs) are special cases of POMDPs and their state space is augmented with a belief over their unobserved/hidden variables. In a belief-MDP, the hidden variables can change over the course of an episode. (Eg. Both the position and the uncertainty in the position of the robot can vary during an episode). In a BAMDP, ... 2 Your setting (of randomly dropping out reward signals) impacts expected future reward by multiply everything by a common factor$(1-\epsilon)\$. As reinforcement learning (RL) control is based on maximising expected future reward, and multiplying by a positive constant does not affect ranking of action values, all existing RL methods will cope just fine ...

1

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 ...

1

I guess it depends on what the goal is. If the goal is a general reward function, this formulation as an MPOMDP could make sense. One way to think about this, is as a way of modeling a general (centralized) POMDP with factored actions and observation spaces. However, it seems that what you are describing might be an active perception problem, where the goal ...

1

Not exactly, at least traditionally: in Game Theory, "imperfect information" is most often defined as agents having only partial information about the history of agents' actions, as you correctly noted. But also note that this doesn't refer to the general world facts or state. But "partial observability" is typically used in terms of systems, e.g. in Markov ...

1

Yes, the core differences between the different categories of problems are correct as you've described them. For SMDPs, I'd like to remark that the water boiling example is maybe not the best. That looks more like an example of "delayed rewards", but not one of "durative actions": when the agent takes that action to raise the temperature, ...

1

There is no major difference here between a POMDP and MDP. When setting reward values, you are generally trying to give the minimal information to the agent that when the sum of rewards is maximised, it solves the problem that you are posing. In literature it is common to use one simple number as a reward, but I am not sure if this is really how you ...

Only top voted, non community-wiki answers of a minimum length are eligible