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
0
votes
2answers
58 views

Is there a natural way to define the terminal state from the MDP transition probabilities $p(s',r|s,a)$?

I'm learning the basics of RL and I'm struggling to understand the notion of terminal state in MDPs. To ask my question straightforwardly: is there a natural way to define the terminal state from the ...
2
votes
0answers
14 views

Are there any known disadvantages of implementing vanilla Q-learning on a discretized-state space environment?

For an RL problem on a continuous state space, the states could be discretized into buckets and these buckets used in implementing the Q-table. I see that is what is done here. However, according to ...
1
vote
1answer
25 views

What is a good convergence criterion for Q-learning in a stochastic environment?

I have a stochastic environment and I'm implementing a Q-table for the learning that happens on the environment. The code is shown below. In short, there are ten states (0, 1, 2,...,9), and three ...
2
votes
1answer
57 views

Does stochasticity of an environment necessarily mean non-stationarity in MDPs?

Is a stochastic environment necessarily also non-stationary? To elaborate, consider a two-state environment ($s_1$ and $s_2$), with two actions $a_1$ and $a_2$. In $s_1$, taking action $a_1$ has a ...
1
vote
1answer
65 views

What is the difference between Bayes-adaptive MDP and a Belief-MDP in Reinforcement Learning?

I have been reading a few papers in this area recently and I keep coming across these two terms. As far as I'm aware, Belief-MDPs are when you cast a POMDP as a regular MDP with a continuous state ...
3
votes
1answer
62 views

Why can we take the action $a$ from the next state $s'$ in the max part of the Q-learning update rule, if that action doesn't lead to any reward?

I'm using OpenAI's cartpole environment. First of all, is this environment not Markov? Knowing that, my main question concerns Q-learning and off-policy methods: For me, there is something weird in ...
3
votes
1answer
112 views

How can we find the value function by solving a system of linear equations without knowing the policy?

An MDP is a Markov Reward Process with decisions, it’s an environment in which all states are Markov. This is what we want to solve. An MDP is a tuple $(S, A, P, R, \gamma)$, where $S$ is our state ...
2
votes
2answers
61 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 ...
2
votes
0answers
33 views

What trait of a planning problem makes reinforcement learning a well suited solution?

Planning problems have been the first problems studied at the dawn of AI (Shakey the robot). Graph search (e.g. A*) and planning (e.g. GraphPlan) algorithms can be very efficient at generating a plan. ...
4
votes
1answer
54 views

How should I implement the state transition when it is a Gaussian distribution?

I am reading this paper Anxiety, Avoidance and Sequential Evaluation and is confused about the implementation of a specific lab study. Namely, the authors model what is called the Balloon task using a ...
2
votes
1answer
61 views

How can I go from $R(s)$ to $R(s,a)$ in this specific MDP?

I'm trying to implement a research paper, as explained in this other post, here the author of the paper assumed R as a function of both states and actions, while the code (and the MDP) I'm using to ...
8
votes
1answer
147 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 ...
5
votes
2answers
193 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
1answer
808 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 ...
6
votes
2answers
132 views

Are perfect and imperfect information games modelled as fully and partially observable environments, respectively?

In perfect information games, the agent can see all the moves performed in the past. Besides, it can observe the next action that will be put into practice by the opponent. In this case, can we say ...
3
votes
1answer
249 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
151 views

How do I convert an MDP with the reward function in the form $R(s,a,s')$ to and an MDP with a reward function in the form $R(s,a)$?

The AIMA book has an exercise about showing that an MDP with rewards of the form $r(s, a, s')$ can be converted to an MDP with rewards $r(s, a)$, and to an MDP with rewards $r(s)$ with equivalent ...
4
votes
1answer
72 views

Can you convert a MDP problem to a Contextual Multi-Arm Bandits problem?

I'm trying to get a better understanding of Multi-Arm Bandits, Contextual Multi-Arm Bandits and Markov Decision Process. Basically, Multi-Arm Bandits is a special case of Contextual Multi-Arm Bandits ...
1
vote
1answer
680 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. ...
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 ...
2
votes
0answers
21 views

Does there necessarily exist “dominated actions” in a MDP?

In a Markov Decision Process, is it possible that there exists no "dominated action"? I define a dominated action the following way: we say that $(s,a)$ is a dominated action, if $\forall \...
4
votes
0answers
103 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
58 views

How can I model a problem as an MDP if the agent does not follow the successive order of states?

In my problem, the agent does not follow the successive order of states, but selects with $\epsilon$-greedy the best pair (state, action) from a priority queue. More specifically, when my agent goes ...
1
vote
0answers
22 views

Understanding example for Improved Policy Iteration for POMDPs

I was going through this paper by Hansen. This paper proposes policy improvement by first converting set of $\alpha$ vectors into finite state controller and then comparing them to obtain improved ...
0
votes
1answer
41 views

When we have multiple traces, do we average over traces or the total number of times we have visited that state?

I am confused about the workings of the first- and every-visit MC. My first question is, when we have multiple traces, do we average over traces or the total number of times we have visited that state?...
2
votes
1answer
56 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| ...
2
votes
1answer
31 views

Why is it useful to define the return as the sum of the rewards from time $t$ onward rather than up to $t$?

Why is it useful to define the return as the sum of the rewards from time $t$ onward rather than up to $t$? The return for an MDP is usually defined as $$G_t=R_{t+1}+R_{t+2}+ \dots +R_T$$ Why is this ...
5
votes
1answer
293 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/...
5
votes
1answer
61 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 ...
2
votes
0answers
45 views

Can $Q$-learning or SARSA be thought of a Markov Chain?

I might just be overthinking a very simple question but nonetheless the following has been bugging me a lot. Given an MDP with non-trivial state and action sets, we can implement the SARSA algorithm ...
16
votes
2answers
9k 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 ...
1
vote
2answers
671 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 ...
4
votes
1answer
291 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
305 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
174 views

Is the state transition matrix known to the agents in a Markov decision processes?

The question is more or less in the title. A Markov decision process consists of a state space, a set of actions, the transition probabilities and the reward function. If I now take an agent's point ...
4
votes
1answer
195 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 ...
1
vote
0answers
12 views

Relation between a value function of an MDP and a value function of the corresponding latent MDP

In paper "DeepMDP: Learning Continuous Latent Space Models for Representation Learning", Gelada et al. state in the beginning of section 2.4 The degree to which a value function of $\bar{\...
0
votes
0answers
11 views

What are some good use cases of Inference in Hybrid Domains (Logical + Continuous)?

So this question pertains to Statistical Relational Learning. Specifically in domains where you have a Knowledge base with probabilistic facts, you may think something like a Markov Logic Networks (...
8
votes
3answers
1k 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 ...
1
vote
1answer
87 views

Bellman optimality equation in semi Markov decision process

I wrote a Python program for a simple inventory control problem where decision epochs are equally divided (every morning) and there is no lead time for orders (the time between submitting an order ...
0
votes
0answers
40 views

Does Multi-Agent Deep Deterministic Policy Gradient also work with discrete action spaces?

I would like to ask if Multi-Agent Deep Deterministic Policy Gradient (MADDPG) works fine with discrete action space. DDPG works only with continuous action space, but I have read that MADDPG can also ...
1
vote
0answers
29 views

Customized food for persons based on their profile using Reinforcement learning

I am newbie to Reinforcement Learning, this is my idea - Agent(food provider) has to select a food based on the environment(based on the user profile). Here the reward will be given to the agent based ...
3
votes
2answers
948 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? ...
1
vote
2answers
149 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, ...
1
vote
1answer
48 views

Why is the optimal policy for an infinite horizon MDP deterministic?

Could someone please help me gain some intuition as to why the optimal policy for a Markov Decision Process in the infinite horizon case (agent acts forever), deterministic? Thank you!
2
votes
1answer
67 views

Is a policy in reinforcement learning analogous to a field such as APF?

If a policy maps states to actions in reinforcement learning, then for a path planning with obstacles, can't we simply use Artificial Potential Field fields for path planning and model policy ...
2
votes
0answers
56 views

If the performance of an RL agent in a partially observable environment is “good”, is this likely only accidental?

In my research, I remember to have read that, in case of an environment which can be modeled by partially observable MDP, there are no convergence guarantees (unfortunately, I do not find the paper ...
2
votes
1answer
70 views

Reinforcement learning with action consisting of two discrete values

I'm new to reinforcement learning. I have a problem where an action is composed of an order (rod with a required length) and an item from a warehouse (an existing rod with a certain length, which will ...
1
vote
0answers
46 views

Correct dimensionality of parameter vector for solving an MRP with linear function approximation?

I'm in the process of trying to learn more about RL by shadowing a course offered collaboratively by UCL and DeepMind that has been made available to the public. I'm most of the way through the course,...
1
vote
2answers
72 views

How do I calculate the return given the discount factor and a sequence of rewards?

I know that $G_t = R_{t+1} + G_{t+1}$. Suppose $\gamma = 0.9$ and the reward sequence is $R_1 = 2$ followed by an infinite sequence of $7$s. What is the value of $G_0$? As it's infinite, how can we ...