17

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


12

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 with tweets that are popularized by the community! You can even checkout RL papers specifically here arxiv-sanity: this site updates with popular and new papers ...


7

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 probabilities of transitioning from one state to the other and the probabilities of getting a reward when you take a certain action in a certain state. The policy ...


6

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 the same value in a specific MDP, if for instance you use $R(s, a, s')$ and the value returned only depends on $s$, then $R(s, a, s') = R(s)$. This is not true ...


6

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


5

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 best action to take in each of the states, i.e. the policy $\pi$. Policy To calculate the policy we make use of the Bellman equation: $$V_{i+1}(s)=R(s)+\gamma \...


5

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 state, what move should I make", you iterate through all possible moves, and feed the the resulting state into the AI asking "How good do you think this new ...


5

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


5

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 from the excerpts I've read.


5

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 Markovian Decision Processes (MDPs) the whole state space is known, this means you know all the information for your problem; therefore, you can use them to find ...


5

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 with this is that they do not define probability distribution for rewards separately, they use joint distribution $p(s', r|s, a)$ which represents probability ...


4

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 general, the expected return depends on the state we are in and the action we choose, not just the action. In general, I wouldn't say that a policy is a mapping ...


4

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 this as $R(s, a)$ or $R(s, a, s')$: simply take $\forall a: R(s, a) = R(s)$, or $\forall a \forall s': R(s, a, s') = R(s)$, as also described in Neil's answer. ...


4

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 features. You can set the ones the player has to 1, while the rest are 0. Note that the in most games you'll need more features than the cards in your hand. I.e ...


4

$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} G &= 0.64 (r_0 + r_2 + r_4 + r_5 + r_6) + 0.36(r_1 + r_3 + r_4 + r_5 + r_6)\\ G &\approx 6.164 \end{align} $TD(\lambda)$ looks like this: \begin{...


4

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 sample the results of taking an action somehow, but do not strictly need to have access to the probability matrix. This might be the case if the agent is allowed ...


3

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


3

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 fixed values depending on $(s,a)$. So in your examples, you would expect your observations to also have $r_1 = r_2$ However, it is possible to define a MDP ...


3

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 to analyze the game for churning events. Then it would be nice, if you could show the AI that "Hey, this is messed up, could you come up with a nice way of ...


3

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 have a terminal state, they are continuous. Your statement may be true for instance in a board game environment where the goal is to win, but it is false for e.g. ...


3

Background The Markov Decision Process is an extension of Andrey Markov's action sequence that visualize action-result sequence possibilities as a directed acyclic graph. One path through the acyclic graph, if it satisfies the Markov Property is called a Markov Chain. The Markov Property requires that the probability distribution of future states at any ...


3

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 relation between the value function $V(s)$ and the $Q$ function $Q(s, a)$ is that the $V(s)$ function is simply the value of the action $a$, such that $Q(s, a)$ ...


3

Hi Hunnam and welcome to our community! By definition, every state in RL has Markov property, which means that the future state depends only on the current state, not the past states. No this is not exactly correct. We can use RL to solve problems with the Markov Property exactly because the current state is a sufficient statistic of the future. In ...


3

Lot of real tasks are in reality not markovian, but it doesn't mean you can't try to train an agent on these tasks. It's like saying "we assume variable x to be normally distributed", you just assume that you can condition the probability distributions on the present state of the environment hoping that the agent will learn a good policy. In fact for most ...


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

The value of a state depends on the policy that you use, so I'll make the assumption here that you're talking about value using the optimal policy. According to the optimal policy, the agent would choose to stay in the square (1,1) every time, but since it has a 0.8 probability of actually staying (and 0.2 probability of dying), we can compute the value of ...


3

You would still be picking a single action. Your action space is now $\mathcal{A} = \mathcal{O} \times \mathcal{I}$ where I've chosen $\mathcal{O}$ to be the set of possible orders from your problem and $\mathcal{I}$ to be the set of possible items. Provided both of these sets are finite, then you should still be able to approach this problem with DQN. ...


3

Suppose you learned your action-value function perfectly. Recall that the action-value function measures the expected return after taking a given action in a given state. Now, the goal when solving an MDP is to find a policy that maximizes expected returns. Suppose you're in state $s$. According to your action-value function, let's say actions $a$ maximizes ...


3

It wouldn't make sense to define the return as you propose, from time 0 to $t$. Once we are in a state at time $t$ we don't care what the returns have been, rather what they will be in the future, thus returns are defined as the total sum of discounted rewards from the current time step onwards. This allows the agent to make decisions about which actions to ...


2

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 environment and the agent) moves to a new state. More precisely, at time step $t=0$ (the first time step), the environment (including the agent) is in some ...


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