Questions tagged [markov-decision-process]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
0answers
21 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
50 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
29 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
33 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
42 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 ...
9
votes
1answer
211 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
215 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
49 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
33 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
489 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
61 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
106 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
167 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 ...
4
votes
1answer
79 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
66 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
183 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 ...
1
vote
1answer
55 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} \...
3
votes
2answers
63 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
39 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
254 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
78 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
130 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
34 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 ...