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
119 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 ...
4
votes
1answer
186 views

Why can't we apply value iteration when we do not know the reward and transition functions, and how does Q-learning solve this issue?

I don't understand why we can't apply value iteration when don't know the reward and transition probabilities. In this lecture, the lecturer says it has to do with not being able to take max with ...
1
vote
1answer
175 views

How can we estimate the transition model and reward function?

In reinforcement learning (RL), there are model-based and model-free algorithms. In short, model-based algorithms use a transition model (e.g. a probability distribution) and the reward function, even ...
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 (...
7
votes
3answers
1k views

How can you represent the state and action spaces for a card game in the case of a variable number of cards and actions?

I know how a machine can learn to play Atari games (Breakout): Playing Atari with Reinforcement Learning. With the same technique, it is even possible to play FPS games (Doom): Playing FPS Games with ...
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
1answer
77 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 ...
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 ...
2
votes
1answer
54 views

Do we have to consider the feasability of an action when defining the reward function of a MDP?

Do we have to consider if (s is given) an action a can lead to s' when defining a reward function? To be more specific: Let's say I have a 1D Map like: |A|B|C|D| ...
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 ...
3
votes
2answers
830 views

When is the Markov decision process not adequate for goal-directed learning tasks?

In the book Reinforcement Learning: An Introduction (Sutton and Barto, 2018). The authors ask Exercise 3.2: Is the MDP framework adequate to usefully represent all goal-directed learning tasks? ...
1
vote
2answers
102 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, ...
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
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 ...
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 ...
4
votes
2answers
2k views

What is a time-step in a Markov Decision Process?

The “Discounted sum of future rewards” using discount factor $\gamma$ is $\gamma$ (reward in 1 time step) + $\gamma^2$ (reward in 2 time steps) + $\gamma^3$ (reward in 3 time steps) + ... I am ...
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,...
1
vote
2answers
532 views

Is Monte Carlo Tree Search appropriate for problems with large state and action spaces?

I'm doing a research on a finite-horizon Markov decision process with $t=1, \dots, 40$ periods. In every time step $t$, the (only) agent has to chose an action $a(t) \in A(t)$, while the agent is in ...
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 ...
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 ...
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 ...
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 ...
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
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 ...
3
votes
2answers
148 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 ...
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))$ ...
1
vote
2answers
207 views

In the context of importance sampling ratio, how is the equation $\mathbb{E}\left[\rho_{t: T-1} G_{t} | S_{t}=s\right]=v_{\pi}(s)$ derived?

When reading the book by Sutton and Barto, I came across the importance sampling ratio. The first equation, I believe, describes the probability a particular sequence is obtained given the current ...
5
votes
1answer
2k views

How can we use linear programming to solve an MDP?

Apparently, we can solve an MDP (that is, we can find the optimal policy for a given MDP) using a linear programming formulation. What's the basic idea behind this approach? I think you should start ...
8
votes
1answer
304 views

What are some resources on continuous state and action spaces MDPs for reinforcement learning?

Most introductions to the field of MDPs and Reinforcement learning focus exclusively on domains where space and action variables are integers (and finite). This way we are introduced quickly to Value ...
5
votes
2answers
480 views

Why am I getting the incorrect value of lambda?

I am trying to solve for $\lambda$ using temporal-difference learning. More specifically, I am trying to figure out what $\lambda$ I need, such that $\text{TD}(\lambda)=\text{TD}(1)$, after one ...
1
vote
1answer
56 views

How should I define an MDP for this problem where we need to guess a number and minimise the number of guesses?

A number has randomly been chosen from 1 to 3. On each step, we can make a guess and we will be told if our guess is equal, bigger or smaller than the chosen number. We're trying to find the number ...
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 ...
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 ...
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
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. ...
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 ...
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 ...
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 ...
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 ...
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 ...
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
1answer
106 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....
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. ...