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.
106
questions
0
votes
0answers
19 views
What is the best way to convert an historical log data file to a Markov Decision Process (MDP) to perform Q-learning? [closed]
Hypothetically, I have an historical log file whose entries contain the instantaneous throughput for the transfer of a set of files (25,000 files ranging in size from 101KB to 222MB) recorded every ...
2
votes
0answers
18 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 \...
2
votes
1answer
57 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
21 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
39 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
30 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
44 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
162 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
11 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
39 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
83 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
69 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
29 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 ...
2
votes
1answer
46 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), deterministic?
Thank you!
2
votes
1answer
66 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
0answers
42 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
69 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
45 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
65 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
95 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
55 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
103 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
44 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
151 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
47 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
135 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
190 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 ...
3
votes
0answers
64 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 ...
1
vote
1answer
297 views
How can blackjack be formulated as a Markov decision process?
I am reading sutton barton's reinforcement learning textbook and have come across the finite Markov decision process (MDP) example of the blackjack game (Example 5.1).
Isn't the environment ...
1
vote
0answers
35 views
State-of-the-art algorithms not working on a custom RL environment
I'm trying to train a RL agent on a custom, highly stochastic environment (MDP). In order to do so I'm using existing implementations of state-of-the-art RL algorithms as provided by Stable Baselines. ...
0
votes
1answer
45 views
What is the difference between the state transition of an MDP and an action-value?
Let's say we have MDP where we have a state transition matrix.
How is this state transition different from action value in reinforcement learning? Is the state transition in MDP stochastic ...
2
votes
0answers
51 views
How are the classical MDP and the object-oriented MDP views different?
I've been reading the attached paper - which aims to model entities in the world as objects, including the learning agent itself!
To say the least, the goal is to navigate through what seems like a ...
2
votes
3answers
87 views
Why does it make sense to study MDPs with finite state and action spaces?
In the standard Markov Decision Process (MDP) formalization of the reinforcement-learning (RL) problem (Sutton & Barto, 1998), a decision maker interacts with an environment consisting of finite ...
1
vote
1answer
46 views
Can optimizing for immediate reward result in a policy maximizing the return?
The goal of a reinforcement learning agent is to maximize the expected return which is often a discounted sum of future rewards. The return indeed is a very noisy random variable as future rewards ...
3
votes
0answers
29 views
Relationship between the reward rate and the sampled reward in a Semi-Markov Decision Process
In the paper: Reinforcement learning methods for continuous-time Markov decision problems, the authors provide the following update rule for the Q-learning algorithm, when applied to Semi-Markov ...
3
votes
2answers
218 views
Formula for expected rewards for state–action–next-state triples as a three-argument function
While reading about reinforcement learning, I have come across the following expression for expected rewards in terms of a summation, the denominator of which I am not able to account for.
The ...
2
votes
0answers
30 views
How can I formalise a non-zero-sum game of $N$ agent as Markov game?
I coded a non-zero-sum game of $N$ agents in a discrete dynamic environment to RL with Q-learning and DQN agents.
It's like a marathon. Only two actions are available per agent: $\{ G \text{ (move ...
3
votes
0answers
60 views
How is the state-visitation frequency computed in “Maximum Entropy Inverse Reinforcement Learning”?
I am trying to understand the formulation of the maximum entropy Inverse RL method by Brian Ziebart. Particularly, I am stuck on how to understand the computation of state - visitation frequencies.
...
3
votes
1answer
68 views
What is the intuition behind grid-based solutions to POMDPs?
After spending some time reading about POMDP, I'm still having a hard time understanding how grid-based solutions work.
I understand the finite horizon brute-force solution, where you have your ...
2
votes
0answers
26 views
How should I define the reward function for the Connect Four game?
I'm creating an RL application for the game Connect Four. I've researched the different strategies for the game and which positions are more favourable to lead to a win.
Should I be assigning ...
1
vote
0answers
45 views
Why can the core reinforcement learning algorithms be applied to POMDPs?
Why can an AI, like AlphaStar, work in StarCraft, although the environment is only partially observable? As far as I know, there are no theoretical results on RL in the POMDP environment, but it ...
1
vote
0answers
45 views
Efficient algorithm to obtain near optimal policies for an MDP
Given a discrete, finite Markov Decision Process (MDP) with its usual parameters $(S, A, T, R, \gamma)$, it is possible to obtain the optimal policy $\pi^{*}$ and the optimal value function $V^{*}$ ...
2
votes
0answers
22 views
What are the most common non-Markov RL paradigms?
I am interested in doing model-free RL but not using the Markov assumptions typical for MDPs or POMDPs.
What are alternative paradigms that don't rely on the Markov assumptions? Are there any common ...
2
votes
0answers
29 views
How to draw backup diagram when reward is in expectation but next state is iterated?
I am working through Sutton and Barto's RL book. So far in the text, when backup diagrams are drawn, the reward and next state are iterated together (i.e. the equations always have $\sum_{s',r}$), ...
1
vote
1answer
73 views
Why isn't the implementation of my policy evaluation for a simple MDP converging?
I am trying to code out a policy evaluation algorithm to find the $V^\pi(s)$ for all states. The following diagram below shows the MDP.
In this case i let p = q = 0.5.
the rewards for each states ...
4
votes
1answer
52 views
How is the Markovian property consistent in reinforcement learning based scheduling?
In Reinforcement Learning, an MDP model incorporates the Markovian property. A lot of scheduling applications in a lot of disciplines use reinforcement learning (mostly deep RL) to learn scheduling ...
0
votes
0answers
51 views
How to understand and visualize a trained RL agent's policy when the state space is high dimensional?
What are typical ways to understand and visualize a trained RL agent's policy when the state space is of high dimension (but not images)?
For example, suppose state and action are denoted by $s=(...
