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
3
votes
0answers
243 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
93 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
304 views

Why does having a fixed policy change a Markov Decision Process to a Markov Reward Process?

If a policy is fixed, it is said that a Markov Decision Process (MDP) becomes a Markov Reward Process (MRP). Why is this so? Aren't the transitions and rewards still parameterized by the action and ...
5
votes
1answer
75 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 each state, or is the agent only aware of the entire action space (in ...
3
votes
1answer
176 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 ...
1
vote
0answers
50 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
223 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, ...
3
votes
1answer
60 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 ...
14
votes
1answer
570 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 ...
1
vote
1answer
375 views

How can I encode states where the environment consists of multiple identical elements, but each is characterised by different features?

I am quite new to Deep Reinforcement Learning, and I'm trying to define states in a Reinforcement Learning problem. The environment consists of multiple identical elements, and each one of them is ...
4
votes
1answer
91 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
761 views

Why am I getting the incorrect value of lambda?

I am trying to solve for $\lambda$ using temporal-difference learning. More specifically, I am trying to figure out what $\lambda$ I need, such that $\text{TD}(\lambda)=\text{TD}(1)$, after one ...
1
vote
1answer
924 views

What is the reward system of reinforcement learning?

Can you describe this reward system in more detail? I understand that the environment sends a signal indicating whether or not the action taken by the agent was 'good' or not, but it seems too simple. ...
5
votes
2answers
210 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 ...
3
votes
1answer
49 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
42 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 ...
6
votes
1answer
3k 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
63 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
3k 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 ...
4
votes
0answers
122 views

What is a generalized MDP?

What is a generalized MDP? Here are a few sub-questions. How is it different than a "regular" MDP? How does it generalize the notion of an MDP? Why do we need a generalized MDP? Do ...
1
vote
1answer
361 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
78 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
496 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
120 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....
4
votes
1answer
331 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
66 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
186 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} \...
5
votes
2answers
275 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
51 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 ...
3
votes
2answers
901 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 ...
1
vote
2answers
232 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
72 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
1answer
1k 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
2answers
1k 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? ...
17
votes
2answers
11k views

How to define states in reinforcement learning?

I am studying reinforcement learning and the variants of it. I am starting to get an understanding of how the algorithms work and how they apply to an MDP. What I don't understand is the process of ...
2
votes
2answers
63 views

Should we feed a greater fraction of terminal states to the value network so that their values are learned first?

The basis of Q-learning is recursive (similar to dynamic programming), where only the absolute value of the terminal state is known. Shouldn't it make sense to feed the model a greater proportion of ...
1
vote
1answer
140 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 ...
8
votes
1answer
168 views

How to fill in missing transitions when sampling an MDP transition table?

I have a simulator modelling a relatively complex scenario. I extract ~12 discrete features from the simulator state which forms the basis for my MDP state space. Suppose I am estimating the ...
6
votes
1answer
317 views

What techniques are used to make MDP discrete state space manageable?

Generating a discretized state space for an MDP (Markov Decision Process) model seems to suffer from the curse of dimensionality. Supposed my state has a few simple features: Feeling: Happy/Neutral/...
4
votes
1answer
216 views

Why can't we apply value iteration when we do not know the reward and transition functions, and how does Q-learning solve this issue?

I don't understand why we can't apply value iteration when don't know the reward and transition probabilities. In this lecture, the lecturer says it has to do with not being able to take max with ...
6
votes
2answers
2k views

What is a time-step in a Markov Decision Process?

The "discounted sum of future rewards" (or return) using discount factor $\gamma$ is $$\gamma^1 r_1 +\gamma^2 r_2 + \gamma^3 r_2 + \dots \tag{1}\label{1}$$ where $r_i$ is the reward received ...
8
votes
3answers
2k views

How can you represent the state and action spaces for a card game in the case of a variable number of cards and actions?

I know how a machine can learn to play Atari games (Breakout): Playing Atari with Reinforcement Learning. With the same technique, it is even possible to play FPS games (Doom): Playing FPS Games with ...
8
votes
1answer
369 views

What are some resources on continuous state and action spaces MDPs for reinforcement learning?

Most introductions to the field of MDPs and Reinforcement learning focus exclusively on domains where space and action variables are integers (and finite). This way we are introduced quickly to Value ...

1 2
3