# Tag Info

## Hot answers tagged markov-decision-process

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

16

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

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

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

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

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

6

Expectation of reward after taking action $a$ in state $s$ and ending up in state $s'$ would simply be $$r(s, a, s') = \sum_{r \in R} r \cdot p(r|s, a, s')$$ 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 ...

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 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 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 affect whether the state has the Markov property. All that matters is that knowing the current state is enough to be determine the next state and reward in ... 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 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 ... 4 TD(\lambda) return has the following form: $$G_t^\lambda = (1 - \lambda) \sum_{n=1}^{\infty} \lambda^{n-1} G_{t:t+n}$$ 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 ... 4 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 time) or non-stationary (p changes over time). Similarly, a deterministic environment, i.e. the probabilities are 1 or 0, can also be either stationary or ... 4 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 V_\alpha^*(s) is the expected sum of discounted rewards under an optimal policy \pi_\alpha^*, i.e., V_\alpha^*(s) = \mathbb{E}_{\rho_\... 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 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 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 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 of imperfect information is one in which you lack knowledge of any of the following: The state of the game (e.g. current market prices). The rewards you will ... 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 I think I may be in position to answer my own question. The Bellman equation (for the optimal policy) for a MDP with r(s,a,s') rewards would look like this:V(s) = \max_a \left\{ \sum_{s'} p(s'|s,a)(r(s,a,s') + \gamma V(s')) \right\} V(s) = \max_a \left\{ \sum_{s'} p(s'|s,a) \cdot r(s,a,s') + \gamma \sum_{s'} p(s'|a,s) \cdot V(s') \right\}  Now, ...

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

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