Last call to make your voice heard! Our 2022 Developer Survey closes in less than a week. Take 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
1 vote
1 answer
27 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 [...
user avatar
  • 3,059
2 votes
1 answer
148 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 ...
user avatar
  • 121
0 votes
1 answer
27 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 ...
user avatar
0 votes
1 answer
42 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 ...
user avatar
  • 1
0 votes
1 answer
31 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 ...
user avatar
  • 489
0 votes
0 answers
10 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 ...
user avatar
  • 1
2 votes
1 answer
59 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 ...
user avatar
  • 23
1 vote
1 answer
74 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\...
user avatar
  • 175
1 vote
1 answer
66 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 ...
user avatar
3 votes
1 answer
109 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. ...
user avatar
  • 85
10 votes
2 answers
815 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 ...
user avatar
0 votes
0 answers
32 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 ...
user avatar
2 votes
1 answer
51 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 ...
user avatar
  • 163
2 votes
1 answer
53 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 ...
user avatar
  • 45
1 vote
0 answers
93 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 ...
user avatar
  • 111
0 votes
0 answers
40 views

Doubt in calculating the optimal costs and value after n steps of a MDP problem

MDP problem - A server requires information from a sensor. The server would like the information to be fresh. However, there is a cost to querying information from the sensor. Specifically, the state ...
user avatar
  • 23
1 vote
0 answers
43 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 ...
user avatar
3 votes
1 answer
75 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$. ...
user avatar
0 votes
1 answer
32 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? ...
user avatar
  • 49
0 votes
0 answers
32 views

How does the Markov assumption hold true for episodic task?

The Markov assumption assumes that the current state is sufficient for taking the next action. Consider an episodic task, where the RL agent is trying to learn to play the game of tic-tac-toe. Here, ...
user avatar
-1 votes
1 answer
177 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 ...
user avatar
3 votes
1 answer
152 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, ...
user avatar
  • 282
2 votes
1 answer
45 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 ...
user avatar
  • 21
2 votes
1 answer
78 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 ...
user avatar
  • 3,059
2 votes
0 answers
45 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 ...
user avatar
  • 489
3 votes
0 answers
48 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),\...
user avatar
5 votes
0 answers
68 views

Proof that there always exists a dominating policy in an MDP

I think that it is common knowledge that for any infinite horizon discounted MDP $(S, A, P, r, \gamma)$, there always exists a dominating policy $\pi$, i.e. a policy $\pi$ such that for all policies $\...
user avatar
  • 175
1 vote
0 answers
23 views

What is the sample complexity of Monte Carlo Exploring Starts in RL?

We can use a model-free Monte Carlo approach to solving an MDP $(S,A,R,P,\gamma)$ with transition dynamics $P$ unknown by estimating Q-values by rolling out trajectories starting from random states $...
user avatar
  • 203
0 votes
0 answers
22 views

MDP - policy iteration convergence proof

I'm currently taking an Intro to AI course, and we've learned about MDP's and specifically about policy iteration. When we talked about the convergence of the policy iteration, it was mentioned that ...
user avatar
  • 1
1 vote
1 answer
70 views

In addition to the reward function, which other functions do I need to implement Q-learning?

In general, $Q$ function is defined as $$Q : S \times A \rightarrow \mathbb{R}$$ $$Q(s_t,a_t) = Q(s_t,a_t) + \alpha[r_{t+1} + \gamma \max\limits_{a} Q(s_{t+1},a) - Q(s_t,a_t)] $$ $\alpha$ and $\gamma$...
user avatar
  • 187
3 votes
1 answer
189 views

Is the Bandit Problem an MDP?

I've read Sutton and Barto's introductory RL book. They define a policy as a mapping from states to probabilities of selecting each possible action. If the agent is following policy $\pi$ at time $t$, ...
user avatar
  • 203
2 votes
1 answer
746 views

What is the difference between terminal state, nonterminal states and normal states?

In Sutton & Barto's Reinforcement Learning: An Introduction, page 54, the authors define the terminal state as following: Each episode ends in a special state called the terminal state But the ...
user avatar
  • 489
0 votes
1 answer
101 views

How do we get the value of this state of an MDP, at time-step $h-2$, using dynamic programming?

I am trying to understand the problem below, represented as an MDP with four states (PU, PF, RU, and RF) and two actions (AS). Let's consider V(RF), the value of the state RF. At time-step $h$, V(RF) ...
user avatar
  • 61
6 votes
1 answer
75 views

Reward interpolation between MDPs. Will an optimal policy on both ends stay optimal inside the interval?

Say I've got two Markov Decision Processes (MDPs): $$\mathcal{M_0} = (\mathcal{S}, \mathcal{A}, P, R_0),\quad\text{and}\quad\mathcal{M}_1 = (\mathcal{S}, \mathcal{A}, P, R_1)$$ Both have the same set ...
user avatar
  • 1,773
