Questions tagged [markov-decision-process]

For questions related to Markov decision processes (MDPs), which model decision making in time-varying and usually stochastic environments.

Filter by
Sorted by
Tagged with
1 vote
0 answers
35 views

LP programming of a Markov Decision Model

I am doing my thesis and I encounter the following issue last weeks, without solving it yet: I am trying to formulate a Markov Decision Process as an LP formulation, considering 2 items. (In the ...
Panagiotis Paspalas's user avatar
2 votes
0 answers
121 views

Is OCN=DOCN decidable?

One-Counter Nets (OCNs) are finite-state machines equipped with an integer counter that cannot decrease below zero and cannot be explicitly tested for zero. An OCN $A$ over alphabet $\sum$ accepts a ...
S. M.'s user avatar
  • 21
0 votes
1 answer
102 views

Analytic international relations

Here is the Saudi-Israel game framework as a Stack Exchange question with MathJax: game-theory markov-processes How can I model the dynamics of Saudi-Israel relations using a stochastic game with ...
Glimmer's user avatar
0 votes
0 answers
43 views

Creating a simple class in python for doing simulation of MDP

I am currently learning Python and doing object-oriented programming. I am trying to create a simulation for MDP. My problem statement is: "I have four stages of process. Each stage has two ...
Margi Shah's user avatar
3 votes
1 answer
225 views

Optimization for Stochastic Simulations

This questions stems from my original question here. I have a system, where each 'run' is a simulation of agents switching between tasks (or states) as in a Markov Chain. I would like to find ways to ...
Raghav Thakar's user avatar
1 vote
1 answer
111 views

(OR-Tools) Custom Function to Evaluate Intermediate Solutons

I have a system with $k$ tasks, where each task is a state in a Markov chain. I am working on allocating agents to each task. I would like to achieve a specific distribution of the agents among these ...
Raghav Thakar's user avatar
0 votes
1 answer
178 views

How to model history-dependent dynamic program?

Suppose there is a dynamic program that the state of the problem grows over time (more info is added to the state of the problem over time) and at each time, we need all historical data, full history, ...
Amin's user avatar
  • 2,150
1 vote
0 answers
46 views

How to check if the state of a dynamic program is Markovian or not?

Based on Markov chain context, we say a stochastic process is Markovian if the state at time $t+1$, $S_{t+1}$ just depends on the state in the previous step, that is, $\Pr\left( S_{t+1}|S_1, S_2, \...
Amin's user avatar
  • 2,150
2 votes
1 answer
331 views

Understanding MDP's Dual Linear Program

I'm trying to understand a proof in Puterman'05 (Markov Decision Processes: Discrete Stochastic Systems). My question is within Theorem 6.9.1 pertaining to the equivalence of solutions to the primal (...
Max's user avatar
  • 23
2 votes
0 answers
31 views

MDP model for a unique system

Let's assume that we have a system where there are two exogenous factors, name $a$ and $b$, that can affect the system state. At each decision epoch either $a$ or $b$ occurs and it is not possible ...
Shey's user avatar
  • 21
1 vote
0 answers
107 views

Markov Chain - Stationary or Borderline distribution [closed]

I have a Markov chain problem below, where : The problem An urn initially contains 3 black balls and 1 red ball. The balls are indistinguishable to the touch. One ball is randomly drawn. If this ball ...
user.mokho's user avatar
4 votes
0 answers
49 views

Equilibria in two player, finite horizon, zero sum stochastic game

Suppose we have a two player, finite horizon, zero sum stochastic game (a.k.a. "competitive MDP"). The game is defined over a finite set of state $S$. At each decision epoch $t\in\{1,\dots,T\}$ (for ...
David M.'s user avatar
  • 2,047
3 votes
1 answer
115 views

Queuing Theoretic Model with Memory

Consider a telephone company which receives call request at some arrival rate and serves each request with some service rate. This can be modeled using a Poisson Process. However I wish to model the ...
ephemeral's user avatar
  • 897
8 votes
1 answer
172 views

Can I use an MDP for a stochastic inventory model when my demand distribution is non-stationary?

Most formulations of Markov Decision Processes for stochastic inventory models I've come across assume a fixed demand distribution. But in my case I have a time series forecast with a non stationary ...
Skander H.'s user avatar
  • 2,089
12 votes
3 answers
1k views

Number of aircraft to operate in an airline company

Suppose that an airline company has X planes, in general the companies keep a number of these aircraft (say 80% of X) in reserve in case of hazards. My question is how the airline companies compute ...
user109284's user avatar
12 votes
1 answer
134 views

Model or State Uncertainty in Queueing Model due to uncertain arrival rate

Introduction I am currently modelling a scenario where two queues need to be served by a single server in a non preemptive discipline. I am quite sorted on generating the optimal policy via Value or ...
Dylan Solms's user avatar
11 votes
1 answer
346 views

Algorithm for workforce scheduling for call volumes

I am trying to solve a workforce scheduling and optimization problem. Available data: daily level forecasted call volumes, shift schedules, resource utilization at the aggregate level, AHT at ...
Lalitha Sundar Iyer S's user avatar
10 votes
2 answers
4k views

Infinite horizon versus finite horizon MDP

When can we approximate a finite horizon MDP with infinite horizon? Can we use infinite horizon stochastic shortest path problem on a directed acyclic graph?
David xuang's user avatar
9 votes
0 answers
211 views

For the solution of complex gaming are we to leave behind approximation and fixed algorithms in favor of agents?

For an evolutionary extensive form game is the use of multi-agent systems a necessity or can more traditional approximate Nash equilibria and mean-field interactions suffice? Few games can be ...
Rob's user avatar
  • 2,098
12 votes
1 answer
169 views

Open source Markov decision process solvers

Which sources are out there that provide reliable and fast MDP solvers? I prefer that the library is callable from C++ but other languages are fine too. There is indeed an abundance of repositories ...
Michiel uit het Broek's user avatar
8 votes
1 answer
379 views

Convergence rate value iteration

Value iteration is one of the most commonly used methods to solve Markov decision processes. Its convergence rate obviously depends on the number of states and actions. However, the convergence rate ...
Michiel uit het Broek's user avatar