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
2
votes
1answer
39 views

Are successive actions independent?

The proof of the consistency of the per-decision importance sampling estimator assumes the independence of $$\frac{\pi(A_t|S_t)}{b(A_t|S_t)}R_{t+1}\quad\text{ and }\quad \prod_{k=t+1}^{T-1}\frac{\pi(...
3
votes
0answers
38 views

Does everyone still use discount rates?

In Section 10.4 of Sutton and Barto's RL book, they argue that the discount rate $\gamma$ has no effect in continuing settings. They show (at least for one objective function) that the average of the ...
5
votes
1answer
1k views

Can Q-learning be used in a POMDP?

Can Q-learning (and SARSA) be directly used in a Partially Observable Markov Decision Process (POMDP)? If not, why not? My intuition is that the policies learned will be terrible because of partial ...
2
votes
1answer
46 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| ...
5
votes
1answer
1k 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 ...
3
votes
0answers
79 views

What is a generalized MDP?

What is a generalized MDP? How is it different than a "regular" MDP? How does it generalise the notion of an MDP? Why do we need a generalised MDP? Do generalised MDPs have some practical usefulness ...
1
vote
1answer
192 views

Unable to understand the second iteration update in value iteration algorithm for solving MDP

I am trying to understand the value iteration method for Markov Decision Process(MDP) and I was referring ot UC Berkeley's slides titled Markov Decision Processes and Exact Solution Methods On slide ...
2
votes
1answer
67 views

Does the observation function for POMDP always add up to 1?

I was reading in the article A tutorial on partially observable Markov decision processes (p. 120), by Michael L. Littman, that $\sum_{z \in Z}O(a, s',z) =1$, where $a$ is the action, $s'$ the next ...
3
votes
2answers
287 views

Difference in continuing and episodic cases in Sutton and Barto - Introduction to RL, exercise 3.5

Excercise 3.5 The equastions in Section 3.1 are for the continuing case and need to be modified (very slightly) to apply to episodic tasks. Show that you know the modifications needed by giving ...
5
votes
1answer
95 views

Should I model my problem as a semi-MDP?

I have a system (like a bank) that people (customers) are entered into the systems by a Poisson process, so the time between the arrival of people (two consecutive customers) will be a random variable....
3
votes
1answer
245 views

Can the rewards be stochastic when the transition model is deterministic?

Suppose we have a deterministic environment where knowing $s,a$ determines $s'$. Is it possible to get two different rewards $r\neq r'$ in some state $s_{\text{fixed}}$? Assume that $s_{\text{fixed}}$ ...
1
vote
1answer
61 views

Is the next state drawn from the joint distribution of the previous state and action?

Suppose $G_t$, the discounted return at time $t$ is defined as: $$ G_t \triangleq R_t+\gamma R_{t+1}+\gamma^{2}R_{t+2} + \cdots = \sum_{j=1}^{\infty} \gamma^{k}R_{t+k}$$ where $R_t$ is the reward at ...
4
votes
1answer
94 views

What is the relation between a policy which is the solution to a MDP and a policy like $\epsilon$-greedy?

In the context of reinforcement learning, a policy, $\pi$, is often defined as a function from the space of states, $\mathcal{S}$, to the space of actions, $\mathcal{A}$, that is, $\pi : \mathcal{S} \...
4
votes
2answers
96 views

How are the reward functions $R(s)$, $R(s, a)$ and $R(s, a, s')$ equivalent?

In this video, the lecturer states that $R(s)$, $R(s, a)$ and $R(s, a, s')$ are equivalent representations of the reward function. Intuitively, this is the case, according to the same lecturer, ...
1
vote
0answers
44 views

What limitations does the Markov property place on real time learning?

The Markov property is the dependence of a system's future state probability distribution solely on the present state, excluding any dependence on past system history. The presence of the Markov ...
1
vote
2answers
430 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
90 views

What is the appropriate approach to playing a game with incomplete state information?

I have a steady hex-map and turn-based war game featuring WWII carrier battles. I would like to improve the fixed policy for the AI using reinforcement learning. I have some beginner's questions, ...
1
vote
1answer
175 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 ...
1
vote
0answers
49 views

How to generalize finite MDP to general MDP?

Suppose, for simplicity sake, to be in a discrete time domain with the action set being the same for all states $S \in \mathcal{S}$. Thus, in a finite Markov Decision Process, the sets $\mathcal{A}$, $...
1
vote
0answers
482 views

Is my understanding of the differences between MDP, Semi MDP and POMDP correct?

I just wanted to confirm that my understanding of the different Markov Decision Processes are correct, because they are the fundamentals of reinforcement learning. Also, I read a few literature ...
3
votes
1answer
628 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
1answer
51 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
2answers
1k 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
2