PaperlayerView exact revision on arXiv

Source-linked AI summary

Variance Reduced Value Iteration and Faster Algorithms for Solving Markov Decision Processes

Aaron Sidford, Mengdi Wang, Xian Wu, Yinyu Ye

arXiv:1710.09988v3cs.DScs.LGmath.OC

TL;DR

The paper tackles the challenge of efficiently solving large discounted MDPs, where existing methods can scale super-linearly. It modifies approximate value iteration with sampling, variance reduction, and monotonic progress, yielding nearly linear-time and sublinear algorithms and extensions to finite-horizon MDPs. These algorithms improve runtime dependence on key MDP parameters and prior methods in multiple regimes.

  • Problem

    Efficiently solving large discounted MDPs remains challenging because the best known algorithms in many parameter regimes scale super-linearly with input size.

  • Method

    The paper combines approximate value iteration with sampling and variance reduction, using monotonic progress toward the optimal value in its fastest algorithms.

  • Results

    The resulting algorithms compute approximately optimal policies in nearly linear and sometimes sublinear time, improve dependence on |S|, |A|, and γ, and extend to finite-horizon MDPs.

  • Takeaways & Limitations

    The results provide new complexity benchmarks for solving discounted infinite-horizon MDPs and apply variance reduction to approximate value iteration for finite-horizon MDPs.

  • Takeaways & Limitations

    The sublinear algorithm requires a data structure supporting expected O(1)-time sampling from transition probabilities, while policy guarantees can incur an additional rounding penalty unless monotonic modifications are used.

Abstract

from arXiv · show

In this paper we provide faster algorithms for approximately solving discounted Markov Decision Processes in multiple parameter regimes. Given a discounted Markov Decision Process (DMDP) with $|S|$ states, $|A|$ actions, discount factor $γ\in(0,1)$, and rewards in the range $[-M, M]$, we show how to compute an $ε$-optimal policy, with probability $1 - δ$ in time \[ \tilde{O}\left( \left(|S|^2 |A| + \frac{|S| |A|}{(1 - γ)^3} \right) \log\left( \frac{M}ε \right) \log\left( \frac{1}δ \right) \right) ~ . \] This contribution reflects the first nearly linear time, nearly linearly convergent algorithm for solving DMDPs for intermediate values of $γ$. We also show how to obtain improved sublinear time algorithms provided we can sample from the transition function in $O(1)$ time. Under this assumption we provide an algorithm which computes an $ε$-optimal policy with probability $1 - δ$ in time \[ \tilde{O} \left(\frac{|S| |A| M^2}{(1 - γ)^4 ε^2} \log \left(\frac{1}δ\right) \right) ~. \] Lastly, we extend both these algorithms to solve finite horizon MDPs. Our algorithms improve upon the previous best for approximately computing optimal policies for fixed-horizon MDPs in multiple parameter regimes. Interestingly, we obtain our results by a careful modification of approximate value iteration. We show how to combine classic approximate value iteration analysis with new techniques in variance reduction. Our fastest algorithms leverage further insights to ensure that our algorithms make monotonic progress towards the optimal value. This paper is one of few instances in using sampling to obtain a linearly convergent linear programming algorithm and we hope that the analysis may be useful more broadly.

1 Introduction

The paper addresses the difficulty of solving large discounted MDPs efficiently by combining value iteration with sampling and variance reduction. It develops nearly linear-time and sublinear algorithms, extends them to finite-horizon MDPs, and reports improved runtime dependence on key parameters.

  • 1 Introduction: The algorithms combine classic value iteration with sampling and variance reduction to compute approximately optimal policies for discounted MDPs.The approach also uses monotonic progress toward the optimal value in its fastest algorithms.
  • 1 Introduction: The first algorithm has nearly linear convergence and runs in nearly-linear time when 1/(1 −γ) = O(|S|^1/3), including polynomially dependent discount factors.The paper describes this as the first provably nearly linear-time algorithm in that regime and says it matches or improves prior value-iteration dependence on |S|, |A|, and γ.
  • 1 Introduction: The second algorithm is sublinear in the Ω(|S|^2|A|) input size under expected O(1)-time transition sampling and improves dependence on 1/(1 −γ).It matches a prior runtime under fewer assumptions, without requiring ergodicity.
  • 1 Introduction: The algorithms extend to finite-horizon MDPs and are presented as the first application of variance reduction for approximate value iteration in that setting.The paper reports improved results over previous methods for approximately computing optimal policies for fixed-horizon MDPs in multiple parameter regimes.
  • 1 Introduction: Variance reduction estimates changes in transition-value expectations relative to previously computed baselines, lowering variance and the number of samples needed.The method trades off the frequency of baseline estimation against sampling differences between current and reference value vectors.

2 Previous Work

