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
10 views

In a deterministic environment of MDP, what is the way to find the best policy within all policies with different values of discount factor (gamma) [closed]

Any links/web pages/readings to answer the questions are greatly appreciated. Thanks, XOR
  • 1
1 vote
0 answers
34 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 ...
1 vote
1 answer
46 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 ...
  • 123
0 votes
0 answers
22 views

What reward should be selected for transition states to make the agent reach the terminal state (destination) faster? negative, positive, or zero?

Consider the simple environment below, where the gray cells are the terminal states and the agent receives a reward of $-5$ for taking any action in these states. The nonterminal states are $S = \{1, ...
  • 11
1 vote
0 answers
43 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 ...
0 votes
0 answers
24 views

How to formulate Monte Carlo Tree Search in a stochastic environment with a changing action space

Can we efficiently solve a problem in which: the valid actions at any given time are changing the environment is stochastic we have an infinite time horizon using MCTS? To be more specific, I'm ...
0 votes
1 answer
60 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 ...
1 vote
1 answer
51 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. ...
1 vote
0 answers
19 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 $\...
  • 173
0 votes
0 answers
31 views

What is the relationship between state value and action Q function?

I am currently working of reformulation of Dec-POMDPs (where I recast a Dec-POMDP to a continuous state MDP for example). I am trying to prove that the action value (q-function) of the new MDP is ...
0 votes
0 answers
13 views

Control variables and cofounding effects in stochastic programming/,model predictive control/reinforcement learning

How can we be sure that confounding variables/control variables donโ€™t pickup the effect our decisions w.r.t decision variables had on the actual control variable? Since the term control variable ...
1 vote
1 answer
121 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 ...
  • 21
1 vote
1 answer
53 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 ...
  • 340
0 votes
0 answers
12 views

How to partition the belief space of a POMDP using a "granularity" parameters?

as I understand, to a solve a pomdp we transform it into a belief-MDP. The value function for this belief-MDP is proven to be piecewise linear and convex (PWLC) [Smallwood and Sondik, 1973].To apply ...
1 vote
1 answer
130 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
1 answer
48 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 ...
0 votes
0 answers
18 views

Markov decision process how to get the correct policy if targets are reached once among N episodes?

I have implemented an MDP on a network such that an agent starts in a node, takes an action from a set of predefined actions and next node (including current). Some of the nodes would result in ...
2 votes
1 answer
161 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 ...
0 votes
0 answers
31 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 ...
3 votes
0 answers
69 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=...
  • 31
0 votes
0 answers
26 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_*)$ ...
  • 81
0 votes
0 answers
26 views

Exercise 3.21 Sutton Barto: Draw or describe the contours of the optimal action-value function for putting, $q_{*}(s, putter)$, for the golf example

I am doing exercise 3.21 in Sutton and Barto. Here's the exercise: Draw or describe the contours of the optimal action-value function for putting, $q_{*}(s, putter)$, for the golf example. Here's ...
  • 81
2 votes
2 answers
146 views

Does maximizing the value function and maximizing the state-action value function generate the same optimal policy?

In reinforcement learning, we define the optimal policy $\pi^*$ as the policy that maximizes the value of the state: $$ \pi_v^*=\underset{\pi}{\operatorname{argmax}} {V_{\pi}(s)} $$ In Q-learning, we ...
  • 203
4 votes
1 answer
62 views

$E_{\pi}[R_{t+1}|S_t=s,A_t=a] = E[R_{t+1}|S_t=s,A_t=a]$?

I would like to solve the first question of Exercise 3.19 from Sutton and Barto: Exercise 3.19 The value of an action, $q_{\pi}(s, a)$, depends on the expected next reward and the expected sum of the ...
  • 81
1 vote
0 answers
38 views

Determining a policy to play a game of chance

I'm trying to optimize the expected return from a game of chance, but have quickly realized the problem outclasses the introductory AI course I took in college years ago. I would appreciate any ...
user avatar
1 vote
0 answers
45 views

Number of possible joint policies in a Dec-POMDP and the time required to evaluate each one

I was reading a book about Dec-POMDPs and came across this curious result where the author specifies the number of possible joint policies to evaluate and the time needed to evaluate a single joint ...
1 vote
1 answer
71 views

Can the state transition function be dynamic in reinforcement learning?

In general, there are two types of transition functions in reinforcement learning. Mathematically, they are as follows #1: Stochastic state transition function: $$T : S \times A \times S \rightarrow [...
  • 3,391
2 votes
1 answer
166 views

Is it appropriate to represent 'total failure' as an absorbing state?

My understanding is that, in Markov decision processes, absorbing state are states which can transition only to themselves and that these transitions generate rewards of 0. I know that absorbing ...
  • 121
0 votes
1 answer
31 views

Does the policy search work if there is no state to state dependency through actions?

There is a game in which the state comes one after the other without depending on the agent's action. The agent gets a reward for its actions at the end of the game. The goal of the agent is to reach ...
0 votes
1 answer
50 views

Does $S_{t+1}$ denote the future information in Q-learning?

In Q-learning, $Q(S_t,a)$ is updated by the Bellman equation. $Q(S_t,a) = r + \max_{a'}(Q(S_{t+1},a'))$ where $S_{t+1}$ is the future state. Let's say $S$ denotes the stock price, does it mean we are ...
  • 1
0 votes
1 answer
37 views

