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.
146
questions
2
votes
1answer
36 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 ...
1
vote
0answers
53 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 ...
0
votes
0answers
29 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 ...
1
vote
0answers
22 views
Reinforcement Learning for Finite Time Horizon and Non-Trivial Terminal Reward
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
1answer
56 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
1answer
29 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? ...
0
votes
0answers
16 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, ...
-1
votes
1answer
49 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 ...
2
votes
1answer
37 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 ...
1
vote
1answer
32 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 ...
0
votes
0answers
11 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 an Markov Decision Process with a non-zero discount ...
2
votes
0answers
43 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),\...
5
votes
0answers
52 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 $\...
1
vote
0answers
14 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 $...
0
votes
0answers
14 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
vote
1answer
67 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$...
2
votes
1answer
42 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$, ...
2
votes
1answer
181 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 ...
0
votes
1answer
99 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) ...
6
votes
1answer
65 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 ...
0
votes
1answer
32 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....
0
votes
1answer
51 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 ...
0
votes
1answer
38 views
Does optimal policy implies deterministic?
Let M be an MDP with two states, A, B, A is the starting state and
you always transit to the final state B using two possible actions.
$A1$ gives you rewards which are normally distributed N(0, 1) and ...
2
votes
0answers
52 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$ ...
5
votes
1answer
279 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 ...
1
vote
0answers
58 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 ...
0
votes
0answers
42 views
Double DQN backpropagation of negative final rewards?
My problem is that in my Double DQN model, negative final rewards are not being backpropagated into action Q-values, and so some Q-values are positive, when they should be negative, and hence ...
7
votes
1answer
443 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 ...
1
vote
1answer
90 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
0answers
56 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 ...
0
votes
1answer
61 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 ...
3
votes
1answer
40 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 \...
0
votes
1answer
90 views
Reinforcement Learning for an environment that is non-markovian
I am a beginner in the field of Reinforcement Learning with only a couple of months of experience being in the field. Soon, I will start working on a project where we want to optimize the production ...
2
votes
1answer
29 views
Is there a way of path reconstruction using only the history of belief state?
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 ...
2
votes
0answers
24 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 ...
2
votes
1answer
152 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 ...
3
votes
1answer
97 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 ...
0
votes
0answers
17 views
What is an appropriate stop criteria for training on a non-stationary environment in reinforcement learning?
I'm currently studying reinforcement learning (RL) and would like to understand non-stationary environments better. So for stationary environments, the Q-values of all state-action pairs converge ...
3
votes
1answer
79 views
Why can we take the action $a$ from the next state $s'$ in the max part of the Q-learning update rule, if that action doesn't lead to any reward?
I'm using OpenAI's cartpole environment. First of all, is this environment not Markov?
Knowing that, my main question concerns Q-learning and off-policy methods:
For me, there is something weird in ...
3
votes
1answer
163 views
How can we find the value function by solving a system of linear equations without knowing the policy?
An MDP is a Markov Reward Process with decisions, it’s an environment in which all states are Markov. This is what we want to solve. An MDP is a tuple $(S, A, P, R, \gamma)$, where $S$ is our state ...
2
votes
0answers
43 views
What trait of a planning problem makes reinforcement learning a well suited solution?
Planning problems have been the first problems studied at the dawn of AI (Shakey the robot). Graph search (e.g. A*) and planning (e.g. GraphPlan) algorithms can be very efficient at generating a plan. ...
1
vote
2answers
98 views
Is there a natural way to define the terminal state from the MDP transition probabilities $p(s',r|s,a)$?
I'm learning the basics of RL and I'm struggling to understand the notion of terminal state in MDPs.
To ask my question straightforwardly: is there a natural way to define the terminal state from the ...
2
votes
1answer
67 views
How can I go from $R(s)$ to $R(s,a)$ in this specific MDP?
I'm trying to implement a research paper, as explained in this other post, here the author of the paper assumed R as a function of both states and actions, while the code (and the MDP) I'm using to ...
4
votes
1answer
67 views
How should I implement the state transition when it is a Gaussian distribution?
I am reading this paper Anxiety, Avoidance and Sequential Evaluation and is confused about the implementation of a specific lab study. Namely, the authors model what is called the Balloon task using a ...
2
votes
0answers
28 views
Does there necessarily exist "dominated actions" in a MDP?
In a Markov Decision Process, is it possible that there exists no "dominated action"?
I define a dominated action the following way:
we say that $(s,a)$ is a dominated action, if $\forall \...
1
vote
1answer
70 views
How can I model a problem as an MDP if the agent does not follow the successive order of states?
In my problem, the agent does not follow the successive order of states, but selects with $\epsilon$-greedy the best pair (state, action) from a priority queue. More specifically, when my agent goes ...
1
vote
0answers
23 views
Understanding example for Improved Policy Iteration for POMDPs
I was going through this paper by Hansen. This paper proposes policy improvement by first converting set of $\alpha$ vectors into finite state controller and then comparing them to obtain improved ...
0
votes
1answer
51 views
When we have multiple traces, do we average over traces or the total number of times we have visited that state?
I am confused about the workings of the first- and every-visit MC.
My first question is, when we have multiple traces, do we average over traces or the total number of times we have visited that state?...
2
votes
1answer
42 views
Why is it useful to define the return as the sum of the rewards from time $t$ onward rather than up to $t$?
Why is it useful to define the return as the sum of the rewards from time $t$ onward rather than up to $t$?
The return for an MDP is usually defined as
$$G_t=R_{t+1}+R_{t+2}+ \dots +R_T$$
Why is this ...
2
votes
0answers
52 views
Can $Q$-learning or SARSA be thought of a Markov Chain?
I might just be overthinking a very simple question but nonetheless the following has been bugging me a lot.
Given an MDP with non-trivial state and action sets, we can implement the SARSA algorithm ...