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.
160
questions
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 [...
- 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 ...
- 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 ...
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 ...
- 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 ...
- 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 ...
- 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 ...
- 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\...
- 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 ...
- 4,035
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.
...
- 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 ...
- 203
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 ...
- 101
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 ...
- 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 ...
- 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 ...
- 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 ...
- 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 ...
- 111
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$. ...
- 153
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? ...
- 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, ...
- 11
-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 ...
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, ...
- 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 ...
- 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 ...
- 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 ...
- 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),\...
- 31
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 $\...
- 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 $...
- 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 ...
- 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$...
- 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$, ...
- 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 ...
- 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) ...
- 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 ...
- 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....
- 3
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 ...
- 133
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 ...
- 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$ ...
- 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 ...
- 339
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 ...
- 339
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 ...
- 205
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_{...
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 ...
- 4,035
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 ...
- 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 \...
- 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 ...
- 103
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 ...
- 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 ...
- 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 ...
- 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 ...
- 75