0 votes
1 answer
50 views

Converging to a wrong optimal policy if the agent is given more choices

I am a bit new to Reinforcement learning. So, I am extremely sorry if I am asking something obvious. I have written a small piece of code to find the optimal policy for a 5x5 grid problem. Scenario 1....
user avatar
0 votes
1 answer
67 views

What would happen to an agent trained using Markov Decision Process if the goal node changes?

I was reading up a paper that did routing based on an MDP, and I was wondering because, in routing, there is a sender node and a receiver node, so if the receiver node changes (sending a message to ...
user avatar
0 votes
1 answer
152 views

Are optimal policies always deterministic, or can there also be optimal policies that are stochastic?

Let $M$ be an MDP with two states, $A$ and $B$, where $A$ is the starting state, and you always transit to the final state $B$ using two possible actions. $A_1$ gives you rewards that are normally ...
user avatar
  • 35
2 votes
0 answers
82 views

Is there any reasonable notion of regret for infinite horizon discounted MDPs?

I am thinking about episodic MDPs. Usually, in episodic MDPs, it seems that we have a finite fixed horizon per episode and no discount factor. Then, a very intuitive notion of regret after $T$ ...
user avatar
  • 287
5 votes
1 answer
482 views

Does the policy iteration convergence hold for finite-horizon MDP?

Most RL books (Sutton & Barto, Bertsekas, etc.) talk about policy iteration for infinite-horizon MDPs. Does the policy iteration convergence hold for finite-horizon MDP? If yes, how can we derive ...
user avatar
2 votes
1 answer
79 views

Relation between discounted MDP and stochastic shortest path problems in RL

I have been reading about discounted MDPs and Stochastic Shortest Path (SSP). I recently came to know (from a friend) that every discounted MDP can be converted to an equivalent SSP but not the other ...
user avatar
8 votes
1 answer
1k views

What is ergodicity in a Markov Decision Process (MDP)?

I have read about the concept of ergodicity on the safe RL paper by Moldovan (section 3.2) and the RL book by Sutton (chapter 10.3, 2nd paragraph). The first one says that "a belief over MDPs is ...
user avatar
1 vote
1 answer
200 views

What is the difference between environment states and agent states in terms of Markov property?

I'm going through the David Silver RL course on YouTube. He talks about environment internal state $S^e_t$, and agent internal state $S^a_t$. We know that state $s$ is Markov if $$\mathbb{P}\{S_t=s|S_{...
user avatar
3 votes
0 answers
116 views

Why do we discount the state distribution?

In Reinforcement Learning, it is common to use a discount factor $\gamma$ to give less importance to future rewards when calculating the returns. I have also seen mention of discounted state ...
user avatar
0 votes
1 answer
72 views

Given a sequence of states followed by the agent, is it possible to find the Q-value for a state-action pair not in this sequence?

Assume you are given a sequence of states followed by the agent, generated by a random policy, $[s_0, s_1, s_2, \dots, s_n]$. Furthermore, assume the MDP is fully observable and time is discrete. Is ...
user avatar
  • 1
3 votes
1 answer
62 views

How is $v_*(s) = \max_{\pi} v_\pi(s)$ also applicable in the case of stochastic policies?

I am reading Sutton & Bartos's Book "Introduction to reinforcement learning". In this book, the defined the optimal value function as: $$v_*(s) = \max_{\pi} v_\pi(s),$$ for all $s \in \...
user avatar
  • 33
0 votes
2 answers
236 views

Reinforcement Learning for an environment that is non-markovian [closed]

I will start working on a project where we want to optimize the production of a chemical unit through reinforcement learning approach. From the SME's, we already obtained a simulator code that can ...
user avatar
2 votes
1 answer
47 views

Is there a way of path reconstruction using only the history of belief states?

Given a history of belief states, is there a common method that backtracks the most likely path of ending up in the current belief state? I have a Markov model which calculates belief states after ...
user avatar
  • 435
2 votes
0 answers
38 views

Are there any known disadvantages of implementing vanilla Q-learning on a discretized-state space environment?

For an RL problem on a continuous state space, the states could be discretized into buckets and these buckets used in implementing the Q-table. I see that is what is done here. However, according to ...
user avatar
  • 75
2 votes
1 answer
352 views

What is a good convergence criterion for Q-learning in a stochastic environment?

I have a stochastic environment and I'm implementing a Q-table for the learning that happens on the environment. The code is shown below. In short, there are ten states (0, 1, 2,...,9), and three ...
user avatar
  • 75
3 votes
1 answer
165 views

Does stochasticity of an environment necessarily mean non-stationarity in MDPs?

Is a stochastic environment necessarily also non-stationary? To elaborate, consider a two-state environment ($s_1$ and $s_2$), with two actions $a_1$ and $a_2$. In $s_1$, taking action $a_1$ has a ...
user avatar
  • 75