Related Experiment Video
Updated: Jun 2, 2026
12:59
Barnes Maze Testing Strategies with Small and Large Rodent Models
Published on: February 26, 2014
No good Markov strategies for Büchi objectives in countable MDPs
Stefan Kiefer1, Richard Mayr2, Mahsa Shirmohammadi3
1University of Oxford, Oxford, United Kingdom.
Annals of Operations Research
|June 1, 2026
Summary
We investigated Markov decision processes with Büchi objectives. Our findings show that epsilon-optimal Markov strategies do not always exist for these infinite processes, contrary to a long-standing question.
Area of Science:
- Decision theory
- Theoretical computer science
- Stochastic processes
Background:
- Markov decision processes (MDPs) are models for sequential decision-making.
- Büchi objectives require visiting a specific set of states infinitely often.
- The existence of epsilon-optimal Markov strategies for infinite MDPs with Büchi objectives was an open question.
Purpose of the Study:
- To address the open question regarding the existence of epsilon-optimal Markov strategies in countably infinite Markov decision processes with Büchi objectives.
Main Methods:
- Constructing a non-trivial counterexample.
- Analyzing the properties of Markov strategies in infinite state spaces.
Main Results:
- Demonstrated that epsilon-optimal Markov strategies do not always exist for countably infinite Markov decision processes with Büchi objectives.
- Provided a specific counterexample to T.P. Hill's (1979) conjecture.
Conclusions:
- The assumption that epsilon-optimal Markov strategies always exist for infinite MDPs with Büchi objectives is false.
- This result has implications for the design and analysis of optimal control policies in stochastic systems.
Related Concept Videos
01:29Mechanistic Models: Compartment Models in Algorithms for Numerical Problem Solving
Mechanistic models play a crucial role in algorithms for numerical problem-solving, particularly in nonlinear mixed effects modeling (NMEM). These models aim to minimize specific objective functions by evaluating various parameter estimates, leading to the development of systematic algorithms. In some cases, linearization techniques approximate the model using linear equations.
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
In individual population analyses, different algorithms are employed, such as Cauchy's method, which uses a...
01:21Mechanistic Models: Overview of Compartment Models
Mechanistic models, a category encompassing both physiological and compartmental modeling, differ from empirical models' approaches to incorporating known factors about the systems being modeled. Empirical models describe data with minimal assumptions, while mechanistic models aim to provide a robust description of available data by specifying assumptions and integrating known factors about the system. Compartmental analysis is a key example of a mechanistic model in pharmacokinetics and...
01:29Mathematical Modeling: Problem Solving
Mathematical modeling transforms real-world scenarios into mathematical expressions, allowing for structured problem-solving and analysis. This process involves defining the situation, assigning variables to measurable quantities, selecting an appropriate model, and solving the resulting equation. Such models are invaluable in finance, providing precise methods to evaluate investments, loans, and repayment structures.A widely used example is the calculation of fixed monthly payments on a loan,...
01:31Alternative Sets of Equilibrium Equations
When analyzing the behavior of structures, engineers often rely on the concept of equilibrium. This refers to the state where all forces and moments acting on a system balance each other, resulting in no net movement or rotation. In many cases, equilibrium can be described by a set of standard equations. However, in some situations, alternative sets of equilibrium equations must be used to describe the system's behavior accurately.
One example of such a situation can be observed in a...
One example of such a situation can be observed in a...
01:24BIBO stability of continuous and discrete -time systems
System stability is a fundamental concept in signal processing, often assessed using convolution. For a system to be considered bounded-input bounded-output (BIBO) stable, any bounded input signal must produce a bounded output signal. A bounded input signal is one where the modulus does not exceed a certain constant at any point in time.
To determine the BIBO stability, the convolution integral is utilized when a bounded continuous-time input is applied to a Linear Time-Invariant (LTI) system.
To determine the BIBO stability, the convolution integral is utilized when a bounded continuous-time input is applied to a Linear Time-Invariant (LTI) system.
01:13Stability of Equilibrium Configuration: Problem Solving
The stability of equilibrium configurations is an important concept in physics, engineering, and other related fields. In simple terms, it refers to the tendency of an object or system to return to its equilibrium position after being disturbed. The stability of an equilibrium configuration can be analyzed by considering the potential energy function of the system and examining its behavior near the equilibrium point.
Problem-solving in the context of the stability of equilibrium configuration...
Problem-solving in the context of the stability of equilibrium configuration...