PaperlayerView exact revision on arXiv

Source-linked AI summary

Partially Observed Markov Decision Processes. Problem Sets and Internet Supplement

Vikram Krishnamurthy

arXiv:1604.08127v1math.OC

TL;DR

This internet supplement provides exercises, examples, and case studies related to partially observed Markov decision processes, including material placed outside the book for ongoing updates. Its content emphasizes mini-research exercises and extensions addressing control, filtering, structural results, and related topics.

  • Problem

    The supplement addresses the need for additional exercises, examples, and case studies to assist understanding of the book's material.

  • Method

    It uses mini-research exercises, examples, and case studies, including extensions of material presented in the book.

  • Results

    The supplement provides exercises and case studies covering POMDP control, filtering, structural results, optimal policies, and related problems.

  • Takeaways & Limitations

    The document serves as an evolving resource for understanding partially observed Markov decision processes through additional problems and pedagogical material.

  • Takeaways & Limitations

    Some stated structural results have scope boundaries, including a theorem that does not apply beyond the trivial case where the observation matrices are equal.

Abstract

from arXiv · show

This document is an internet supplement to my book "Partially Observed Markov Decision Processes - From Filtering to Controlled Sensing" published by Cambridge University Press in 2016. This internet supplement contains exercises, examples and case studies. The material appears in this internet supplement (instead of the book) so that it can be updated. This document will evolve over time and further discussion and examples will be added. This internet supplement document is work in progress and will be updated periodically. I welcome constructive comments from readers of the book and this internet supplement.

Preface to Internet Supplement

The internet supplement extends the book with updateable exercises, examples, case studies, and software-supported problems across stochastic models and filtering. Its exercises range from proving foundational results to simulation and algorithmic comparisons.

  • Purpose: The supplement contains exercises, examples, and case studies that can be updated over time.It is intended to evolve with additional discussion and examples.
  • Resources: Downloadable software and MATLAB interfaces support solving POMDPs with nonlinear information-state costs and bandit problems.The website also provides several POMDP examples.
  • Purpose: The exercises are mainly mini-research problems rather than simplistic drills, including extensions of the book’s material.The author also plans additional case studies and pedagogical notes.
  • Exercises: The problem sets ask readers to prove stationary-distribution results using Farkas’ lemma and simulate state-space and filtering models.Examples include maneuvering-target dynamics, optimal prediction, and Lyapunov stability.
  • Exercises: Other exercises study ergodicity through spectral, Dobrushin, and Wasserstein tools, including how powers of a transition matrix can yield useful contraction bounds.The supplement connects variational distance and Dobrushin coefficients through the discrete metric.

Optimal Filtering

The supplement presents filtering and Bayesian-estimation exercises spanning Lasso, pulse de-interleaving, jump Markov systems, stochastic grammars, and HMM sensitivity. It also gives explicit bounds for filters using different transition matrices.

  • Bayesian estimation: Bayesian estimation exercises connect Lasso posteriors, noisy pulse de-interleaving, and jump Markov linear-system formulations.Pulse de-interleaving estimates source periods and phases from noisy arrival times.
  • Stochastic grammars: Stochastic context-free grammars extend finite-observation HMMs and can represent strings whose variable memory cannot be generated exclusively by a Markov chain.Stochastic parsing is described as a polynomial-cost method for estimating noisy underlying strings.
  • Comparative filtering: The supplement proposes numerical comparisons between HMM filters and Kalman filters, as well as between several nonlinear and particle-filtering methods.The exercises include IMM, unscented Kalman, particle-filter, fixed-lag-smoothing, and recursive-least-squares comparisons.
  • Sensitivity analysis: Filter sensitivity analysis bounds the difference between filtered distributions when transition matrices differ by at most ε in induced 1-norm.The stated results include expected one-step deviations and recursive L1 bounds.
  • Sensitivity analysis: The sensitivity bounds use the observation-law measure σ(π, y; P) and the Dobrushin coefficient to control recursive filtering differences.The theorem’s proof invokes the submultiplicative property of the Dobrushin coefficient.

