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.
32
questions
0
votes
0answers
27 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 ...
0
votes
0answers
22 views
Bandits with missing contexts
Say 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 context is ...
4
votes
1answer
58 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
67 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....
0
votes
0answers
30 views
What is the state of the art AI training technique for imperfect information 2 player turn based games?
As far as I can tell (correct me if I'm wrong), Alphazero (with MCTS and neural network heuristic function RL) is the state of the art training method for turn based, deterministic, perfect ...
2
votes
1answer
56 views
Markov property in maze solving problem in reinforcement learning
By definition, every state in RL has Markov property, which means that the future state depends only on the current state, not the past states.
However, I saw that in some case we can define a state ...
3
votes
1answer
33 views
Why does having a fixed policy change a Markov Decision Process (MDP) to a Markov Reward Process (MRP)?
If a policy is fixed, it is said that an MDP becomes an MRP.
Why is this so? Aren't the transitions and rewards still parameterized by the action and current state? In other words, aren't the ...
5
votes
1answer
34 views
Is the agent aware of a possible different set of actions for each state?
I have a use case where the set of actions is different for different states. Is the agent aware of what actions are valid for which states or is the agent only aware of the entire action space (in ...
2
votes
1answer
43 views
Can I have different rewards for a single action based on which state it transitions to?
I am working on an MDP where there are four states and ten actions. I am supposed to derive the optimal policy to reach the desired state. At any state, a particular action can take you to any of the ...
0
votes
0answers
13 views
Derivation for Value Iteration of CVaR
I am reading a paper named Risk-sensitive and Robust Decision-making: a CVaR Optimization Approach.
In appendix A.3 they provide a proof for their Theorem $4$. The $n=1$ case for equation (11) is ...
11
votes
1answer
266 views
How to stay a up-to-date researcher in ML/RL community?
As a student who wants to work on machine learning, I would like to know how it is possible to start my studies and how to follow it to stay up-to-date. For example, I am willing to work on RL and MAB ...
4
votes
1answer
36 views
Why are state transitions in MDPs probabilistic rather than deterministic?
I've read that for MDPs the state transition function $P_a(s, s')$ is a probability. This seems strange to me for modeling because most environments (like video games) are deterministic.
Now, I'd ...
5
votes
2answers
221 views
Why am I getting the incorrect value of lambda?
I am trying to solve for lambda using Temporal Difference Learning I am trying to figure out what lambda I need, to make TD(λ)=TD(1)
but I get the incorrect value of lambda.
Here is how I did:
<...
5
votes
2answers
53 views
Reinforcement learning with uniformly random dynamics
Suppose I have an MDP $(S, A, p, R)$ where the $p(s_j|s_i,a_i)$ is uniform, i.e given an state $s_i$ and an action $a_i$ all states $s_j$ are equally probable.
Now I want to find an optimal policy ...
2
votes
1answer
34 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(...
5
votes
1answer
648 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
69 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
140 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
62 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
197 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
82 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....
0
votes
0answers
97 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 ...
3
votes
3answers
192 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
55 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 ...
2
votes
1answer
66 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
69 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
41 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
296 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
82 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
140 views
Importance Sampling Ratio Probability
When reading Reinforcement Learning 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 ...
1
vote
0answers
39 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}$, $...
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 ...