Previous work spans deterministic value iteration, policy iteration, linear programming, and sampling-based methods for DMDPs, with runtime and approximation guarantees varying across parameter regimes. The paper positions its results against these methods and recent lower bounds.

  • Deterministic Methods: Deterministic DMDP methods include value iteration, policy iteration, and linear programming, with extensive analyses of convergence, exact solution, and polynomial-time behavior.Value iteration uses successive approximation, while policy iteration and simplex-based methods have strongly polynomial analyses in relevant settings.
  • Approximate Linear Programming: Approximate linear programming offers many methods, but converting approximate LP solutions into approximate values and policies requires care because approximate values do not necessarily yield approximate policies.The paper gives an illustrative conversion using interior-point methods in an appendix.
  • Runtime Comparisons: The paper’s comparison tables summarize exact and high-probability approximate DMDP runtimes across deterministic and sampling-based methods.The tables parameterize complexity using state count, actions per state, discount factor, reward bound, and, for exact methods, LP complexity.
  • Sampling-Based Methods: Sampling-based MDP research has emphasized sample complexity and reinforcement-learning settings, where explicit runtime accounting is often not central because sampling costs vary by oracle model.The paper relates its randomized algorithms to generative models that permit transition sampling for specified state-action pairs.
  • Position Relative to Prior Work: The paper reports sharp dependence on |S|, |A|, and γ, while prior work establishes lower bounds of Ω(|S|^2|A|) generally and Ω(|S||A|...) when transitions can be sampled quickly.Its main result nearly matches the lower bounds in its dependence on |S| and |A|.

3 Preliminaries

The preliminaries define DMDPs, policies, value operators, and ε-optimality, then review contraction, policy-approximation, and monotonicity properties used in the analysis. The sampling model assumes expected O(1)-time transition sampling, achievable through preprocessing.

  • DMDP Model: A DMDP consists of finite states and actions, transition probabilities, state-action rewards bounded by M, and a discount factor γ ∈(0, 1).The transition probability pa(i, j) describes reaching state j from state i after action a.
  • Sampling Assumption: The paper assumes independent transition sampling in expected O(1) time for each state-action pair, achievable with O(|S|^2|A|) preprocessing under its computation model.If sampling instead takes O(log |S|) time, the runtime changes only by a hidden polylogarithmic factor.
  • Value Operators: The value operator T maps a value vector to Bellman-updated values, and the optimal value v∗ is its unique fixed point.For a policy π, Tπ is the corresponding policy-specific operator and vπ is its unique fixed point.
  • Optimality: A policy or value vector is ε-optimal when its value is within ε of the optimal value in the infinity norm.For policies, this means ∥v∗−vπ∥∞≤ε; for values, it means ∥v∗−u∥∞≤ε.
  • Analytical Properties: The value operator is a γ-contraction and is monotone, while policy-value error can be bounded by the residual ∥Tπ(u)−u∥∞ scaled by γ/(1−γ).These properties support convergence, correctness, and residual-based analysis of value iteration.

4 DMDP Algorithms

The paper develops randomized approximate value-iteration algorithms for DMDPs, progressing from basic sampling and variance reduction to high-precision, sublinear, and monotonic policy computation.

  • 4.2 Basic Approximate VI Analysis: RandomizedVI approximates the value operator by sampling at each iteration and provides convergence, correctness, and runtime guarantees.Its approximate operator returns both an estimated value vector and a corresponding policy.
  • 4.1 Approximate Value Operator: Variance reduction estimates differences from a reference value vector, reducing sampling needs when the reference is close to the target values.ApxVal samples u − v0 and combines sample averages with an offset, rather than sampling u directly.
  • 4.3 High Precision Randomized VI in Nearly Linear Time: HighPrecisionRandomVI repeatedly invokes RandomizedVI from progressively better initial vectors, achieving geometrically improving accuracy while maintaining comparable iteration cost.The resulting value vector is ε-optimal with high probability, and the method targets nearly linear-time high-precision computation.
  • 4.4 Randomized VI in Sublinear Time: SampledRandomizedVI and SublinearRandomVI replace exact computations with sampling to obtain sublinear-time approximate value vectors when transition sampling is available.Their quality and runtime are stated through separate guarantees for the sampled and sublinear procedures.
  • 4.5 Obtaining a Policy: The basic policy-conversion analysis can incur a 1/(1−γ)^2 optimality loss, so the paper introduces monotonic methods to avoid this loss.The earlier conversion produces a policy with a 16ε/(1−γ)^2 guarantee, while the monotonic approach targets policy quality matching value quality.
  • 4.6 Improved Monotonic Algorithm: ApxMonVal maintains entrywise monotonicity and the invariant Tπ(v) ≥ v, allowing SublinearRandomMonVI to compute approximate policies without the previous conversion penalty.The monotonic operator returns approximate values and policies, and the resulting algorithm provides a high-probability approximate-policy guarantee.

5 Finite Horizon Markov Decision Process