Algorithms for Maximum Likelihood Parameter Estimation

The section introduces maximum-likelihood estimation in an abstract measure-theoretic setting and motivates EM as an iterative approximation when direct MLE computation is difficult.

  • MLE setup: A family of probability measures and available information define the likelihood used to estimate the parameter θ.The setup assumes absolute continuity with respect to a fixed probability measure.
  • MLE setup: The maximum-likelihood estimate is defined by maximizing the likelihood over the parameter space.
  • EM algorithm: EM provides an iterative approximation method because direct computation of the MLE is generally difficult.The iteration replaces the current parameter index and repeats until a stopping condition.
  • EM algorithm: The generated parameter sequence has non-decreasing likelihood values by Jensen’s inequality.

CHAPTER 4. ALGORITHMS FOR MAXIMUM LIKELIHOOD PARAMETER ESTIMATION15

The exercises extend maximum-likelihood and EM ideas to linear Gaussian models, sinusoidal HMMs, jump Markov systems, social learning, and data-incest removal. They emphasize estimation, computational cost, risk sensitivity, and simulation-based comparison.

  • EM extensions: Forward-only EM algorithms for linear Gaussian state-space models use filters for state functionals and Kalman-filter estimates.
  • EM extensions: A sinusoid observed with iid Gaussian noise is used to formulate an EM exercise for estimating amplitude, phase, Markov-chain parameters, and noise variance.
  • Computational efficiency: The exercises ask whether forward-only EM filter costs of O(X^4) for jump counts and O(X^3) for duration times can be reduced by approximation.
  • Social learning: Social-learning exercises examine simulation, multinomial sampling, CVaR risk aversion, coherent risk measures, and conditions under which agents herd.The CVaR parameter α controls risk aversion, with smaller α representing greater risk aversion.
  • Data incest: Data-incest exercises study graph-based exact removal, Gaussian comparisons with covariance intersection, consensus methods, communication labels, and bias.

Fully Observed Markov Decision Processes

The supplement develops fully observed stopping, discounted, and Markov-game formulations, including feedback equivalences and equilibrium results. It emphasizes that Nash equilibria exist in finite discounted Markov games, while computation is generally difficult but becomes tractable in special zero-sum cases.

  • Feedback and open-loop formulations can generate identical state and observation sequences in deterministic systems.
  • In fully observed stochastic feedback control, the feedback input can produce zero-mean states with variance σ2.
  • Stopping-time problems: An investor’s finite-horizon call-option exercise problem is formulated as a fully observed stopping-time problem with an augmented state recording whether exercise has occurred.
  • Discounted problems: Random termination with continuation probability ρ converts an undiscounted cost problem into a discounted-cost formulation.
  • Markov games: For finite-state, finite-action discounted Markov games, at least one Nash equilibrium exists within stationary randomized Markov policies.
  • Markov games: Computing equilibria is generally difficult, but a zero-sum discounted Markov game has a unique value function even when multiple saddle points exist.

Partially Observed Markov Decision Processes (POMDPs)

The supplement provides downloadable POMDP software and example problems, including a three-state simulation exercise, approximate-policy comparison, and the tiger problem.

  • The website provides downloadable software for solving POMDPs and several POMDP examples.
  • Suggested exercises include simulating dynamic programming on a quantized three-state belief grid and comparing Lovejoy’s suboptimal algorithm with the optimal policy.
  • The tiger problem uses two hidden door states, two observations, and three actions: open the left door, open the right door, or listen.

CHAPTER 7. PARTIALLY OBSERVED MARKOV DECISION PROCESSES (POMDPS)26

