22

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. Literature that teaches the basics of RL tends to use very simple environments so that all states can be enumerated. This simplifies value estimates into basic ...


9

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 techniques that are designed for discrete, linear, spaces. However, as you might imagine, if you aren't careful, this can cause a lot of trouble! Sutton & Barto's ...


7

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 precisely state this, so you could either place them at the bottom or at random. Goal state The board with the k knights placed on the target squares. State transition function A function that takes ...


6

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 to a much harder case, continuous variables, and see how we deal with it. Mood: range [-1, 1] // 1 is Happy, 0 is Neutral, -1 is Sad Hunger: range [0, 1] //...


4

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 two main ways in which the scale of a value table might be too much: Memory required to represent the table. This is relatively simple to calculate for any ...


4

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$ length where $N$ is a huge number. Let's say I solve this task using $Q$-learning and I fix my state space to $10$ vectors each of $N$ dimensions. $Q$-learning can ...


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

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

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 problem: at each time step, the agent selects an action to either perform an exploration or exploitation move. It then records the reward of the taken action ...


3

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 an exact analog for state in RL. The framework for RL is a strict generalisation of CB, and can be made similar or the same in a few separate ways: If the ...


3

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 state $s_t$ not only affects the reward $r_r$ that the agent will get but it will also affect the next state $s_{t+1}$ the agent will end up in, while, in ...


3

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 telling it as part of the learning process. If you think of the architecture used in DQN to solve Atari, they had a CNN that outputted a vector which was then ...


2

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 you wouldn't use convolutional layers in your neural net like its used in the paper you mentioned, you can use ordinary fully connected layers, it depends on the ...


2

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 neural network, it should be able to generelize well to states it has not yet encountered. If you do not use a function approximator but stick with a table, the ...


2

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 reward from not matching the previous action. By making this data part of the state, you re-establish the Markov property in the MDP model of the environment, ...


2

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 world where the top right and bottom left states are terminal as when you reach these your agent dies. These are both terminal but not the same state. For chess ...


2

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 approximator and engineered features which are a good match to predicting either the value functions or policy function that an agent will need to produce. It ...


1

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. In non-episodic problems, you might want to consider a long term state distribution under any given policy, although it is quite common to use a simple start ...


1

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 perceive the close environment such as an adjacent room. This makes sense, the problem of avoiding hazards would be trivial if the full map was revealed to ...


1

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,a) = \delta_{s^{'}s_T} \delta_{rr_{S_T}} $$ Where $\delta_{ab}$ is a Kronecker symbol, and by $r_{S_T}$ I mean the reward collected by the agent sitting in the ...


1

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 and a $\mathbb{A}(s)$ representing the set of all possible actions for each state. Based on that, probably there aren't any possible actions for the terminal ...


1

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 starting position is a state, and after you did one move you are in a different state. The total number of chess states is more than $10^{100}$. It is therefore very ...


1

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 few states, it is possible to store these values in a table (it is also useful for the intuitiveness of the explanation). However, if you start trying to solve ...


1

Here's an incomplete answer, but it may help. Your state is read by the function getExtendedObservation(). This function makes two things : it calls the function getObservation() from this source code, gets a state, and extend this state with three components : relative x,y position and euler angle of block in gripper space But what are the 5 first ...


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