# Tag Info

11

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

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

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

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

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

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

For a Markov Decision Process (MDP) a model which are the states (S), actions (A), rewards (R), and transition probabilites P(s'|s,a). The goal is to obtain the best action to do in each of the states, i.e. the policy π. Policy To calculate the policy we make use of the Bellman equation: When starting to calculate the values we can simply start with: ...

2

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

2

$O(a, s', z) = \mathbb{P}(z \mid a, s')$ is a conditional probability distribution, so it always needs to sum up to $1$. You should interpret $O(a, s', z)$ as the probability of observation $z$, given that the agent took action $a$ and landed in state $s'$. $O(a, s', z)$ is thus not a joint distribution, even though the notation $O(a, s', z)$ might suggest ...

2

Is it just about final states? So for $s \in S$ when S is not final? You are thinking the right way, but to represent what you mean you don't need to write out "when $s$ is not final" - although that would be fine (and is used in some places), there is a more concise way of saying that given to you by the book. As this is a formal exercise from the book, ...

2

When the next state selection is not driven by any meaningful dynamics i.e. it is independent of starting state $s$ and action taken $a$, but the rewards received do depend somehow on the $s$ and $a$, then the MDP you describe also fits with something called a Contextual Bandit Problem where there is no control over state due to action choice, and thus no ...

2

Convergence guarantees for basic RL algorithms like policy gradient / actor-critic methods make no assumptions about the dynamics of the MDP. So, theoretically, you don't need to change much. Practically, when the number of possible trajectories from any given state is so high, the return from each state will have high variance. This means you'll have to ...

2

Your understanding is right! Using a probabilistic transition function allows the model to explore a bigger search space before making a decision. One of the most important use cases of MDP is in POS tagging in NLP using a Hidden Markov Model. In case of a deterministic model, search space is limited by the number of transitions and hence at each step, a ...

2

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

2

This question seems to be addressed directly in slides 29-31 of the deck you linked to in the comment under your question. The basic idea is: Assume you have a complete model of the MDP (transitions, rewards, etc.). For any given state, we have the assumption that the state's true value is reflected by: V(s) = r + \gamma \arg\max_{a \in A}\sum_{s' \in S}...

2

The good news is that: Your MDP appears valid, with well-defined states, actions. It has state transition and reward functions (which you have implemented as matrices). There is nothing else to add, it's a full MDP. You could use this MDP to evaluate a policy, using a variety of reinforcement learning (RL) methods suitable for finite discrete MDPS. For ...

2

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

2

The reward function can be a function of the current state, current action, and next state: $R(s_t, a_t, s_{t+1})$. It's valid to use the Bellman operator in this setting because it's still a contraction and will yield the optimal value function. NOTE: I'm assuming that you will be solving the MDP with the Bellman equation.

2

Dealing with a Non-Markovian process is unusual in Reinforcement Learning. Although some explicit attempts have been made, the most common approach when confronted with a non-Markovian environment is to try and make the agent's representation of it Markovian. After reducing Agent's model of the dynamics to a Markovian process, rewards are assigned from the ...

2

Although you can frame your problem as a bandit problem or RL, it has other workable interpretations. Critical information from your comments is that: Total reward is not a simple sum of all the results from 66 different machines. There are interactions between machines. Total reward is deterministic. This looks like a problem in combinatorial optimisation....

2

So does that mean, that the input of the first hidden layer was simply the state and the input of the second hidden layer the output of the first hidden layer concatenated with the actions? Yes. Why would you do that? To have the first layer focus on learning the state value independent of the selected action? How would that help? Neural networks hidden ...

1

If a policy is fixed, it is said that an MDP becomes an MRP. I would change the phrasing slightly here, to: If a policy is fixed, an MDP can be accurately modeled as an MRP. Why is this so? Aren't the transitions and rewards still parameterized by the action and current state? In other words, aren't the transition and reward matrices still cubes? The ...

1

Welcome to AI.SE @Francis Chang! This is actually an implementation choice, and will depend on how you chose to represent the agent's model of the function that maps from states to actions. If you explicitly represent the entire state space, as you might chose to do with simple benchmark problems that you solve by directly solving an MDP with something ...

1

First thing to know is that, in this case, values for the gridworld in new iteration are completely calculated with respect to the old values from the previous iteration. Value of $0.78$ is got like this: $0.9 \cdot (0.8 \cdot 1 + 0.1 \cdot 0.72 + 0.1 \cdot 0) = 0.7848 \approx 0.78$ term $0.8 \cdot 1$ is for going to the right with probability of $0.8$ ...

1

This is a consequence of the Markovian assumption, which underpins all of RL. The Markovian assumption says that it doesn't matter how we reached a given state, only that we reached it, when deciding how likely it is that we move to subsequent states. This naturally implies that our choice of actions must also depend only on the current state. You are ...

1

To model the problem through RL, it is possible to discretize time horizon into very short time interval (for example 5 minutes as a stage) such that in each time interval, just a single customer enter to our system. On the other hand, it is possible that stages are defined as the time when a customer enters our system. 1) Is the second ...

1

Question 1. Are the states $s'$ drawn from a from a joint probability distribution $P_{sa}$? In other words, if you are in an initial state $s$, take an action $\pi(s)$, then $s'$ is the random state you would end up in according to the probability distribution $P_{sa}$? This is tricky, because you don't show a definition of $P_{sa}$. My first thought ...

1

The problem which you want to solve is Reinforcement Learning with Partially Observable Markov Decision Process. I recommend you taking a look at papers which work in this formalism. For example, papers related to dota bot created by OpenAI. You can start here: https://openai.com/five/

1

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