The paper extends randomized and variance-reduced value iteration to finite-horizon MDPs, producing non-stationary ε-optimal policies with high probability. Variance reduction reuses value estimates across horizon blocks to improve runtime, with the best choice depending on accuracy and problem size.

  • 5.1 Randomized Value Iteration for Finite Horizon MDP: The finite-horizon extension adapts RandomizedVI by descending iteration counts, zero terminal values, and cumulative policy-error accuracy.These changes match backward induction and the fact that finite-horizon optimal policies are non-stationary.
  • 5.1 Randomized Value Iteration for Finite Horizon MDP: RandomizedFiniteHorizonVI returns an ε-optimal non-stationary policy with probability 1 − δ.It performs backward induction and outputs a policy for every time step, using additive error guarantees across the horizon.
  • 5.2 Variance Reduced Value Iteration for Finite Horizon MDP: VarianceReducedFiniteHorizonVI repeatedly solves L-step subproblems using the previous invocation’s last value vector as the next termination value.Each invocation yields an Lε/H-optimal subpolicy, and a union bound over H/L invocations gives an ε-optimal policy with probability 1 − δ.
  • 5.2 Variance Reduced Value Iteration for Finite Horizon MDP: Variance reduction lowers sampling cost by estimating changes from fixed reference values rather than recomputing transition expectations from scratch.The resulting error is tied to the current value quality, enabling a trade-off between reference recomputation and difference estimation.
  • 5.2 Variance Reduced Value Iteration for Finite Horizon MDP: VarianceReducedFiniteHorizonVI improves over RandomizedFiniteHorizonVI when the latter’s runtime is superlinear in |S|^2|A|, while L = 1 is preferable in the sublinear regime.For very small ε, L can be chosen to balance the runtime terms.
  • 5.2 Variance Reduced Value Iteration for Finite Horizon MDP: Theorem 5.5 gives a high-probability running-time guarantee for VarianceReducedFiniteHorizonVI while preserving ε-optimality.The theorem follows the blockwise variance-reduction construction and its accuracy guarantee.

6 Summary and Remarks

The paper develops variance-reduced value-iteration algorithms for DMDPs and extends them to finite-horizon MDPs. It reports nearly linear and sometimes sublinear runtimes, while identifying improved discount-factor dependence as future work.

  • 6 Summary and Remarks: Variance reduction yields approximately optimal DMDP policies in nearly linear and sometimes sublinear running times.The algorithms improve prior randomized results in their dependence on γ, |S|, and |A|.
  • 6 Summary and Remarks: The same ideas extend to finite-horizon MDPs, and the paper presents them as the first use of variance reduction for approximate value iteration in that setting.The authors also identify broader extensions to structurally informed MDPs and other optimization methods as future directions.

A Value Iteration Facts

This section records contraction, policy-evaluation, and monotonicity properties of the DMDP value operators. These facts connect approximate values and Bellman residuals to optimal values and policy values.

  • A Value Iteration Facts: The optimal Bellman operator is a γ-contraction in the infinity norm.Thus, applying T contracts distance to the optimal value vector by γ.
  • A Value Iteration Facts: For any policy π, the distance between Tπ(u) and vπ is bounded by γ/(1 − γ) times the Bellman residual of u.This relates approximate policy evaluation to the residual of the current value vector.
  • A Value Iteration Facts: If u ≤ v entry-wise, then T(u) ≤ T(v) entry-wise.The Bellman operator preserves componentwise ordering.

B Solving DMDPs With Interior Point Methods

The appendix formulates DMDPs as linear programs and explains how approximate LP solutions can be converted into approximately optimal policies. It then reduces the computational problem to ℓ1 regression using interior-point methods.

  • B Solving DMDPs With Interior Point Methods: The DMDP LP constraints are equivalent to requiring v ≥ T(v), and its unique minimizer is the optimal value vector.An approximately optimal objective together with feasibility bounds yields a vector close to its Bellman update.
  • B Solving DMDPs With Interior Point Methods: Choosing each state’s action greedily with respect to an approximate LP value yields an 8ε|S|(1 − γ)^−2-optimal policy.The conversion incurs a quantitative loss, so LP accuracy must be set more tightly than the desired policy accuracy.
  • B Solving DMDPs With Interior Point Methods: The appendix reduces approximate DMDP LP solving to an ℓ1 regression problem and applies interior-point running-time guarantees.The reduction uses a symmetric constraint formulation and penalizes violations of the original LP constraints.
  • B Solving DMDPs With Interior Point Methods: Approximate solutions to the auxiliary ℓ1 problem may violate the original LP constraints, requiring a parameter choice that trades constraint violation against objective error.Lemma B.7 quantifies how an ε-approximate ℓ1 solution induces an approximate DMDP LP solution.
  • B Solving DMDPs With Interior Point Methods: The resulting interior-point method computes an ε-approximate policy with high probability within the stated theorem runtime.The runtime follows from solving the DMDP ℓ1 problem to the accuracy required by the policy-conversion lemma.
Loading 1710.09988v3…