Skip to main content
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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
9 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 ...
craaaft's user avatar
  • 101
-1 votes
1 answer
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 ...
DSPinfinity's user avatar
0 votes
0 answers
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 ...
Simon's user avatar
  • 153
0 votes
1 answer
43 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 ...
newbieCoder's user avatar
0 votes
1 answer
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?
DSPinfinity's user avatar
0 votes
0 answers
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 ...
DSPinfinity's user avatar
0 votes
0 answers
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 ...
Yancy Pan's user avatar
2 votes
1 answer
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$ ...
Euclid's user avatar
  • 21
1 vote
1 answer
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 ...
DSPinfinity's user avatar
1 vote
2 answers
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.
DSPinfinity's user avatar
0 votes
1 answer
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."
DSPinfinity's user avatar
0 votes
1 answer
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-...
DSPinfinity's user avatar
2 votes
2 answers
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 ...
Jahid Chowdhury Choton's user avatar
0 votes
2 answers
49 views

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

Here are two relations for value functions: Eq.1: $v_{\pi}(s)=E_{\pi}[q_{\pi}(S_t, A_t)|S_t=s]$ Eq.1: $q_{\pi}(s,a)=E[R_{t+1}+\gamma v_{\pi}(S_{t+1})|S_t=s, A_t=a]$ Question: Why is there subscript $\...
DSPinfinity's user avatar
0 votes
0 answers
25 views

What does the term "expected leaf node" in this exercise from Sutton-Barto mean?

What does the term "expected leaf node" in the Exercise below from Sutton-Barto mean?
DSPinfinity's user avatar
-1 votes
1 answer
93 views

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

I was learning fundamentals of reinforcement learning from various sources like coursera, Udacity, ...
Bhavesh Achhada's user avatar
1 vote
1 answer
58 views

When is it non-Markovian?

Several months ago, I was writing for class. I claimed an environment was non-Markovian because it would take several states to de-alias some positions in the grid world. I was corrected that it was ...
foreverska's user avatar
  • 1,288
1 vote
1 answer
35 views

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)?

I'm trying to model a MDP to traverse a complete weighted graph (i.e. all vertex are connected). The states, and also the actions (i.e. S=A), are the vertex of the weighted graph. The transition ...
Cristian García Romero's user avatar
1 vote
0 answers
36 views

Solving MDP as linear program: why minimize the sum of the states' values?

This is a follow-up question to the answer to How can we use linear programming to solve an MDP? Quick recap: the $max$ operators that appear in the Bellman optimality equations can be turned into a ...
Celelibi's user avatar
  • 111
0 votes
1 answer
162 views

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

I am working in a team to develop a Q-learning based approach for hyperparameter tuning. I have a disagreement with one of my teammates on how they defined this problem. They defined it as follows: ...
Ahmed Mokhtar's user avatar
1 vote
0 answers
66 views

When can we unnest the minimizations/recursions in an value function(bellman optimality equation)?

When reading the following paper(page 4): An Approximate Dynamic Programming Approach for Dual Stochastic Model Predictive Control I could see that they were able to unnest the minimization's in the ...
richard baws's user avatar
0 votes
0 answers
40 views

Optimal decision with continuous, stochastic signals and rewards

I am performing a task, where I have to decide which projects to pursue at a given point in time, where the projects have different horizons of 30 minutes. At a given point in time, forecasts are made ...
Mathman's user avatar
1 vote
0 answers
21 views

How can I prove that early termination in an MDP state is valid?

I have an MDP $M$ with transition function $p$, states $S$ and a state $s^0 \in S$. $s^0$ has the property that both the most optimistic trajectory (highest expected reward) and the most pessimistic ...
corazza's user avatar
  • 111
1 vote
0 answers
66 views

Is this a bandit problem or a MDP?

I am trying to understand if this problem can be casted both as a bandit problem as well as an MDP. Lets assume that we are trying to optimize sales $y_t$ based on investments $x_{1, t}, x_{2, t}$ ...
hugh's user avatar
  • 53
2 votes
1 answer
72 views

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

When considering multi-armed bandits in different formats, UCB, $\epsilon$-greedy, thompson sampling etc seems so greedy/myopic in the sense that it solely considers reward for the current timestep. ...
hugh's user avatar
  • 53
0 votes
1 answer
59 views

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

I am quite new to RL. I would like to know why a state-dependent reward function R(s) is more restrictive than a state-action-dependent reward function R(s, a)? And why is it that a policy can be ...
TicTacToemat's user avatar
0 votes
0 answers
46 views

How to decide on size of state space?

I'm in a reinforcement learning class and we're working on a dice game problem where you profit the number rolled for certain digits and lose all your money on certain other digits. You can choose to ...
faangorn's user avatar
2 votes
1 answer
184 views

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

I would like to build an RL agent who's objective is to find an N length sequence of actions to a reward where N is not known and the states are indistinguishable from each other (at least for it's ...
foreverska's user avatar
  • 1,288
0 votes
0 answers
27 views

If the agent is at the same state but at different times and receives a different reward, wouldn't this be violating somehow the MDP assumption?

I've been trying to train an agent, I've received and read suggestions to improve its speed to reach the goal. The suggestion is to use a time penalty, for example, adding $-0.1$ to the reward each ...
Andrea Carolina Mora Lopez's user avatar
1 vote
1 answer
55 views

How is the Markov property of a general state-space model derived?

