Skip to main content
2 votes

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$-...
cinch's user avatar
  • 2,277
2 votes
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 ...
cinch's user avatar
  • 2,277
2 votes
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 ...
nbro's user avatar
  • 40.9k
2 votes

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 ...
cinch's user avatar
  • 2,277
2 votes
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.
nbro's user avatar
  • 40.9k
2 votes

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 ...
cinch's user avatar
  • 2,277
2 votes
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 ...
nbro's user avatar
  • 40.9k
2 votes
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 ...
Neil Slater's user avatar
  • 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
Alberto's user avatar
  • 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-...
BoZenKhaa's user avatar
  • 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 ...
Eduardo Pignatelli's user avatar
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, ...
cinch's user avatar
  • 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 ...
foreverska's user avatar
  • 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 ...
foreverska's user avatar
  • 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 ...
maxy's user avatar
  • 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 ...
Alberto's user avatar
  • 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 ...
Jahid Chowdhury Choton's user avatar
1 vote
Accepted

What is the logic in including/not including subscript $\pi$ in in "E" for value functions?

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_{...
cinch's user avatar
  • 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, ...
vl_knd's user avatar
  • 498

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