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.
58
questions
3
votes
0answers
18 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
47 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
13 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
25 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
32 views
+100
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
12 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
21 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}$), ...
0
votes
1answer
27 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
1answer
34 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
37 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
1answer
18 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
138 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
12 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
40 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
47 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
35 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
103 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'...
0
votes
0answers
32 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
23 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 ...
1
vote
0answers
18 views
Finding total number of states in a POMDP
I've been working on a question that is posed in a document I've been reading, that models qualifying for a job as a POMDP. In this model, a person takes 3 exams, and must pass all of them in order to ...
4
votes
1answer
74 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
73 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....
2
votes
1answer
28 views
Why feed actions in later layer in Q network?
I read the DDPG paper, in which the authors state that the actions are fed only later to their Q network:
Actions were not included until the 2nd hidden layer of Q. (Sec 7, Experiment Details)
So ...
1
vote
0answers
67 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
58 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
57 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
38 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
72 views
Can someone please help me validate my MDP?
Problem Statement :
I have a system with four states - S1 through S4 where S1 is the beginning state and S4 is the end/terminal state. The next state is always better than the previous state i.e if ...
0
votes
0answers
37 views
Finding optimal Value function and Policy for an MDP
I am solving an RL MDP problem which is model based. I have an MDP which has four possible states S1-S4 and four different actions A1-A4, with S4 being terminal state and S1 is the beginning state. ...
6
votes
1answer
134 views
Benchmarks for reinforcement learning in discrete MDPs
To compare the performance of various algorithms for perfect information games, reasonable benchmarks include reversi and m,n,k-games (generalized tic-tac-toe). For imperfect information games, ...
2
votes
1answer
46 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
15 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
314 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
39 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
364 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
61 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
35 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 ...
4
votes
1answer
879 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
43 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
928 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
75 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
176 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
66 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
249 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
91 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
3answers
229 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
58 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 ...
3
votes
1answer
82 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
78 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, ...