This chapter frames adaptive control and estimation as POMDPs by augmenting the state with an unknown, static model parameter and updating its posterior belief. It also highlights exact POMDP solution properties and the estimation–control trade-off of dual control.

  • POMDP formulation: The tiger problem has state and observation sets {l, r} and action set {l, r, h}.
  • Belief-space exercises: Uniform sampling from the belief simplex Π(X) can be obtained by normalizing independent unit-exponential variables, equivalently using a Dirichlet distribution.
  • Adaptive control: Adaptive control with unknown transition matrices is formulated as a POMDP whose augmented state is (xk, θk), with θk static but partially observed.
  • Adaptive control: The controller’s belief πk(l)=P(θk=l|Hk) is updated from the observed trajectory and serves with xk as the belief state.
  • Adaptive control: The resulting value function is piecewise linear and concave in the model-parameter belief, and exact POMDP algorithms can compute the optimal policy.
  • Dual control: Dual control captures the trade-off between estimation and control: uncertainty can motivate more aggressive probing, whereas certainty permits less aggressive control.

POMDPs in Controlled Sensing and Sensor Scheduling

The supplement applies POMDPs to controlled sensing, constrained sensor scheduling, adaptive control, and structural MDP results. It derives belief-state dynamic programs and gives monotonicity, lower-bound, and switching-policy conclusions under explicit structural conditions.

  • Controlled sensing: Moving sensors can be modeled as a POMDP that chooses observer trajectories to locate a Markovian target from noisy, distance-dependent measurements.
  • Sensor scheduling: A finite-horizon sensor-usage constraint is represented through Bellman equations with boundary conditions for using a sensor at most or exactly L times.
  • Sensor scheduling: The at-most-L sensor constraint can be incorporated in POMDP software by augmenting the state with a controlled counter process.
  • Structural MDP results: Under relaxed transition conditions, the myopic policy is a lower bound on the optimal policy: µ∗(i) ≥ µ(i).
  • Structural MDP results: A monotone policy remains compatible with policy iteration because evaluation preserves the relevant vector ordering and improvement yields another monotone policy.
  • Structural MDP results: For stochastic knapsack replacement, the optimal policy switches from brand 1 to brand 2 and then later brands as the remaining time increases.
  • Structural MDP results: Finite-horizon supermodularity conditions provide a route to monotonicity of the optimal policy with respect to state, action, and horizon.

Structural Results for Optimal Filters

This section develops structural results for filtering and decision problems, including stochastic-order limitations, threshold detectors, monotone policies, and convex or nested stopping regions. It also presents exercises on POMDP value functions, stopping-time problems, sensing, and related extensions.

  • Threshold detection: The Neyman–Pearson rule maximizes Q subject to P ≤ α, and under MLR dominance the optimal detector has a threshold structure.The threshold condition is expressed through the likelihood ratio f(x)/g(x).
  • Value-function structure: The structural-results exercises ask how MLR-based value-function results extend to nonlinear costs, shifted likelihood-ratio order, action-dependent observations, and dynamic risk measures.
  • Stopping-time POMDPs: Stopping-time POMDPs have convex stopping sets, while additional conditions can yield an explicit polytope characterization and nested finite-horizon sets S0 ⊆ S1 ⊆ S2 . . ..The exercises also ask for conditions on transition and observation models that support the explicit characterization.
  • Sensing and stopping: Optimal measurement and channel-sensing exercises formulate observation selection as stopping-time POMDPs, update beliefs after observations, and investigate convex sensing regions.
  • Monotone policies: The supplement also states that under suitable conditions the Bayesian Nash equilibrium policy is monotone increasing in the observation and therefore has a threshold form.

Stopping Time POMDPs for Quickest Change Detection

Classical Bayesian sequential detection reduces to a two-state stopping-time POMDP whose belief-state stopping regions are intervals, leaving an interval of beliefs where measurement continues.

  • The model has two hidden states, identity state transition matrix, noisy observations, two stopping actions, and a measurement action.
  • Misclassification costs penalize declaring state 1 when the state is 2, or declaring state 2 when the state is 1.
  • The belief state is π = [π(1), π(2)]′, and the observation space may be finite or continuous.
  • The stopping regions R1 and R2 are convex and therefore intervals when represented by π(2) on [0,1].
  • The regions take the form R1 = [0, π∗1] and R2 = [π∗2, 1], with a continue region [π∗1, π∗2].
  • The general theorem applies beyond this example to more than two states and evolving Markov states.

