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.
126
questions
4
votes
1answer
56 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 ...
0
votes
0answers
32 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
23 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 ...
5
votes
1answer
82 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
34 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_{...
2
votes
0answers
25 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
39 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
37 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
71 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
19 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
20 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
53 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
76 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
3 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
69 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
117 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
35 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
73 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
63 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
59 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
23 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
59 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
43 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
32 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
46 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
192 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
43 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
88 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
80 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
75 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
67 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
73 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
70 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 ...
2
votes
0answers
56 views
If the performance of an RL agent in a partially observable environment is “good”, is this likely only accidental?
In my research, I remember to have read that, in case of an environment which can be modeled by partially observable MDP, there are no convergence guarantees (unfortunately, I do not find the paper ...
1
vote
0answers
48 views
Correct dimensionality of parameter vector for solving an MRP with linear function approximation?
I'm in the process of trying to learn more about RL by shadowing a course offered collaboratively by UCL and DeepMind that has been made available to the public. I'm most of the way through the course,...
0
votes
0answers
33 views
Why Q-Learning and SARSA have terrible performance?
I am trying to solve a MDP problem with almost 50 states and 60 actions with Q-Learning or SARSA. However, the performance of both algorithms is terrible and cannot find the optimal policy found by ...
1
vote
2answers
96 views
How do I calculate the return given the discount factor and a sequence of rewards?
I know that $G_t = R_{t+1} + G_{t+1}$.
Suppose $\gamma = 0.9$ and the reward sequence is $R_1 = 2$ followed by an infinite sequence of $7$s. What is the value of $G_0$?
As it's infinite, how can we ...
2
votes
1answer
110 views
Implementing SARSA for a 2-stage Markov Decision Process
I am a bit confused as to how exactly I should be implementing SARSA (or Q-learning too) on what is a simple 2-stage Markov Decision Task. The structure of the task is as follows:
Basically, there ...
0
votes
2answers
64 views
Does “transition model” alone in an MDP imply it's non-deterministic?
I am looking at a lecture on POMDP, and the context is that, when the quadcopter can't see the landmarks, it has to use reckoning. And then he mentions the transition model is not deterministic, hence ...
2
votes
1answer
105 views
Updating action-value functions in Semi-Markov Decision Process and Reinforcement Learning
Suppose that the transition time between two states is a random variable (for example, unknown exponential distribution); and between two arrivals, there is no reward. If $\tau$ (real number not an ...
0
votes
0answers
45 views
Model Based rl and cross entropy method with nonlinear function approximators
Pseudo code for Cross entropy method according to youtube lecture 32:55
Initialize $\mu \in R^{d}, \sigma \in R^{d}$
iteration 1,2,...
Collect n samples of $\theta_{i} \sim N(\mu,diag(\sigma))$
...
3
votes
2answers
152 views
What is the value of a state when there is a certain probability that agent will die after each step?
We assume infinite horizon and discount factor $\gamma = 1$. At each step, after the agent takes an action and gets its reward, there is a probability $\alpha = 0.2$, that agent will die. The assumed ...
3
votes
1answer
49 views
Why is learning $s'$ from $s,a$ a kernel density estimation problem but learning $r$ from $s,a$ is just regression?
In David Silver's 8th lecture he talks about model learning and says that learning $r$ from $s,a$ is a regression problem whereas learning $s'$ from $s,a$ is a kernel density estimation. His ...
5
votes
1answer
266 views
How do I convert an MDP with the reward function in the form $R(s,a,s')$ to and an MDP with a reward function in the form $R(s,a)$?
The AIMA book has an exercise about showing that an MDP with rewards of the form $r(s, a, s')$ can be converted to an MDP with rewards $r(s, a)$, and to an MDP with rewards $r(s)$ with equivalent ...
2
votes
2answers
198 views
Why is the policy not a part of the MDP definition?
I'm reading an article on reinforcement learning, and I don't understand why the agent's policy $\pi$ is not part of definition of Markov Decision process(MDP):
Bu, Lucian, Robert Babu, and Bart De ...
2
votes
0answers
66 views
Can we use a Gaussian process to approximate the belief distribution at every instant in a POMDP?
Suppose $x_{t+1} \sim \mathbb{P}(\cdot | x_t, a_t)$ denotes the state transition dynamics in a reinforcement learning (RL) problem. Let $y_{t+1} = \mathbb{P}(\cdot | x_{t+1})$ denote the noisy ...
