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.

Filter by
Sorted by
Tagged with
1
vote
1answer
27 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!
3
votes
2answers
92 views

What are some best practices when trying to design a reward function?

Generally speaking, is there a best-practice procedure to follow when trying to define a reward function for a reinforcement-learning agent? What common pitfalls are there when defining the reward ...
2
votes
1answer
64 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
37 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
67 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
44 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
32 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
53 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
59 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
45 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
95 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
43 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
144 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
43 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 ...
4
votes
1answer
93 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
182 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
59 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
150 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
33 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
33 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 ...
1
vote
0answers
44 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
74 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
38 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
26 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
157 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
29 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
35 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
56 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
23 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
35 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
43 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^{*}$ ...
1
vote
0answers
20 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
28 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
47 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
48 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
45 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=(...
1
vote
2answers
76 views

Policy invariance under affine transformations of the reward function?

In the context of a Markov decision process, this paper says "it is well-known that the optimal policy is invariant to positive affine transformation of the reward function". On the other hand, ...
2
votes
1answer
145 views

How can I constraint the actions with dependent coordinates?

I am working on a customized RL environment where each action is represented as a tuple $a = (a_1,a_2,\cdots,a_n)$ such that certain condition must be satisfied for entries of $a$ (for instance, $a_1+...
0
votes
1answer
18 views

Unable to understand V* at infinite time horizon using Bellman equation for solving MDP

I've been following the Berkeley cs188's assignment (I'm not taking the course). Currently, they don't show the solution in the gradescope unless I get it correct. My reasoning was $V^*(a)$ = 10 ...
3
votes
0answers
48 views

Are there reinforcement learning algorithms not based on Markov decision processes?

Are all RL algorithms based on the MDP? If not, could you give examples of some which aren't? I've looked elsewhere, but I haven't seen it explicitly said.
2
votes
0answers
58 views

Formulation of a Markov Decision Process Problem

Given a list of $N$ questions. If question $i$ is answered correctly (given probability $p_i$), we receive reward $R_i$; if not the quiz terminates. Find the optimal order of questions to maximize ...
2
votes
0answers
39 views

Why is this Monte Carlo approach scalable for a growing number of states variables and action variables?

I am reading a research paper on the formulation of MDP problems to ICU treatment decision making: Treatment Recommendation in Critical Care: A Scalable and Interpretable Approach in Partially ...
6
votes
1answer
110 views

Interesting examples of discrete stochastic games

SGs are a generalization of MDPs to multiple agents. Like this previous question on MDPs, are there any interesting examples of zero-sum, discrete SGs—preferably with small state and action spaces? I'...
1
vote
0answers
77 views

What is the difference between value iteration and policy iteration? [duplicate]

In reinforcement learning, what is the difference between policy iteration and value iteration? As much as I understand, in value iteration, you use the Bellman equation to solve for the optimal ...
1
vote
0answers
35 views

How do I determine the optimal policy in a bandit problem with missing contexts?

Suppose I learn an optimal policy $\pi(a|c)$ for a contextual multi-armed bandit problem, where the context $c$ is a composite of multiple context variables $c = c_1, c_2, c_3$. For example, the ...
2
votes
0answers
21 views

Finding total number of states in a POMDP

I've been working on a question that is posed in a document I've been reading, that models qualifying for a job as a POMDP. In this model, a person takes 3 exams, and must pass all of them in order to ...
4
votes
1answer
105 views

How to assign rewards in a non-Markovian environment?

I am quite new to the Reinforcement Learning domain and I am curious about something. It seems to be the case that the majority of current research assumes Markovian environments, that is, future ...
2
votes
1answer
99 views

Solving a Multi-Armed, “Multi-Bandit” Problem

This is the problem: I have 66 slot-machines and for each of them I have 7 possible actions/arms to choose from. At each trial, I have to choose one of 7 actions for each and every one of the 66 slots....
2
votes
1answer
39 views

Why feed actions in later layer in Q network?

I read the DDPG paper, in which the authors state that the actions are fed only later to their Q network: Actions were not included until the 2nd hidden layer of Q. (Sec 7, Experiment Details) So ...