CHAPTER 13. STOPPING TIME POMDPS FOR QUICKEST CHANGE DETECTION 44

This section introduces an order-book model of high-frequency trading in which agents combine social information from previous decisions with private noisy signals.

  • The model studies risk-averse agents who buy or sell stocks using order-book information about previous decisions and private noisy signals.
  • The stated aims include modeling agent dynamics and sequentially detecting a market-related quantity.

Myopic Policy Bounds for POMDPs and Sensitivity

The supplement examines bounds, dominance conditions, sensitivity questions, and recursive optimization methods for POMDPs and related hidden-state models. It also highlights where structural results require restrictive observation assumptions.

  • Myopic Policy Bounds: Changing the cost vector while preserving the optimal policy is proposed as a way to seek tighter upper and lower policy bounds.
  • Myopic Policy Bounds: A proposed pair of transition and observation inequalities cannot hold nontrivially when only observation probabilities depend on action and transition probabilities are identical.
  • Myopic Policy Bounds: Blackwell dominance is introduced for cases where the preceding observation-based theorem does not apply.
  • Sensitivity and Limitations: Allowing p(y(1)|y(2), x) to depend on state x destroys the probability-measure property needed by the proof, so the theorem no longer follows.
  • Sensitivity and Limitations: Under a different factorization involving p(y(2)|x_k, x_{k−1}) and p(y(1)|y(2)), the proof continues to hold.
  • Recursive Optimization: The material also formulates recursive gradient and Gauss–Newton procedures based on filtering recursions and successive model estimates.

1. Recursive EM algorithm1

The supplement develops recursive EM, prediction-error, and stochastic search-ruler procedures for hidden Markov model estimation and stochastic optimization. These methods use filtering-based recursions, normalized costs, and variance-reduction ideas.

  • Recursive EM: The recursive EM construction starts from the auxiliary likelihood and uses transition and observation matrices in a recursive Gauss–Newton stochastic-gradient update.
  • Recursive EM: The recursive EM update has a plus sign because it maximizes a reward rather than minimizes a loss.
  • Recursive EM: Transition-matrix estimates can be constrained to remain stochastic by parameterizing them with spherical coordinates.
  • Prediction-Error Estimation: Recursive prediction-error estimation differs from recursive EM because its cost depends on derivatives of the HMM filter with respect to model parameters.
  • Stochastic Search-Ruler: The stochastic search-ruler algorithm compares normalized sample costs against independent uniform random numbers and is designed to search over discrete candidates.
  • Stochastic Search-Ruler: Theorem 8 characterizes the stationary distribution of the search-ruler Markov chain, while the algorithm is attracted to global minimizers and spends more time there than at other candidates.
  • Variance Reduction: Using common random numbers yields a variance-reduced variant with Var{Zn(θ, un)} ≤ Var{Yn(θ, un)}, which is expected to converge faster.

Index

The index catalogs topics spanning POMDPs, HMMs, detection, estimation, control, games, optimization, and learning. It also lists structural results, equilibrium concepts, sensing problems, and stochastic-analysis tools.

  • POMDPs and control: The index covers POMDP topics including adaptive control, active hypothesis testing, dual control, stopping-time problems, separable models, and the tiger problem.
  • Estimation and signal processing: Estimation and signal-processing entries include HMMs, EM algorithms, recursive estimation, tracking, de-interleaving, interference, and jump Markov linear systems.
  • Structural and analytical tools: The index also lists structural and analytical tools such as threshold policies, dominance orders, Lyapunov functions, Wasserstein distance, differential inclusions, and sensitivity bounds.
  • Games and equilibria: Game-theoretic entries address Markov games, Nash and Bayesian Nash equilibria, correlated equilibria, global games, regret matching, and switched controllers.
  • Detection and sensing: Detection and sensing topics include Neyman-Pearson detection, Shiryaev statistics, channel sensing, observer trajectories, and coordinated sensing.
Loading 1604.08127v1…