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.

43 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
4
votes
0answers
115 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 ...
3
votes
0answers
33 views

Why do we discount the state distribution?

In Reinforcement Learning, it is common to use a discount factor $\gamma$ to give less importance to future rewards when calculating the returns. I have also seen mention of discounted state ...
3
votes
0answers
30 views

Relationship between the reward rate and the sampled reward in a Semi-Markov Decision Process

In the paper: Reinforcement learning methods for continuous-time Markov decision problems, the authors provide the following update rule for the Q-learning algorithm, when applied to Semi-Markov ...
3
votes
0answers
105 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
0answers
53 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.
3
votes
0answers
228 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 ...
3
votes
0answers
41 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 ...
2
votes
0answers
29 views

Is there any reasonable notion of regret for infinite horizon discounted MDPs?

I am thinking about episodic MDPs. Usually, in episodic MDPs, it seems that we have a finite fixed horizon per episode and no discount factor. Then, a very intuitive notion of regret after $T$ ...
2
votes
1answer
21 views

Is there a way of path reconstruction using only the history of belief state?

Given a history of belief states, is there a common method that backtracks the most likely path of ending up in the current belief state? I have a Markov model which calculates belief states after ...
2
votes
0answers
22 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 ...
2
votes
0answers
36 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. ...
2
votes
0answers
23 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 \...
2
votes
0answers
49 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 ...
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
0answers
66 views

Can we use a Gaussian process to approximate the belief distribution at every instant in a POMDP?

Suppose $x_{t+1} \sim \mathbb{P}(\cdot | x_t, a_t)$ denotes the state transition dynamics in a reinforcement learning (RL) problem. Let $y_{t+1} = \mathbb{P}(\cdot | x_{t+1})$ denote the noisy ...
2
votes
0answers
53 views

How are the classical MDP and the object-oriented MDP views different?

I've been reading the attached paper - which aims to model entities in the world as objects, including the learning agent itself! To say the least, the goal is to navigate through what seems like a ...
2
votes
0answers
31 views

How can I formalise a non-zero-sum game of $N$ agent as Markov game?

I coded a non-zero-sum game of $N$ agents in a discrete dynamic environment to RL with Q-learning and DQN agents. It's like a marathon. Only two actions are available per agent: $\{ G \text{ (move ...
2
votes
0answers
27 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 ...
2
votes
0answers
33 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}$), ...
2
votes
0answers
73 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
39 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 ...
2
votes
0answers
24 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 ...
1
vote
0answers
57 views

Relation between discounted MDP and stochastic shortest path problems in RL

I have been reading about discounted MDPs and Stochastic Shortest Path (SSP). I recently came to know (from a friend) that every discounted MDP can be converted to an equivalent SSP but not the other ...
1
vote
0answers
23 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 ...
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{\...
1
vote
0answers
30 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 ...
1
vote
0answers
48 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
0answers
38 views

State-of-the-art algorithms not working on a custom RL environment

I'm trying to train a RL agent on a custom, highly stochastic environment (MDP). In order to do so I'm using existing implementations of state-of-the-art RL algorithms as provided by Stable Baselines. ...
1
vote
0answers
61 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
52 views

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
24 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 ...
1
vote
0answers
37 views

How do I determine the optimal policy in a bandit problem with missing contexts?

Suppose 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 ...
1
vote
0answers
48 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. ...
1
vote
0answers
50 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
0answers
63 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}$, $...
0
votes
0answers
27 views

Double DQN backpropagation of negative final rewards?

My problem is that in my Double DQN model, negative final rewards are not being backpropagated into action Q-values, and so some Q-values are positive, when they should be negative, and hence ...
0
votes
1answer
48 views

What is the difference between environment states and agent states in terms of Markov property?

I'm going through the David Silver RL course on YouTube. He talks about environment internal state $S^e_t$, and agent internal state $S^a_t$. We know that state $s$ is Markov if $\mathbb{P}\{S_t=s|S_{...
0
votes
0answers
7 views

What is an appropriate stop criteria for training on a non-stationary environment in reinforcement learning?

I'm currently studying reinforcement learning (RL) and would like to understand non-stationary environments better. So for stationary environments, the Q-values of all state-action pairs converge ...
0
votes
0answers
12 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 (...
0
votes
0answers
49 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 ...
0
votes
0answers
33 views

Why Q-Learning and SARSA have terrible performance?

I am trying to solve a MDP problem with almost 50 states and 60 actions with Q-Learning or SARSA. However, the performance of both algorithms is terrible and cannot find the optimal policy found by ...
0
votes
0answers
45 views

Model Based rl and cross entropy method with nonlinear function approximators

Pseudo code for Cross entropy method according to youtube lecture 32:55 Initialize $\mu \in R^{d}, \sigma \in R^{d}$ iteration 1,2,... Collect n samples of $\theta_{i} \sim N(\mu,diag(\sigma))$ ...
0
votes
0answers
59 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=(...