22 votes
Accepted

How to define states in reinforcement learning?

The problem of state representation in Reinforcement Learning (RL) is similar to problems of feature representation, feature selection and feature engineering in supervised or unsupervised learning. ...
user avatar
  • 24.5k
10 votes

How to define states in reinforcement learning?

A common early approach to modeling complex problems was discretization. At a basic level, this is splitting a complex and continuous space into a grid. Then you can use any of the classic RL ...
user avatar
7 votes
Accepted

What are the state space and the state transition function in AI?

Initial state How things are at first. In your particular example, it would be where your k knights are placed on the board initially. Your problem doesn't ...
user avatar
  • 585
6 votes
Accepted

What techniques are used to make MDP discrete state space manageable?

tl:dr Read chapter 9 of an Introduction of Reinforcement Learning There is definitely a problem (a curse if you will) when the dimensionality of a task (MDP) grows. For fun, lets extend your problem ...
user avatar
4 votes

What constitutes a large space state (in Q-learning)?

I know this might be specific to different problems but does anyone know if there is any rule of thumb or references on what constitutes a large state space? Not really, it is all relative. There are ...
user avatar
  • 24.5k
4 votes
Accepted

What is a high dimensional state in reinforcement learning?

Usually when people write about having a high-dimensional state space, they are referring to the state space actually used by the algorithm. Suppose my state is a high dimensional vector of $N$ ...
user avatar
  • 9,469
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 ...
user avatar
  • 24.5k
3 votes

Is it appropriate to represent 'total failure' as an absorbing state?

In an episodic problem, absorbing states are implemented to make the maths work similarly to continuing tasks. It allows one set of equations to cover two types of MDP (continuing and episodic). For ...
user avatar
  • 24.5k
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 ...
user avatar
  • 34.5k
3 votes

It is possible to solve a problem with continuous action spaces and no states with reinforcement learning?

A stateless RL problem can be reduced to a Multiarmed Bandit (MAB) problem. In such a scenario, taking an action will not change the state of the agent. So, this is the setting of a conventional MAB ...
user avatar
3 votes

What is the relation between the context in contextual bandits and the state in reinforcement learning?

Conceptually, in general, how is the context being handled in CB, compared to states in RL? In terms of its place in the description of Contextual Bandits and Reinforcement Learning, context in CB is ...
user avatar
  • 24.5k
3 votes
Accepted

What is the relation between the context in contextual bandits and the state in reinforcement learning?

The notion of a state in reinforcement learning is (more or less) the same as the notion of a context in contextual bandits. The main difference is that, in reinforcement learning, an action $a_t$ in ...
user avatar
  • 34.5k
3 votes
Accepted

How does replacing states with latent representations help RL agents?

In short, it is much easier for the agent to learn from a smaller dimensional state space. This is because the agent must also do representation learning; i.e. it must also infer what the state is ...
user avatar
2 votes

What is a high dimensional state in reinforcement learning?

Yes, it makes sense to use DQN in state space with small number of dimensions as well. It doesn't really matter how big your state dimension is, but if you have state with 2 dimensions for instance ...
user avatar
  • 2,236
2 votes
Accepted

What happens when the agent faces a state that never before encountered?

Having too many states to actually visit is a common problem in RL. This is exactly why we often use function approximation. If you replace your q table with a good function approximator such as a ...
user avatar
2 votes
Accepted

Reinforcement Learning algorithm with rewards dependent both on previous action and current action

The answer to both your concerns is: Add the previous action choice to the state representation. It is all you need to do. It gives the agent the data it needs to learn the association of negative ...
user avatar
  • 24.5k
2 votes

How to approach a blackjack-like card game with the possibility of cards being counted?

How can I approach projects with a big state space without loosing a huge chunk of predictability (which I might fear with DQN, DDPQ or TD3)? You can impact this by choosing a combination of function ...
user avatar
  • 24.5k
2 votes
Accepted

Does the state space of an MDP change in these two examples?

Whilst engineering solutions in reinforcement learning, I think it is common to discuss the concept of state space loosely, in terms of what the search space looks like for the algorithm, and what ...
user avatar
  • 24.5k
2 votes
Accepted

What is the difference between terminal state, nonterminal states and normal states?

Terminal state is always the same in the sense that it represents the same thing, that the episode is over. They don’t need to be the exact same state; for instance you could have an $n$ by $n$ grid ...
user avatar
1 vote

How to manage impossible actions?

You could code your agent's policy to never select impossible actions. Your other question implies that you are writing your own behaviour policy function (e.g. you asked about implementing a softmax ...
user avatar
  • 24.5k
1 vote
Accepted

Is it possible learning convergence is lost in Reinforcement Learning as the state space grows?

With tabular reinforcement learning (RL) methods, then catastrophic forgetting does not come into play, as it is a feature of online learning with approximators such as neural networks. Essentially ...
user avatar
  • 24.5k
1 vote
Accepted

Does $R_{s}=E[R_{t}|S_{t}=s]$ indicate the reward we might expect on getting on average moving from any other state to $s$?

$$R_{s}=\mathbb{E}[R_{t}|S_{t}=s]$$ is the expected reward at time step $t$ given that the state at time $t$ is $s$, where $R_{t}$ and $S_t$ are random variables that represent the reward and state ...
user avatar
  • 34.5k
1 vote
Accepted

Why do terms in the computation of state space size scale exponentially?

Intuitively, I feel like if there are 30 foods, each with 2 states, then that is 60 states, no $2^{30}$. Let's try it with 3 pellets. If you are right there would be $2 \times 3 = 6$ states, if the ...
user avatar
  • 24.5k
1 vote
Accepted

How DFS may expand the same state many times via different paths in an acyclic state space?

First, note that the verb to expand has a specific meaning in this context: when you expand a node/state $s$, you try each action $a_1, \dots, a_n$ available from $s$, and each of these actions $a_i$ ...
user avatar
  • 34.5k
1 vote

Is there any inherent assumption of start and goal states in an MDP?

Is there any reason for not specifying start and goal states in MDP like in a finite automaton? In general MDPs have a start state distribution. That may be a single state, but does not have to be. ...
user avatar
  • 24.5k
1 vote
Accepted

Q-learning in gridworld with random board

From your linked description of the game, we can see it has a key property when used normally in AI teaching: Partially observable: The Wumpus world is partially observable because the agent can only ...
user avatar
  • 24.5k
1 vote

Is there a natural way to define the terminal state from the MDP transition probabilities $p(s',r|s,a)$?

As far as I remember, terminal state is a state from which agent cannot escape, i.e if the agent reached this state, he will never escape. In mathematical notation can be written as: $$ p(s^{'}, r|s_T,...
user avatar
1 vote

Is there a natural way to define the terminal state from the MDP transition probabilities $p(s',r|s,a)$?

I don't know if there is a general definition of the terminal state based on the MDP transition probabilities. But remember that we define our MDP problem in a $\mathbb{S}$ set of all possible states ...
user avatar
1 vote

What happens when the agent faces a state that never before encountered?

I will try to explain this problem with the very tangible example of chess. In chess, the number of possible states is any configuration that you can make with the pieces on the board. So, the ...
user avatar
1 vote
Accepted

Do I need to know in advance all possible number of states in Q-Learning?

When you start off learning about Q-learning, you start with a simple example that has a few states. For each of the states, you try to estimate what the 'value' is of that state. Because there are so ...
user avatar

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