Hot answers tagged

13 votes
Accepted

Is there a fundamental difference between an environment being stochastic and being partially observable?

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 ...
nbro's user avatar
  • 40.2k
8 votes

Is there a fundamental difference between an environment being stochastic and being partially observable?

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....
Dennis Soemers's user avatar
  • 10.2k
7 votes
Accepted

Can Q-learning be used in a POMDP?

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 ...
nbro's user avatar
  • 40.2k
4 votes

What exactly are partially observable environments?

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 ...
Neil Slater's user avatar
  • 31.6k
3 votes
Accepted

What's the relationship between Bayesian RL and POMDPs?

After looking more into this, I think I have a better understanding. In Bayesian RL, one has uncertainty over the transition function of the environment. For example, we might know that our robot can ...
mdc's user avatar
  • 380
3 votes
Accepted

What exactly are partially observable environments?

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 ...
nbro's user avatar
  • 40.2k
3 votes
Accepted

Why is tic-tac-toe considered a non-deterministic environment?

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 ...
Neil Slater's user avatar
  • 31.6k
3 votes

What is the intuition behind grid-based solutions to POMDPs?

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-...
nbro's user avatar
  • 40.2k
3 votes

Are perfect and imperfect information games modelled as fully and partially observable environments, respectively?

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 ...
John Doucette's user avatar
3 votes

Can the normalization factor for the belief state update be zero?

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 ...
nbro's user avatar
  • 40.2k
2 votes
Accepted

How are POMDPs solved in practice?

A formal POMDP approach that models a belief state (a distribution over possible states) needs to have a theoretical model for the hidden aspects of the state. This is not always appropriate or ...
Neil Slater's user avatar
  • 31.6k
2 votes
Accepted

Does the observation function for POMDP always add up to 1?

$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 ...
nbro's user avatar
  • 40.2k
2 votes
Accepted

Is it possible for value-based methods to learn stochastic policies?

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 ...
Neil Slater's user avatar
  • 31.6k
2 votes
Accepted

What could happen if we wrongly assume that the POMDP is an MDP?

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 ...
Neil Slater's user avatar
  • 31.6k
2 votes

What is the difference between Bayes-adaptive MDP and a Belief-MDP in Reinforcement Learning?

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 ...
Mohith Kaameswaran Sakthivel's user avatar
2 votes

Is there a mathematical formalism to deal with a missing reward signal?

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 ...
Neil Slater's user avatar
  • 31.6k
1 vote
Accepted

Are multi agent or self-play environments always automatically POMDPs?

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 ...
Neil Slater's user avatar
  • 31.6k
1 vote

Can a Reinforcement Learning problem with multiple simultaneous actions be formalized as a Multiagent Partially Observable Markov Decision Process?

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 (...
F.A.O.'s user avatar
  • 11
1 vote

Is there a way of path reconstruction using only the history of belief states?

The belief state in a POMDP is a distribution over the hidden state given all past actions and observations, i.e., at time $k$, the belief state is $b_k(s_k) \triangleq P(s_k \mid a_{0:k-1}, z_{1:k})$,...
mikkola's user avatar
  • 580
1 vote

Are perfect and imperfect information games modelled as fully and partially observable environments, respectively?

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 ...
Bastian Blankenburg's user avatar
1 vote

Is my understanding of the differences between MDP, Semi MDP and POMDP correct?

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 ...
Dennis Soemers's user avatar
  • 10.2k
1 vote
Accepted

How to define a reward function in POMDPs?

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, ...
Neil Slater's user avatar
  • 31.6k

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