Motivation
Markov decision processes assume that the transition law is known exactly. In practice it is estimated from data, and the optimal policy computed for the point estimate can perform badly when the true law differs. Robust dynamic programming replaces each transition law by a set of plausible laws and evaluates a policy by its worst-case expected reward over that set. The worst case is taken against an adversary (nature) who may choose a law from the set at every step.
For this worst case to be computable by backward induction, the set of path measures of a policy has to decompose epoch by epoch. Garud Iyengar named this property Rectangularity and proved that under it the classical finite horizon theory carries over: a robust Bellman equation holds, and deterministic Markov policies are optimal among all history dependent randomized policies, with state and action sets that may be countably infinite and ambiguity sets that need not be convex (Iyengar, CORC Tech Report TR-2002-07, rev. 2004; published in Math. Oper. Res. 30(2), 2005).
Timeline:
- 1973: Satia and Lave study Markov decision processes with uncertain transition probabilities, finite states and actions (Oper. Res. 21(3)).
- 2001: Epstein and Schneider axiomatize recursive multiple priors, the decision-theoretic origin of rectangular ambiguity (J. Econ. Theory 113, working paper 2001).
- 2002–2005: Nilim and El Ghaoui give a robust counterpart of the Bellman recursion for finite state and action spaces and convex ambiguity sets, against Markov controllers (Oper. Res. 53(5)).
- 2002–2005: Iyengar proves the robust Bellman equation and Markov optimality for countable spaces, arbitrary ambiguity sets and all history dependent randomized policies, under Rectangularity.
Setting
A finite horizon ambiguous Markov decision process (AMDP) has decision epochs t∈T={0,…,N−1}, N≥1, and a terminal epoch N. States lie in a countable set S and actions in a countable set A. In state s at epoch t the admissible actions form a nonempty set At(s). For each admissible action a, the next state is drawn from some probability measure p∈Pt(s,a), where Pt(s,a) is a nonempty set of probability measures on S, the ambiguity set. The decision maker receives rt(s,a,s′) when a is taken in s and the next state is s′, and rN(s) at the terminal epoch.
A history at epoch n is hn=(s0,a0,…,sn−1,an−1,sn). A policy π=(dt) assigns to each history ht a probability measure dt(ht) on At(st). It is deterministic (ΠD) if every dt(ht) is a point mass, and deterministic Markov (ΠMD) if moreover the chosen action depends on the current state st alone. Π denotes all history dependent randomized policies.
Under Rectangularity (Assumption 1), the set Tπ of path measures consistent with π is a product of one-epoch sets: nature chooses, for every epoch t, every history ht and every admissible action a, a measure pht,a∈Pt(st,a), and the path measure is P(hN)=∏tdt(ht)(at)pht,at(st+1). The robust value of π from hn and the robust value function are
Vnπ(hn)=P∈TnπinfEP[t=n∑N−1rt(st,at,st+1)+rN(sN)],Vn∗(hn)=π∈ΠsupVnπ(hn).
The optimistic values Vˉnπ, Vˉn∗ replace the infimum over Tnπ by a supremum.
Formalization targets
Goal: Theorem 2 (Markov optimality)
For n=0,…,N, Vn∗(hn) depends on hn only through sn; for n∈T, Vn∗(sn)=supπ∈ΠMDVnπ(sn); and
Vn∗(s)=a∈An(s)sup p∈Pn(s,a)infEp[rn(s,a,s′)+Vn+1∗(s′)],n∈T.(16)
Milestones
- Proof of Theorem 1, eq. (15): at one epoch, randomizing over actions does not raise the worst-case value, and the adversary may choose its measure separately per action.
- Theorem 1 (Bellman equation): VN∗(hN)=rN(sN) and Vn∗(hn)=supainfp∈Pn(sn,a)Ep[rn(sn,a,s)+Vn+1∗(hn,a,s)] (11).
- Corollary 1: Vn∗(hn)=supπ∈ΠDVnπ(hn) for n∈T.
- Theorem 3: the optimistic analogue of Theorem 2, with recursion (18) in which both the outer and the inner optimizations are suprema.
The mission also contains, as a draft theorem that is not a milestone, the per-policy identity of the proof of Theorem 1, eq. (12): for each policy, Vnπ(hn)=infp∈TdnEp[rn+Vn+1π(hn,an,sn+1)].
Significance
Theorem 2 is the basis of robust dynamic programming in finite horizon: computing an optimal robust policy reduces to N backward passes, each a family of one-stage problems infp∈Pn(s,a)Ep[v]. It also justifies restricting attention to deterministic Markov policies, which is what every algorithm in the robust MDP literature computes. Theorem 1 isolates the role of Rectangularity: without it the worst case over path measures does not decompose and the recursion characterizes nothing.
The results are proved on paper; no machine-checked proof is known. The platform holds the finite-state, Markov-controller special case (the Nilim–El Ghaoui RobustMDP series, posed, not proved), whose comparison class is too small to express the claim ΠMD suffices against Π. A formal proof here supplies the history dependent policy and adversary machinery on countable spaces that the discounted robust theory and the robust MDP literature reuse.
Difficulty
The obvious argument writes the robust value as an inf–sup over path measures and pushes the infimum inside the expectation epoch by epoch. That step is the content of (12): the infimum of an expectation equals the expectation of an infimum only because nature's continuation choice may depend on the realized action and next state, so near-worst continuations for different branches can be glued into one admissible adversary. Infima need not be attained (the ambiguity sets are arbitrary, the state set countable), so the gluing is an ϵ-argument over countably many branches. The supremum over policies needs a matching splicing of ϵ-optimal continuation policies (13)–(14). Finally, randomized decision rules must be eliminated (15), which uses Rectangularity again, now per action. Restricting either the policies or the adversary to Markov ones from the start is not allowed: it changes the comparison class and makes the goal circular.
Formalization scope
- One countable state type
S and one countable action type A serve all epochs; the page's epoch-dependent sets St embed into their disjoint union. Epochs are 0-based natural numbers, with terminal epoch M.N and 1 ≤ N.
- A history at epoch n is
(Fin n → S × A) × S. Probability measures are PMF; Ep[f]=∑sp(s)f(s) as a tsum. The expected reward under a policy and an adversary is computed by backward iterated sums, which is the expectation under the product path measure (3).
- A policy is a decision rule for every epoch, admissible for
t < N; the supremum over Π equals that over the page's Πn because Vnπ uses only dn,…,dN−1. An adversary chooses pht,a∈Pt(st,a) for every epoch, history and admissible action.
- Added and implicit hypotheses: At(s)=∅ and Pt(s,a)=∅ (implicit on the page), and a uniform bound ∣rt∣≤R, ∣rN∣≤R (added: Section 2 states none, but with countable states the expectations and the real suprema and infima need it). All values then lie in a bounded interval, so no supremum or infimum is a junk value.
- Ambiguity sets are arbitrary nonempty sets of measures: no convexity, closedness or attainment is assumed anywhere.
- "Vn∗ is a function of the current state alone" is stated as the existence of W(n,s) with Vn∗(hn)=W(n,sn); the value is not defined on states, which would hide the claim. The notation Vnπ(sn) for Markov policies is made explicit as a clause.
- Ruled out: restricting Π or the adversary to Markov or stationary objects, a static adversary that fixes one p per (s,a) for the whole horizon, and suprema over unbounded or empty families; each makes some target false or trivial.
Definitions: AMDP, History, History.extend, IsPolicy, Policy, IsDeterministic, IsDetMarkov, Adversary, Selection, expect, expTail, expectedReward, V, Vstar, Vbar, VbarStar, all in RobustDP.FiniteHorizon. Lemmas about gluing adversaries along history prefixes and about suprema of bounded families indexed by subtypes are reusable. Contributions to any milestone are welcome, in any order; (15) is a one-epoch statement independent of the rest.
Selected references
- G. Iyengar, Robust dynamic programming, CORC Tech Report TR-2002-07, Columbia University, revised May 4, 2004; Math. Oper. Res. 30(2):257–280, 2005. https://doi.org/10.1287/moor.1040.0129
- A. Nilim and L. El Ghaoui, Robust control of Markov decision processes with uncertain transition matrices, Oper. Res. 53(5):780–798, 2005. https://doi.org/10.1287/opre.1050.0216
- J. K. Satia and R. E. Lave, Markovian decision processes with uncertain transition probabilities, Oper. Res. 21(3):728–740, 1973. https://doi.org/10.1287/opre.21.3.728
- L. G. Epstein and M. Schneider, Recursive multiple-priors, J. Econ. Theory 113(1):1–31, 2003. https://doi.org/10.1016/S0022-0531(03)00097-8
- M. L. Puterman, Markov Decision Processes: Discrete Stochastic Dynamic Programming, Wiley, 1994. https://doi.org/10.1002/9780470316887