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
4
votes
1answer
118 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
10 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
9 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
37 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
76 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
60 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
28 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
1answer
33 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
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
39 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
68 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
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
56 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
70 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
48 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
147 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
45 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
108 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
186 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
191 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
36 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
48 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
79 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
42 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
177 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
40 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
60 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
24 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
39 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
59 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
49 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
48 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
97 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
49 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
59 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'...