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.

163 questions
Filter by
Sorted by
Tagged with
24 views

$E_{\pi}[R_{t+1}|S_t=s,A_t=a] = E[R_{t+1}|S_t=s,A_t=a]$?

I would like to solve the first question of Exercise 3.19 from Sutton and Barto: Exercise 3.19 The value of an action, $q_{\pi}(s, a)$, depends on the expected next reward and the expected sum of the ...
• 143
1 vote
29 views

Determining a policy to play a game of chance

I'm trying to optimize the expected return from a game of chance, but have quickly realized the problem outclasses the introductory AI course I took in college years ago. I would appreciate any ...
• 111
1 vote
34 views

Number of possible joint policies in a Dec-POMDP and the time required to evaluate each one

I was reading a book about Dec-POMDPs and came across this curious result where the author specifies the number of possible joint policies to evaluate and the time needed to evaluate a single joint ...
1 vote
32 views

• 175
1 vote
69 views

Does the state space of an MDP change in these two examples?

In the classic Atari environments, like that introduced in the original DQN paper, the state space is the set of all possible images that the Atari emulator can produce (or more generally just any RGB ...
• 4,055
123 views

Are multi agent or self-play environments always automatically POMDPs?

As part of my thesis, I'm working on a zero sum game with RL to train an agent. The game is a real-time game, a derivation of pong, one could imagine playing pong with both sides being foosball rods. ...
• 85
855 views

Is there a fundamental difference between an environment being stochastic and being partially observable?

In AI literature, deterministic vs stochastic and being fully-observable vs partially observable are usually considered two distinct properties of the environment. I'm confused about this because what ...
• 203
34 views

Why does the Bandit Slippery Walk environment have complimentary probabilities?

I am learning about Reinforcement learning in the book Grokking Deep Reinforcement Learning. Below are snippets. Below is the description of Bandit Slippery Walk (BSW) Below is the description of two ...
• 101
51 views

Is there a mathematical formalism to deal with a missing reward signal?

Typically, a Reinforcement Learning learning problem is formalized as finding an optimal policy for a Markov Decision Process (MDP). In many real-life situations, however, an agent can only get ...
• 163
57 views

Can RL still learn in a scenario where current state and the next state are independant?

I am trying to implement reinforcement learning into my real-world problem. One thing making me hesitant to apply RL is that this real-world problem of mine is unique in a way how every state is ...
• 55
1 vote
96 views

Implementation of MDP in python to determine when to take action clean

I am trying to model the following problem as a Markov decision process. In a steel melting shop of a steel plant, iron pipes are used. These pipes generate rust over time. Adding an anti-rusting ...
• 111
40 views

Doubt in calculating the optimal costs and value after n steps of a MDP problem

MDP problem - A server requires information from a sensor. The server would like the information to be fresh. However, there is a cost to querying information from the sensor. Specifically, the state ...
• 23
1 vote
47 views

Are there any deep RL algorithms that work well on finite MDPs and non-trivial terminal rewards?

I notice that most Deep Reinforcement Learning (DRL) works focus on Markov Decision Process (MDP) with an infinite time horizon. Are there any algorithms that work well on finite MDP and non-trivial ...
75 views

In reinforcement learning, why are policies defined as functions of states and not observations?

I am new to RL and I am following Sutton & Barto's book. My doubt is, when we talk about the policy of our agent, we say it is the probability of taking some action $a$ given the state $s$. ...
33 views

Discard irrelavant states from a MDP

I came across this question about MDP. From the look of it, it seems the full MDP is reducible if the discarded state only have 1 way in and out but is it really so if we change the discounted factor? ...
• 49
32 views

How does the Markov assumption hold true for episodic task?

The Markov assumption assumes that the current state is sufficient for taking the next action. Consider an episodic task, where the RL agent is trying to learn to play the game of tic-tac-toe. Here, ...
226 views

Calculating state-value functions in Markov Decision Process

I am watching David Silver's lectures on RL available on YouTube. My question here is with regard to Lecture 2 (Link to Video). At 1:11:00, I could not understand how he is calculating the state-value ...
160 views

Is it really hard to learn in a stochastic environment?

I understand that a stochastic environment is one that does not always lead you to the desired state by giving a particular action $a$ (But the probability to change to a not desire state is fixed, ...
• 282
46 views

Markov Decision Processes with variable epoch lengths

I am working on modeling a transportation problem as an MDP. Multiple trucks move material from one node to various other nodes in a network. However, the time it takes a truck to travel between any 2 ...
• 21
87 views

Is there any inherent assumption of start and goal states in an MDP?

MDP stands for the Markov decision process. It is a 5-length tuple used in reinforcement learning. $$MDP = (S, A, T, R, \pi)$$ $S$ stands for a set of states, also called state space. $A$ stands for a ...
• 3,099
47 views

Is it better to model a Contextual Multi-Armed Bandit problem as an MDP with a non-zero discount factor than treating it as it is?

I'd like to ask if it is, generally, better to model a problem that naturally appears as a Contextual Multi-Armed Bandit like Recommender Systems as a Markov Decision Process with a non-zero discount ...
• 509
48 views

137 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 ...
• 4,055
76 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 ...
64 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 \...
• 33