# Tag Info

### MDP Average Reward independent of Initial State

In the infinite horizon MDP case, your so called optimal average (1-step) reward metric can be proved to be independent of any starting state $s_0$ for any policy with exploration such as $\epsilon$-...
• 2,277
Accepted

### Why are there up to $m^2$ action values when we consider the complexity of DP based on $q(x,u)$?

To fully understand generically the transition dynamics from state $x$ to state $x′$ in terms of action values without state values involvement, we need to evaluate all possible combinations of ...
• 2,277
Accepted

### Why do exhaustive search require 14 travel segment evaluations but dynamic programming require 10 for this shortest path problem?

Like it's explained in the image's caption, DP techniques are based on the idea that you can reuse the solution to subproblems, so it assumes that you can break down the original problem into ...
• 40.9k

### Why do exhaustive search require 14 travel segment evaluations but dynamic programming require 10 for this shortest path problem?

Exhaustive search is just trial and error for the specified problem which has a fixed start node X and a fixed end node Y, thus every possible travel route from X to Y has to be evaluated ...
• 2,277
Accepted

### Is the sequence 1-1-2-3-Exit possible in the following Markov reward process?

No, it's not possible, and you correctly explained why.
• 40.9k

### If $p(s'|s,a) = 0$, would the reward the reward $r(s,a,s')$ be infinite?

You've correctly figured out the most part of your confusion. The only thing I want to add is that by the finite MDP definition here it's certainly possible $p(s'|s,a)=0$ for some $s',s$. The reason ...
• 2,277
Accepted

### Is there any example of a Markov Decision Process (MDP) with infinite number of states?

Many real-world problems have an infinite number of states, but, in practice, digital computers cannot represent an infinite number of states or numbers anyway, so you will always need to discretize ...
• 40.9k
Accepted

### MDP to model finding an optimal sequence of actions with no other state data

I'm not sure how to model this as an MDP. You have defined a fixed set of actions, and I think from your statements that the environment is deterministic (same sequence of actions from start state ...
• 32.7k
1 vote
Accepted

### Are there problems where the optimal policy is stochastic?

Sutton and Barto give an example of an MDP where the optimal stochastic policy strictly dominates the best deterministic one, should answer all your questions
• 2,273
1 vote

### Relation between discounted MDP and stochastic shortest path problems in RL

This is discussed in [1], where the authors provide the following proposition: If $FH$ is the class of finite-horizon MDPs, $IFH$ the class of infinite-horizon MDPs and $SSP$ are stochastic shortest-...
• 113
1 vote

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

As already explained by others, the policy accounts for the agent's decisions, which are not set by the enviornment. The only requirement of an MDP is to define a space of possible policies from which ...
1 vote
Accepted

### When is it non-Markovian?

Your observation about the possibility of n being infinite makes sense. If an environment requires an infinite unbounded history of states to make decisions, it is considered non-Markovian. However, ...
• 2,277
1 vote

### How to properly model the MDP of a weighted graph with the constraint of only visiting each vertex once (and not get stuck in infinite loops)?

Many environments are non-Markovian. Sometimes based on the perception of the agent a Markovian environment becomes non-Markovian (woods101 with perception aliasing). If the model assumes a Markovian ...
• 1,298
1 vote

### Can Q-learning rewards and next states be non-deterministic?

There's a lot being asked here and I don't know that I'm tracking well enough to comment on this formulation. But I will try to clarify some RL theory and answer the title question. If the transition ...
• 1,298
1 vote
Accepted

### UCB, Thompson sampling etc seems myopic/greedy for bandits?

The (binary) multi-armed bandit actually is a MDP with one state and $K$ actions. So your suggestion boils down to meta-learning: Find the parameters of one MDP that can solve another. Let's go with ...
• 233
1 vote

### Why is R(s) more restrictive than R(s, a) in an MDP?

you have in front of you 10 slot machines you can play with any of them, and each of them have a specific winrate (reward function) the only state of this MDP is the initial state, the one where you ...
• 2,273
1 vote
Accepted

### If $p(s'|s,a) = 0$, would the reward the reward $r(s,a,s')$ be infinite?

Ok, so I was able to find the answer to this question by myself. So I'm sharing it with everyone. By the law of non-exclusive events, $P(A|B) = \frac{P(A,B)}{P(B)}$ where $P(B) > 0$. This can also ...
1 vote
Accepted

Your second equation is defined on page 78 and in the same page there's a step on the lower part of derivations contains the answer to your confusion. $q_{\pi}(s, {\pi'}(s)) \\= E[R_{t+1} + \gamma v_{... • 2,277 1 vote ### What is the logic in including/not including subscript$\pi\$ in in "E" for value functions?

The subscript just indicates over which variable the expectation is taken. For consistency it can be included everywhere. Sometimes, when the variable over which the expectation is taken is obvious, ...
• 498

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