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.
137
questions
2
votes
0answers
32 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
44 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
13 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
62 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
36 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
56 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
94 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
63 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
29 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
36 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
27 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
40 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
204 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
57 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
36 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 ...
6
votes
1answer
257 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 ...
0
votes
1answer
58 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
50 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
41 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
39 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
77 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
24 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
109 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
90 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
11 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
75 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
126 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
39 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
86 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
64 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
63 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
27 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
65 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
48 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
41 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
51 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 ...
4
votes
1answer
225 views
Is the state transition matrix known to the agents in a Markov decision processes?
The question is more or less in the title.
A Markov decision process consists of a state space, a set of actions, the transition probabilities and the reward function. If I now take an agent's point ...
1
vote
0answers
12 views
Relation between a value function of an MDP and a value function of the corresponding latent MDP
In paper "DeepMDP: Learning Continuous Latent Space Models for Representation Learning", Gelada et al. state in the beginning of section 2.4
The degree to which a value function of $\bar{\...
0
votes
0answers
12 views
What are some good use cases of Inference in Hybrid Domains (Logical + Continuous)?
So this question pertains to Statistical Relational Learning. Specifically in domains where you have a Knowledge base with probabilistic facts, you may think something like a Markov Logic Networks (...
0
votes
0answers
54 views
Does Multi-Agent Deep Deterministic Policy Gradient also work with discrete action spaces?
I would like to ask if Multi-Agent Deep Deterministic Policy Gradient (MADDPG) works fine with discrete action space.
DDPG works only with continuous action space, but I have read that MADDPG can also ...
1
vote
1answer
105 views
Bellman optimality equation in semi Markov decision process
I wrote a Python program for a simple inventory control problem where decision epochs are equally divided (every morning) and there is no lead time for orders (the time between submitting an order ...
4
votes
1answer
127 views
Can you convert a MDP problem to a Contextual Multi-Arm Bandits problem?
I'm trying to get a better understanding of Multi-Arm Bandits, Contextual Multi-Arm Bandits and Markov Decision Process.
Basically, Multi-Arm Bandits is a special case of Contextual Multi-Arm Bandits ...
1
vote
0answers
30 views
Customized food for persons based on their profile using Reinforcement learning
I am newbie to Reinforcement Learning, this is my idea - Agent(food provider) has to select a food based on the environment(based on the user profile). Here the reward will be given to the agent based ...
1
vote
2answers
95 views
Why is the optimal policy for an infinite horizon MDP deterministic?
Could someone please help me gain some intuition as to why the optimal policy for a Markov Decision Process in the infinite horizon case (agent acts forever) is deterministic?
2
votes
1answer
68 views
Is a policy in reinforcement learning analogous to a field such as APF?
If a policy maps states to actions in reinforcement learning, then for a path planning with obstacles, can't we simply use Artificial Potential Field fields for path planning and model policy ...
1
vote
1answer
118 views
What is the difference between Bayes-adaptive MDP and a Belief-MDP in Reinforcement Learning?
I have been reading a few papers in this area recently and I keep coming across these two terms. As far as I'm aware, Belief-MDPs are when you cast a POMDP as a regular MDP with a continuous state ...
2
votes
1answer
72 views
Reinforcement learning with action consisting of two discrete values
I'm new to reinforcement learning. I have a problem where an action is composed of an order (rod with a required length) and an item from a warehouse (an existing rod with a certain length, which will ...