Does $R_{s}=E[R_{t}|S_{t}=s]$ indicate the reward we might expect on getting on average moving from any other state to $s$?

I'm trying to understand correctly what each "variable" in RL is and I'm not sure about $R_{s}$ the reward function. I used to think that it's the reward we may expect on average after ...
  • 509
0 votes
0 answers
21 views

How are previous values updated when performing value iteration?

I have been trying to understand how you determine the value for each square in a grid world and I have seen/watched a few different examples to try and apply it to my own grid and I find myself ...
  • 1
2 votes
1 answer
293 views

Factors that affect the number of iterations of value iteration

I had an assumption that value iteration will take more iterations to converge if the map size increases/environment's complexity increases. I tried to verify this idea by running value iteration on ...
  • 23
1 vote
1 answer
102 views

Are these two forms of the state value function the same?

Why are there different forms of the value function in reinforcement learning? Sutton & Barto (2nd edition, equation 3.14) define the state value function as follows $$v_{\pi}(s) = \displaystyle\...
  • 175
1 vote
1 answer
120 views

Does the state space of an MDP change in these two examples?

In the classic Atari environments, like that introduced in the original DQN paper, the state space is the set of all possible images that the Atari emulator can produce (or more generally just any RGB ...
4 votes
1 answer
186 views

Are multi agent or self-play environments always automatically POMDPs?

As part of my thesis, I'm working on a zero sum game with RL to train an agent. The game is a real-time game, a derivation of pong, one could imagine playing pong with both sides being foosball rods. ...
  • 105
12 votes
2 answers
1k views

Is there a fundamental difference between an environment being stochastic and being partially observable?

In AI literature, deterministic vs stochastic and being fully-observable vs partially observable are usually considered two distinct properties of the environment. I'm confused about this because what ...
0 votes
0 answers
62 views

Why does the Bandit Slippery Walk environment have complimentary probabilities?

I am learning about Reinforcement learning in the book Grokking Deep Reinforcement Learning. Below are snippets. Below is the description of Bandit Slippery Walk (BSW) Below is the description of two ...
2 votes
1 answer
62 views

Is there a mathematical formalism to deal with a missing reward signal?

Typically, a Reinforcement Learning learning problem is formalized as finding an optimal policy for a Markov Decision Process (MDP). In many real-life situations, however, an agent can only get ...
  • 173
2 votes
1 answer
153 views

Can RL still learn in a scenario where current state and the next state are independant?

I am trying to implement reinforcement learning into my real-world problem. One thing making me hesitant to apply RL is that this real-world problem of mine is unique in a way how every state is ...
  • 55
1 vote
0 answers
149 views

Implementation of MDP in python to determine when to take action clean

I am trying to model the following problem as a Markov decision process. In a steel melting shop of a steel plant, iron pipes are used. These pipes generate rust over time. Adding an anti-rusting ...
  • 111
1 vote
0 answers
62 views

Are there any deep RL algorithms that work well on finite MDPs and non-trivial terminal rewards?

I notice that most Deep Reinforcement Learning (DRL) works focus on Markov Decision Process (MDP) with an infinite time horizon. Are there any algorithms that work well on finite MDP and non-trivial ...
3 votes
1 answer
86 views

In reinforcement learning, why are policies defined as functions of states and not observations?

I am new to RL and I am following Sutton & Barto's book. My doubt is, when we talk about the policy of our agent, we say it is the probability of taking some action $a$ given the state $s$. ...
0 votes
1 answer
37 views

Discard irrelavant states from a MDP

I came across this question about MDP. From the look of it, it seems the full MDP is reducible if the discarded state only have 1 way in and out but is it really so if we change the discounted factor? ...
  • 49
-1 votes
1 answer
501 views

Calculating state-value functions in Markov Decision Process

I am watching David Silver's lectures on RL available on YouTube. My question here is with regard to Lecture 2 (Link to Video). At 1:11:00, I could not understand how he is calculating the state-value ...
3 votes
1 answer
241 views

Is it really hard to learn in a stochastic environment?

I understand that a stochastic environment is one that does not always lead you to the desired state by giving a particular action $a$ (But the probability to change to a not desire state is fixed, ...
  • 282
2 votes
1 answer
62 views

Markov Decision Processes with variable epoch lengths

I am working on modeling a transportation problem as an MDP. Multiple trucks move material from one node to various other nodes in a network. However, the time it takes a truck to travel between any 2 ...
  • 21
2 votes
1 answer
158 views

Is there any inherent assumption of start and goal states in an MDP?

MDP stands for the Markov decision process. It is a 5-length tuple used in reinforcement learning. $$MDP = (S, A, T, R, \pi)$$ $S$ stands for a set of states, also called state space. $A$ stands for a ...
  • 3,391
2 votes
0 answers
61 views

Is it better to model a Contextual Multi-Armed Bandit problem as an MDP with a non-zero discount factor than treating it as it is?

I'd like to ask if it is, generally, better to model a problem that naturally appears as a Contextual Multi-Armed Bandit like Recommender Systems as a Markov Decision Process with a non-zero discount ...
  • 509
3 votes
0 answers
59 views

How to prove Lemma 1.6 in the book "Reinforcement Learning: Theory and Algorithms"

I am trying to prove the following lemma from Reinforcement Learning: Theory and Algorithms on page 8. Lemma 1.6. We have that: $$ \left[(1-\gamma)\left(I-\gamma P^{\pi}\right)^{-1}\right]_{(s, a),\...