Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [markov-decision-process]

For questions related to the concept of Markov decision process (MDP), which is a mathematical framework for modeling decision making in situations where outcomes are partly random and partly under the control of a decision-maker. The concept of MDP is useful for studying optimization problems solved via dynamic programming and reinforcement learning.

209 questions
Filter by
Sorted by
Tagged with
14 views

### Existence of optimal stochastic policy?

I know that in a MDP there always exists a unique optimal deterministic policy. Does a statement like this also exist for optimal stochastic policies? Is there also always a unique optimal stochastic ...
• 101
66 views

### Violation of Markov property

Consider the following cases: a-) In solving an episodic problem we observe that all trajectories from the start state to the goal state pass through a particular state exactly twice. b-) In solving ...
• 813
14 views

### Q-Learning conditions for convergence and ergodicity

Q-learning is guaranteed to convergence if the learning rate satisfies the Robbins-Monro conditions and if every state-action pair is visited infinitely often. Regarding the latter, does it mean that ...
• 153
44 views

### Value iteration in a Grid World Example

I am facing some confusion regarding the calculation of the values for the states in a grid world. Given that this is my grid world, where the there is a reward for going to F of +1, and no other ...
16 views

### Optimality of two policies versus variance of returns from a state

If for an MDP there exist two optimal policies, it may be possible that the variance of their returns are different for a given state. This is correct, right?
• 813
15 views

### Properties of an example environment

Let us consider the following problem. A student is developing a robot that can roll a die. The robot grips and releases the die with an arm that can also twist, and uses two cameras that can see the ...
• 813
28 views

### In Markov Decision Process, how to understand the calculation of the average length of episode?

In the Sec. 13.2 of RL: An Introduction (Sutton & Barto), the concept of average episode length is discussed for both episodic MDP and continuing MDP. In an episodic MDP, the average length of an ...
28 views

### MDP Average Reward independent of Initial State

Asking this question of mine in MathOverflow here since AI StackExchange appears to be a more appropriate place. Consider a Markov Decision Process where the state space $S$ and the action space $A$ ...
• 21
1 vote
21 views

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

Please see slide 32 in the following lecture slides on DP: https://groups.uni-paderborn.de/lea/share/lehre/reinforcementlearning/lecture_slides/built/Lecture03.pdf Let $m$ the size size of action ...
• 813
1 vote
42 views

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

Why do exhaustive search require 14 travel segment evaluations but dynamic programming require 10 for this shortest path problem? I need a clear explanation.
• 813
22 views

### MDP and a given policy and the correctness of the state-value function

Is the following statement correct? "For an MDP and a given policy, the Bellman equation can be used to check the correctness of the state-value function."
• 813
37 views

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

Is the sequence 1-1-2-3-Exit possible in the following Markov reward process? The probability of transitioning from state 1 to itself is 0. Source: https://maelfabien.github.io/rl/RL_2/#markov-process-...
• 813
87 views

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

In chapter 2 of Barto and Sutton's RL book, the four argument probability function $p: S \times R \times S \times A \to [0,1]$ is reduced to three arguments $p: S \times S \times A \to [0,1]$ as ...
49 views

• 183
695 views

### In the Policy Gradient Theorem proof, why is $d^\pi(s) = \sum_{k=0}^{\infty}\gamma^{k}Pr(s_0 \rightarrow s, k, \pi)$ true?

I was reading the original Policy Gradient Paper. I didn't quiet get the last step of the proof for the policy gradient theorem. The proof given in the paper is below: I don't understand how the last ...
• 31
355 views

### What's the relationship between Bayesian RL and POMDPs?

Bayesian RL seems concerned with having uncertainty over the transition function of the environment, while POMDPs try to capture uncertainty over the state one is currently in. However, both end up ...
• 380
1 vote
946 views

### Markov's Decision Process - calculate value in each iteration

I have the following decision tree: I calculated the value of the plan using the following paramenters (given): {𝑆0 → 𝑎1 , 𝑆1 → 𝑎3 , 𝑆2 → 𝑎4 }, Discount factor (𝛾)= 0.2 I used this formula to ...
1 vote
88 views

### How to prove that an action-value function optimal for one problem formulation is also optimal for another?

I want to ask about the intuition/where-to-look/what-to-try if I want to prove that an action value function optimal for a problem is also optimal for another reformulation of that smae problem. For ...
172 views

### Remove already reached targets from the system to enable reaching other targets?

This may be a very fundamental question, but somehow I can't decide. I have a graph and the user can take several actions while traversing it and there are multiple points with rewards. When I execute ...