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.
192
questions
1
vote
0
answers
57
views
When can we unnest the minimizations/recursions in an value function(bellman optimality equation)?
When reading the following paper(page 4): An Approximate Dynamic Programming Approach
for Dual Stochastic Model Predictive Control
I could see that they were able to unnest the minimization's in the ...
- 11
0
votes
0
answers
35
views
Optimal decision with continuous, stochastic signals and rewards
I am performing a task, where I have to decide which projects to pursue at a given point in time, where the projects have different horizons of 30 minutes.
At a given point in time, forecasts are made ...
- 1
1
vote
0
answers
17
views
How can I prove that early termination in an MDP state is valid?
I have an MDP $M$ with transition function $p$, states $S$ and a state $s^0 \in S$. $s^0$ has the property that both the most optimistic trajectory (highest expected reward) and the most pessimistic ...
- 111
1
vote
0
answers
58
views
Is this a bandit problem or a MDP?
I am trying to understand if this problem can be casted both as a bandit problem as well as an MDP.
Lets assume that we are trying to optimize sales $y_t$ based on investments $x_{1, t}, x_{2, t}$ ...
- 53
2
votes
1
answer
44
views
UCB, Thompson sampling etc seems myopic/greedy for bandits?
When considering multi-armed bandits in different formats, UCB, $\epsilon$-greedy, thompson sampling etc seems so greedy/myopic in the sense that it solely considers reward for the current timestep.
...
- 53
0
votes
1
answer
52
views
Why is R(s) more restrictive than R(s, a) in an MDP?
I am quite new to RL. I would like to know why a state-dependent reward function R(s) is more restrictive than a state-action-dependent reward function R(s, a)? And why is it that a policy can be ...
- 11
0
votes
0
answers
22
views
How to decide on size of state space?
I'm in a reinforcement learning class and we're working on a dice game problem where you profit the number rolled for certain digits and lose all your money on certain other digits. You can choose to ...
- 1
2
votes
1
answer
84
views
MDP to model finding an optimal sequence of actions with no other state data
I would like to build an RL agent who's objective is to find an N length sequence of actions to a reward where N is not known and the states are indistinguishable from each other (at least for it's ...
- 268
1
vote
0
answers
108
views
How can i cast this problem as an POMDP or an belief space MDP?
I am currently attempting to formulate my problem as either a Partially Observable Markov Decision Process (POMDP) or a Belief space MDP. My end goal is to gain insights into the proposed methods ...
- 35
0
votes
0
answers
19
views
If the agent is at the same state but at different times and receives a different reward, wouldn't this be violating somehow the MDP assumption?
I've been trying to train an agent, I've received and read suggestions to improve its speed to reach the goal. The suggestion is to use a time penalty, for example, adding $-0.1$ to the reward each ...
1
vote
1
answer
36
views
How is the Markov property of a general state-space model derived?
Below is the derivation for the Markov property of a general state-space model.
The red part is not clear. Could someone please explain the steps in the sequential derivation for the red part?
- 493
4
votes
1
answer
56
views
Could you explain these 2 steps of the derivation of the Bellman equation as a recursive equation in Sutton & Barto?
I am reading the Sutton & Barto (2018) RL textbook.
On page 59, it derives the recursive property of the state-value function as below.
Could you explain the steps of third and fourth equality?
...
- 195
1
vote
0
answers
26
views
Can we use Low rank approximation in Markov decision process problem?
I am newbie in MDP.I have started reading Ronald Howard Dynamic Programming and MDP book as well as Sutton and Barto An Introduction to Reinforcement Learning. To my understanding MDP is a model based ...
1
vote
1
answer
165
views
How can I find an upper bound on the number of iterations required to have less than $\varepsilon$ difference in the value of state?
I learned about the Value Iteration algorithm which can help find an optimal policy and values of an MDP with state rewards:
$$V_0(s)=R(s)$$
$$V_{t}(s)=R(s)+\gamma\cdot\underset{a}{max}\underset{s'}{\...
- 131
0
votes
0
answers
23
views
Under which conditions does value iteration and policy iteration will give us the optimal solution if gamma equals 1
I’m learning about policy iteration and value iteration, and I’m wondering under which conditions does both algorithms will give us the optimal solution, if our discount factor (gamma) equals 1.
Note: ...
0
votes
0
answers
238
views
Convergence of Value Iteration for Discount factor of 1
Given this pseudo code for value iteration:
In the case of gamma=1, under what conditions on the MDP will we still be able to find the optimal policy?
2
votes
1
answer
473
views
Should DQN/PPO be used for state spaces that are not that large?
I'm interested in trying out Q-learning to solve a problem where I already have a simulation of the environment that can run at about 100,000 fps or steps/sec. Its also continuous with no terminal ...
- 121
0
votes
0
answers
15
views
Does fixing an action in the state transition function of an MDP yield a transition matrix?
I stumbled across this seemingly elementary question while studying the theory of Markov Decision Processes. Suppose $\mathcal{M} = (\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R})$ is an MDP and ...
0
votes
0
answers
56
views
Should I model this problem as a POMDP?
Suppose we have a finite-horizon sequential decision-making problem. At period $t$ we are in state $s$. We take action $a$ and we receive reward $r$ and go to state $s-1$ at period $t+1$. However, it ...
- 481
1
vote
0
answers
42
views
Would the optimal policy remain same, if I replace R with V*?
In the context of RL, say I'm performing Value Iteration on a reward function R1. And the converged optimal policy is P1 and values are V1.
Then, let's say I set rewards to be R2=V1 and perform value ...
2
votes
1
answer
139
views
What is the difference between these two versions of the Bellman equation?
The first version is the one I am most familiar with:
$$V_\pi(s) = \sum_{a}^{}\pi(a|s) \sum_{s'}^{}T(s, a, s')[R(s, a, s') + \gamma V_\pi(s')]$$
where $T(s, a, s')$ represents the probability of ...
- 133
1
vote
0
answers
228
views
MDP with a non-markovian reward function?
I have set up a RL environment and it converges to a decent solution when using a reward function:
$R(s_t,a_t) = fenv(s_t, a_t)$ , where $fenv$ is the environment dynamics.
Now, i want to change the ...
- 11
0
votes
1
answer
758
views
How can we approximate infinite horizon MDP with finite horizon MDP in the context of reinforcement learning?
For a given value of "discount factor" (and reward values' range) in fixed finite horizon markov decision process (MDP), upto how many episodes we have to extend this MDP so that we can ...
1
vote
1
answer
147
views
How to correctly evaluate the state value of this simple markov decision process?
For some contexts, I'm working on a c# library for reinforcement learning. I implemented two methods to evaluate a state value function, namely the TD(0) method and the Monte Carlo first visit method.
...
- 113
1
vote
0
answers
35
views
How to compare different trajecories in a Markov Decision Process
I realize that my question is a bit fuzzy and I am sorry for that. If needed, I will try to make it more rigorous and precice.
Let $\mathcal{M}$ be a Markov Decision Process, with state space $\...
- 173
2
votes
1
answer
473
views
In the Policy Gradient Theorem proof, why is $d^\pi(s) = \sum_{k=0}^{\infty}\gamma^{k}Pr(s_0 \rightarrow s, k, \pi)$ true?
I was reading the original Policy Gradient Paper. I didn't quiet get the last step of the proof for the policy gradient theorem. The proof given in the paper is below:
I don't understand how the last ...
- 31
2
votes
1
answer
266
views
What's the relationship between Bayesian RL and POMDPs?
Bayesian RL seems concerned with having uncertainty over the transition function of the environment, while POMDPs try to capture uncertainty over the state one is currently in. However, both end up ...
- 380
1
vote
1
answer
623
views
Markov's Decision Process - calculate value in each iteration
I have the following decision tree:
I calculated the value of the plan using the following paramenters (given):
{𝑆0 → 𝑎1 , 𝑆1 → 𝑎3 , 𝑆2 → 𝑎4 },
Discount factor (𝛾)= 0.2
I used this formula to ...
- 13
1
vote
1
answer
78
views
How to prove that an action-value function optimal for one problem formulation is also optimal for another?
I want to ask about the intuition/where-to-look/what-to-try if I want to prove that an action value function optimal for a problem is also optimal for another reformulation of that smae problem. For ...
- 31
2
votes
1
answer
172
views
Remove already reached targets from the system to enable reaching other targets?
This may be a very fundamental question, but somehow I can't decide.
I have a graph and the user can take several actions while traversing it and there are multiple points with rewards. When I execute ...
0
votes
0
answers
51
views
How to represent the state and action space when modeling card game Love Letter using Markov Decision Process
Now my task is to use model checking to find a best strategy for card game Love Letter, and I need to model the game using Markov Decison Process first.
I have done a lot of resaerch and I decided to ...
4
votes
0
answers
155
views
What is the correct interpretation of the discount factor in MDPs?
In infinite-horizon MDPs one can consider the expected discounted return from a distribution of start states as the objective[^1]. i.e. $\mathbb{E}[V^{\pi}(S_0)] = \mathbb{E}[G_0] = \mathbb{E}[\sum_{t=...
- 41
0
votes
0
answers
30
views
Rewrite the four Bellman equations for the four value functions $(v_{\pi},v_*,q_{\pi},q_*)$ in terms of $p$ (3.4) and $r$ (3.5) [duplicate]
I have done exercise 3.29 from Sutton and Barto and I'd like to check if it's correct. Here's the exercise:
Rewrite the four Bellman equations for the four value functions $(v_{\pi},v_*,q_{\pi},q_*)$ ...
- 145
1
vote
2
answers
504
views
Does maximizing the value function and maximizing the state-action value function generate the same optimal policy?
In reinforcement learning, we define the optimal policy $\pi^*$ as the policy that maximizes the value of the state:
$$
\pi_v^*=\underset{\pi}{\operatorname{argmax}} {V_{\pi}(s)}
$$
In Q-learning, we ...
- 213
4
votes
1
answer
151
views
$E_{\pi}[R_{t+1}|S_t=s,A_t=a] = E[R_{t+1}|S_t=s,A_t=a]$?
I would like to solve the first question of Exercise 3.19 from Sutton and Barto:
Exercise 3.19 The value of an action, $q_{\pi}(s, a)$, depends on the expected next reward and
the expected sum of the ...
- 145
1
vote
0
answers
52
views
Determining a policy to play a game of chance
I'm trying to optimize the expected return from a game of chance, but have quickly realized the problem outclasses the introductory AI course I took in college years ago. I would appreciate any ...
user55846
1
vote
0
answers
48
views
Number of possible joint policies in a Dec-POMDP and the time required to evaluate each one
I was reading a book about Dec-POMDPs and came across this curious result where the author specifies the number of possible joint policies to evaluate and the time needed to evaluate a single joint ...
- 31
1
vote
1
answer
228
views
Can the state transition function be dynamic in reinforcement learning?
In general, there are two types of transition functions in reinforcement learning. Mathematically, they are as follows
#1: Stochastic state transition function:
$$T : S \times A \times S \rightarrow [...
- 3,612
2
votes
1
answer
206
views
Is it appropriate to represent 'total failure' as an absorbing state?
My understanding is that, in Markov decision processes, absorbing state are states which can transition only to themselves and that these transitions generate rewards of 0. I know that absorbing ...
- 121
0
votes
1
answer
53
views
Does the policy search work if there is no state to state dependency through actions?
There is a game in which the state comes one after the other without depending on the agent's action. The agent gets a reward for its actions at the end of the game. The goal of the agent is to reach ...
- 19
0
votes
1
answer
73
views
Does $S_{t+1}$ denote the future information in Q-learning?
In Q-learning, $Q(S_t,a)$ is updated by the Bellman equation. $Q(S_t,a) = r + \max_{a'}(Q(S_{t+1},a'))$ where $S_{t+1}$ is the future state.
Let's say $S$ denotes the stock price, does it mean we are ...
- 1
0
votes
1
answer
53
views
Does $R_{s}=E[R_{t}|S_{t}=s]$ indicate the reward we might expect on getting on average moving from any other state to $s$?
I'm trying to understand correctly what each "variable" in RL is and I'm not sure about $R_{s}$ the reward function. I used to think that it's the reward we may expect on average after ...
- 573
2
votes
1
answer
746
views
Factors that affect the number of iterations of value iteration
I had an assumption that value iteration will take more iterations to converge if the map size increases/environment's complexity increases.
I tried to verify this idea by running value iteration on ...
- 23
1
vote
1
answer
177
views
Are these two forms of the state value function the same?
Why are there different forms of the value function in reinforcement learning?
Sutton & Barto (2nd edition, equation 3.14) define the state value function as follows
$$v_{\pi}(s) = \displaystyle\...
- 175
1
vote
1
answer
210
views
Does the state space of an MDP change in these two examples?
In the classic Atari environments, like that introduced in the original DQN paper, the state space is the set of all possible images that the Atari emulator can produce (or more generally just any RGB ...
- 4,665
4
votes
1
answer
344
views
Are multi agent or self-play environments always automatically POMDPs?
As part of my thesis, I'm working on a zero sum game with RL to train an agent.
The game is a real-time game, a derivation of pong, one could imagine playing pong with both sides being foosball rods.
...
- 115
13
votes
2
answers
2k
views
Is there a fundamental difference between an environment being stochastic and being partially observable?
In AI literature, deterministic vs stochastic and being fully-observable vs partially observable are usually considered two distinct properties of the environment.
I'm confused about this because what ...
- 255
2
votes
1
answer
93
views
Is there a mathematical formalism to deal with a missing reward signal?
Typically, a Reinforcement Learning learning problem is formalized as finding an optimal policy for a Markov Decision Process (MDP). In many real-life situations, however, an agent can only get ...
- 173
2
votes
1
answer
410
views
Can RL still learn in a scenario where current state and the next state are independant?
I am trying to implement reinforcement learning into my real-world problem.
One thing making me hesitant to apply RL is that this real-world problem of mine is unique in a way how every state is ...
- 55
1
vote
0
answers
164
views
Implementation of MDP in python to determine when to take action clean
I am trying to model the following problem as a Markov decision process.
In a steel melting shop of a steel plant, iron pipes are used. These pipes generate rust over time. Adding an anti-rusting ...
- 111