Below is the derivation for the Markov property of a general state-space model. The red part is not clear. Could someone please explain the steps in the sequential derivation for the red part?
DSPinfinity's user avatar
4 votes
1 answer
96 views

Could you explain these 2 steps of the derivation of the Bellman equation as a recursive equation in Sutton & Barto?

I am reading the Sutton & Barto (2018) RL textbook. On page 59, it derives the recursive property of the state-value function as below. Could you explain the steps of third and fourth equality? ...
tesio's user avatar
  • 205
1 vote
0 answers
41 views

Can we use Low rank approximation in Markov decision process problem?

I am newbie in MDP.I have started reading Ronald Howard Dynamic Programming and MDP book as well as Sutton and Barto An Introduction to Reinforcement Learning. To my understanding MDP is a model based ...
Homer Jay Simpson's user avatar
1 vote
1 answer
216 views

How can I find an upper bound on the number of iterations required to have less than $\varepsilon$ difference in the value of state?

I learned about the Value Iteration algorithm which can help find an optimal policy and values of an MDP with state rewards: $$V_0(s)=R(s)$$ $$V_{t}(s)=R(s)+\gamma\cdot\underset{a}{max}\underset{s'}{\...
Daniel's user avatar
  • 131
0 votes
0 answers
391 views

Convergence of Value Iteration for Discount factor of 1

Given this pseudo code for value iteration: In the case of gamma=1, under what conditions on the MDP will we still be able to find the optimal policy?
Toffe1369's user avatar
2 votes
1 answer
718 views

Should DQN/PPO be used for state spaces that are not that large?

I'm interested in trying out Q-learning to solve a problem where I already have a simulation of the environment that can run at about 100,000 fps or steps/sec. Its also continuous with no terminal ...
gameveloster's user avatar
0 votes
0 answers
18 views

Does fixing an action in the state transition function of an MDP yield a transition matrix?

I stumbled across this seemingly elementary question while studying the theory of Markov Decision Processes. Suppose $\mathcal{M} = (\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R})$ is an MDP and ...
Othman El Hammouchi's user avatar
1 vote
0 answers
45 views

Would the optimal policy remain same, if I replace R with V*?

In the context of RL, say I'm performing Value Iteration on a reward function R1. And the converged optimal policy is P1 and values are V1. Then, let's say I set rewards to be R2=V1 and perform value ...
famishedrover's user avatar
2 votes
1 answer
188 views

What is the difference between these two versions of the Bellman equation?

The first version is the one I am most familiar with: $$V_\pi(s) = \sum_{a}^{}\pi(a|s) \sum_{s'}^{}T(s, a, s')[R(s, a, s') + \gamma V_\pi(s')]$$ where $T(s, a, s')$ represents the probability of ...
Nova's user avatar
  • 133
1 vote
0 answers
290 views

MDP with a non-markovian reward function?

I have set up a RL environment and it converges to a decent solution when using a reward function: $R(s_t,a_t) = fenv(s_t, a_t)$ , where $fenv$ is the environment dynamics. Now, i want to change the ...
StarDust_08's user avatar
0 votes
1 answer
968 views

How can we approximate infinite horizon MDP with finite horizon MDP in the context of reinforcement learning?

For a given value of "discount factor" (and reward values' range) in fixed finite horizon markov decision process (MDP), upto how many episodes we have to extend this MDP so that we can ...
Engr. Moiz Ahmad's user avatar
1 vote
1 answer
180 views

How to correctly evaluate the state value of this simple markov decision process?

For some contexts, I'm working on a c# library for reinforcement learning. I implemented two methods to evaluate a state value function, namely the TD(0) method and the Monte Carlo first visit method. ...
nathan raynal's user avatar
1 vote
0 answers
45 views

How to compare different trajecories in a Markov Decision Process

I realize that my question is a bit fuzzy and I am sorry for that. If needed, I will try to make it more rigorous and precice. Let $\mathcal{M}$ be a Markov Decision Process, with state space $\...
Onil90's user avatar
  • 183
2 votes
1 answer
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 ...
Fady's user avatar
  • 31
2 votes
1 answer
354 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 ...
mdc's user avatar
  • 380
1 vote
1 answer
945 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 ...
stuckincode's user avatar
1 vote
1 answer
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 ...
Souhaielrmx's user avatar
2 votes
1 answer
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 ...
Ferda-Ozdemir-Sonmez's user avatar
0 votes
0 answers
56 views

How to represent the state and action space when modeling card game Love Letter using Markov Decision Process

Now my task is to use model checking to find a best strategy for card game Love Letter, and I need to model the game using Markov Decison Process first. I have done a lot of resaerch and I decided to ...
jiaxin886's user avatar
4 votes
0 answers
186 views

What is the correct interpretation of the discount factor in MDPs?

In infinite-horizon MDPs one can consider the expected discounted return from a distribution of start states as the objective[^1]. i.e. $\mathbb{E}[V^{\pi}(S_0)] = \mathbb{E}[G_0] = \mathbb{E}[\sum_{t=...
Skander's user avatar
  • 41
0 votes
0 answers
35 views

Rewrite the four Bellman equations for the four value functions $(v_{\pi},v_*,q_{\pi},q_*)$ in terms of $p$ (3.4) and $r$ (3.5) [duplicate]

I have done exercise 3.29 from Sutton and Barto and I'd like to check if it's correct. Here's the exercise: Rewrite the four Bellman equations for the four value functions $(v_{\pi},v_*,q_{\pi},q_*)$ ...
user's user avatar
  • 145

1
2 3 4 5