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
  • 23.8k
17 votes

How to stay a up-to-date researcher in ML/RL community?

There are some wonderful resources for keeping up to date in the ML community. Here are just a handful that a coworker showed me: Deep Learning Monitor: this site contains hot and new papers along ...
user avatar
  • 2,249
12 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 ...
user avatar
  • 33.8k
9 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

How are the reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ equivalent?

In general the different reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ are not equivalent mathematically, so you will not find any formal proof. It is possible for the functions to resolve to ...
user avatar
  • 23.8k
7 votes

Why is the policy not a part of the MDP definition?

The MDP defines the environment (which corresponds to the task that you need to solve), so it defines e.g. the states of the environment, the actions that you can take in those states, the ...
user avatar
  • 33.8k
7 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....
user avatar
  • 9,379
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
6 votes
Accepted

What are some resources on continuous state and action spaces MDPs for reinforcement learning?

There is a small survey of continuous states, actions and time in reinforcement learning in my thesis proposal. Regarding books, Reinforcement Learning: State-of-the-Art seems to be pretty up-to-date ...
user avatar
  • 1,999
6 votes
Accepted

Why does the definition of the reward function $r(s, a, s')$ involve the term $p(s' \mid s, a)$?

Expectation of reward after taking action $a$ in state $s$ and ending up in state $s'$ would simply be \begin{equation} r(s, a, s') = \sum_{r \in R} r \cdot p(r|s, a, s') \end{equation} The problem ...
user avatar
  • 2,226
5 votes

What is a time-step in a Markov Decision Process?

In a Markov Decision Process (MDP) model, we define a set of states ($S$), a set of actions ($A$), the rewards ($R$), and the transition probabilities $P(s' \mid s, a)$. The goal is to figure out the ...
user avatar
  • 365
5 votes

How can you represent the state and action spaces for a card game in the case of a variable number of cards and actions?

Instead of having the AI learn what action to take, you can alternatively train it to judge how "good" a position is. In order to determine what move to make, you don't ask the AI "This is the current ...
user avatar
  • 151
5 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 ...
user avatar
  • 33.8k
5 votes
Accepted

Benchmarks for reinforcement learning in discrete MDPs

Although I am not aware of any "benchmark problems" for (discrete) MDPs, I'll comment a bit on possible benchmarks and I will show some benchmarks used to test POMDP algorithms. MDP vs POMDP In ...
user avatar
  • 365
5 votes
Accepted

Why can we take the action $a$ from the next state $s'$ in the max part of the Q-learning update rule, if that action doesn't lead to any reward?

I'm using OpenAI's cartpole environment. First of all, is this environment not Markov? The OpenAI Gym CartPole environment is Markov. Whether or not you know the transition probabilities does not ...
user avatar
  • 23.8k
5 votes
Accepted

Does stochasticity of an environment necessarily mean non-stationarity in MDPs?

Is a stochastic environment necessarily also non-stationary? No. A stochastic environment (i.e. an MDP with a transition model $p(s', r \mid s, a)$) can be stationary (i.e. $p$ does not change over ...
user avatar
  • 33.8k
4 votes
Accepted

What is the relation between a policy which is the solution to a MDP and a policy like $\epsilon$-greedy?

for example, the "greedy policy" always chooses the action with the highest expected return, no matter which state we are in The "no matter which state we are in" there is generally not true; in ...
user avatar
  • 9,379
4 votes

How are the reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ equivalent?

Let $R(s)$ denote a probability distribution over rewards that our agent may get in some MDP as a reward for entering a state $s$. The easiest case is to demonstrate that we can also choose to write ...
user avatar
  • 9,379
4 votes

Can the rewards be stochastic when the transition model is deterministic?

My question is, would $r_1 =r_2$? That's usually up to you as the designer of the system. Usually when you declare that you have "a deterministic environment", you imply that both $s'$ and $r$ are ...
user avatar
  • 23.8k
4 votes

What is a time-step in a Markov Decision Process?

In the reinforcement learning setting, an agent interacts with an environment in (discrete) time steps, which are incremented after the agent takes an action, receives a reward and the "system" (the ...
user avatar
  • 33.8k
4 votes

How can you represent the state and action spaces for a card game in the case of a variable number of cards and actions?

Filling values is totally fine. In the case of image recognition the filling will be the background of the image (examples). For example in Belot you have total of 32 cards, which can be 32 boolean ...
user avatar
4 votes
Accepted

Why am I getting the incorrect value of lambda?

$TD(\lambda)$ return has the following form: \begin{equation} G_t^\lambda = (1 - \lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t:t+n} \end{equation} For you MDP $TD(1)$ looks like this: \begin{align} ...
user avatar
  • 2,226
4 votes
Accepted

Is the state transition matrix known to the agents in a Markov decision processes?

In reinforcement learning (RL), there are some agents that need to know the state transition probabilities, and other agents that do not need to know. In addition, some agents may need to be able to ...
user avatar
  • 23.8k
4 votes
Accepted

What is ergodicity in a Markov Decision Process (MDP)?

In short, the relevant class of a MDPs that guarantees the existence of a unique stationary state distribution for every deterministic stationary policy are unichain MDPs (Puterman 1994, Sect. 8.3). ...
user avatar
  • 381
4 votes
Accepted

Are optimal policies always deterministic, or can there also be optimal policies that are stochastic?

I think the result you are referring to is the one that says that there always exists a deterministic optimal policy for an MDP. This is true. But note that this does not imply that a stochastic ...
user avatar
  • 381
4 votes
Accepted

Reward interpolation between MDPs. Will an optimal policy on both ends stay optimal inside the interval?

I believe the claim is true. Here is my attempt at a proof. Let us consider the optimal infinite horizon value function $V_\alpha^*$ of $\mathcal{M}_\alpha$ at an arbitrary state $s \in S$. The value $...
user avatar
  • 381
4 votes
Accepted

In reinforcement learning, why are policies defined as functions of states and not observations?

Ultimately, a policy must be such that is is possible for an agent to execute it. If the policy depends on the state, the implicit assumption is that the agent has knowledge of the state and can ...
user avatar
  • 381
3 votes

How can you represent the state and action spaces for a card game in the case of a variable number of cards and actions?

Considering your use case, I would not use Deep Learning methods... what is the point? Instead of just winning, good AI is fun to play with. In practice when fine tuning game mechanics, you will want ...
user avatar
  • 278
3 votes
Accepted

Should we feed a greater fraction of terminal states to the value network so that their values are learned first?

The basis of Q-learning is recursive (similar to dynamic programming), where only the absolute value of the terminal state is known. This may be true in some environments. Many environments do not ...
user avatar
  • 23.8k
3 votes

Why can't we apply value iteration when we do not know the reward and transition functions, and how does Q-learning solve this issue?

For normal value iteration, you need to have the model, i.e. the transition probability, denoted by $P(s' \mid s,a)$. With Q-learning, you use the current reward and the already stored Q value: The ...
user avatar
  • 365

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