PaperlayerView exact revision on arXiv

Source-linked AI summary

Online Robust Reinforcement Learning with Model Uncertainty

Yue Wang, Shaofeng Zou

arXiv:2109.14523v2cs.LG

TL;DR

The paper addresses robust model-free reinforcement learning when samples come from an unknown, misspecified MDP but deployment may involve perturbed dynamics. It estimates the uncertainty set online and develops robust Q-learning and robust TDC, which achieve convergence guarantees and empirical robustness without extra discount-factor conditions.

  • Problem

    Standard RL assumes the training and deployment environments are identical, but model deviation can substantially degrade policy performance.

  • Method

    The paper estimates an unknown R-contamination uncertainty set from current samples and develops online, incremental robust Q-learning and robust TDC algorithms.

  • Results

    Robust Q-learning converges to the optimal robust action-value function, while robust TDC converges to stationary points; both match vanilla counterparts’ convergence speed within a constant factor and need no extra discount-factor condition.

  • Takeaways & Limitations

    The approach provides memory-efficient online robust RL under model uncertainty and can be extended to TD, SARSA, and other GTD algorithms.

  • Takeaways & Limitations

    The setting assumes samples come from an unknown centroid MDP while deployment occurs in a similar perturbed environment; reward uncertainty and other uncertainty sets remain future directions.

Abstract

from arXiv · show

Robust reinforcement learning (RL) is to find a policy that optimizes the worst-case performance over an uncertainty set of MDPs. In this paper, we focus on model-free robust RL, where the uncertainty set is defined to be centering at a misspecified MDP that generates a single sample trajectory sequentially and is assumed to be unknown. We develop a sample-based approach to estimate the unknown uncertainty set and design a robust Q-learning algorithm (tabular case) and robust TDC algorithm (function approximation setting), which can be implemented in an online and incremental fashion. For the robust Q-learning algorithm, we prove that it converges to the optimal robust Q function, and for the robust TDC algorithm, we prove that it converges asymptotically to some stationary points. Unlike the results in [Roy et al., 2017], our algorithms do not need any additional conditions on the discount factor to guarantee the convergence. We further characterize the finite-time error bounds of the two algorithms and show that both the robust Q-learning and robust TDC algorithms converge as fast as their vanilla counterparts(within a constant factor). Our numerical experiments further demonstrate the robustness of our algorithms. Our approach can be readily extended to robustify many other algorithms, e.g., TD, SARSA, and other GTD algorithms.

1 Introduction

The paper addresses robust RL when deployment environments differ from training environments and the uncertainty set is unknown. It proposes model-free, online algorithms for tabular and function-approximation settings with convergence and finite-time guarantees.

  • 1 Introduction: Model-free robust RL learns a robust policy from a single trajectory generated by a misspecified MDP while simultaneously estimating the uncertainty set.The setting avoids assuming a known uncertainty model and addresses the off-transition-kernel challenge.
  • 1 Introduction: The uncertainty set is estimated from current samples using an R-contamination design without extra memory or relaxation around the sampling MDP.This preserves the dependence on the misspecified MDP that generates samples.
  • 1 Introduction: Robust Q-learning converges to the optimal robust Q function without an additional discount-factor condition and matches vanilla Q-learning’s rate within a constant factor.The algorithm is online, incremental, and has the same memory cost as vanilla Q-learning.
  • 1 Introduction: Robust TDC extends the approach to function approximation through a smoothed robust Bellman formulation and a two-time-scale update rule.The method targets robust policy evaluation in the off-transition-kernel setting.
  • 1 Introduction: Experiments report higher reward for robust Q-learning under a misspecified MDP and faster robust TDC convergence, while vanilla TDC may diverge.These experiments are presented as evidence of robustness in both settings.

2 Preliminaries

The preliminaries define MDPs, policy values, and robust values when transition kernels vary within an uncertainty set. Robust dynamic programming uses a support-function Bellman operator whose fixed point is the optimal robust Q function.

  • 2 Preliminaries: An MDP comprises state and action spaces, a transition kernel, a cost function, and a discount factor γ ∈ [0, 1).Policies select actions and incur transition-dependent costs over time.
  • 2 Preliminaries: A policy’s value is its expected accumulated discounted cost, and the objective is to minimize that value from every initial state.The action-value and state-value functions encode these discounted costs.
  • 2 Preliminaries: In robust MDPs, nature adversarially selects a sequence of transition kernels from the uncertainty set.The robust value evaluates a fixed policy under the worst-case kernel sequence.
  • 2 Preliminaries: The transition-kernel uncertainty set can be represented state-action-wise as collections of next-state distributions, with a support function measuring the worst expectation over each collection.This representation enables robust Bellman recursion.
  • 2 Preliminaries: The robust Bellman operator is a contraction whose fixed point is the optimal robust Q function, solvable by dynamic programming when the uncertainty set is known.The operator combines costs, discounting, support functions, and action minimization.

3 R-Contamination Model For Uncertainty Set Construction

The paper models transition uncertainty with an R-contamination set centered at an unknown sampling kernel. Its size is controlled by a known parameter, while the set is estimated from sequential samples.

  • 3 R-Contamination Model For Uncertainty Set Construction: The uncertainty set is constructed with the R-contamination model, motivated by adversarial RL and robust detection.The model provides the paper’s chosen structure for transition-kernel uncertainty.
  • 3 R-Contamination Model For Uncertainty Set Construction: The set is centered at an unknown transition kernel that generates the sample trajectory, such as an imperfect simulator or a related environment.The learned policy is intended to perform well in a perturbed MDP from this centered set.
  • 3 R-Contamination Model For Uncertainty Set Construction: The design parameter R measures the size of the uncertainty set and is assumed known by the algorithm.The centroid transition probabilities themselves remain unknown.
  • 3 R-Contamination Model For Uncertainty Set Construction: An R-contamination set centered at p is contained in a total-variation ball, making the total-variation uncertainty set less conservative.The paper also relates total variation and KL divergence through Pinsker’s inequality.

4 Tabular Case: Robust Q-Learning

The tabular method estimates the unknown uncertainty set online from each observed transition and incorporates it into robust Q-learning without storing a full transition model. The algorithm converges to the optimal robust action-value function, requires no extra discount-factor condition, and achieves a finite-time complexity matching vanilla Q-learning up to constants.

  • Sample-based robust Q-learning: The algorithm estimates the unknown uncertainty set from each observed transition and uses the resulting support function in an online, incremental robust Q-learning update.The sample-based estimate uses the current observation's maximum-likelihood transition estimate, while the algorithm stores only the Q-table rather than the full transition model.
  • Efficiency and memory: Unlike the model-based approach, the method needs no prior uncertainty-set knowledge and uses |S| × |A| memory instead of a transition-model table of size |S|2|A|.
  • Convergence: Convergence does not require the additional discount-factor condition induced by prior uncertainty-set relaxation methods.
  • Convergence: The robust Q-learning algorithm converges asymptotically to the optimal robust action-value function Q∗.
  • Finite-time guarantee: ˜O(1/µmin(1−γ)5ϵ2 + tmix/µmin(1−γ)) samples suffice for an ϵ-accurate estimate up to logarithmic terms, matching vanilla Q-learning within a constant factor.

5 Function Approximation: Robust TDC

The robust TDC method evaluates a policy under the worst-case transition kernel using linear function approximation and a smoothed robust Bellman operator. Its online two-time-scale algorithm converges toward stationary points with finite-time complexity matching vanilla TDC, without additional discount-factor conditions.

  • 5 Function Approximation: Robust TDC: The robust TDC algorithm addresses policy evaluation when samples come from a different transition kernel than the worst-case kernel being evaluated.This off-transition-kernel setting can cause ordinary function-approximation methods to diverge.
  • 5 Function Approximation: Robust TDC: The method approximates the robust value function with linear features and minimizes a mean squared projected robust Bellman error.The projection is defined with respect to the stationary distribution induced by the policy.
  • 5 Function Approximation: Robust TDC: LogSumExp smoothing makes the robust Bellman operator differentiable, and its fixed point approaches the original robust operator's fixed point as ϱ increases.The smoothed operator is introduced because the max operation is nonsmooth in the parameters.
  • 5.1 Algorithm Development: Robust TDC uses a fast time scale to estimate an auxiliary vector and a slow time scale to estimate the gradient, enabling online incremental updates from one trajectory.The weight-doubling trick addresses the need for two independent samples in an unbiased gradient estimate.
  • 5.2 Finite-Time Error Bound of Robust TDC: With a = b = 0.5, the expected squared gradient norm achieves the stated finite-time rate, and robust TDC matches vanilla TDC complexity while adding model-uncertainty robustness.The convergence analysis targets stationary points because the smoothed objective is non-convex.

6 Experiments

Experiments evaluate robust Q-learning under perturbed training environments and robust TDC under function approximation, with additional comparison against RARL. Across tasks, robust methods outperform or remain stable relative to non-robust baselines as model mismatch increases.

  • 6.1 Robust Q-Learning: Robust Q-learning achieves much higher accumulated discounted reward than vanilla Q-learning on FrozenLake and CartPole when policies are trained on perturbed MDPs and tested on the true MDP.The plots use 30 trajectories and show 95th- and 5th-percentile envelopes.
  • 6.1 Robust Q-Learning: As the perturbation parameters p and R increase, robust Q-learning’s reward advantage over vanilla Q-learning becomes more significant.
  • 6.2 Robust TDC with Linear Function Approximation: Robust TDC converges much faster than vanilla TDC on FrozenLake, while vanilla TDC may diverge under larger training–test model mismatch.Robust TDC still converges to a stationary point in the reported high-mismatch setting.
  • 6.2 Robust TDC with Linear Function Approximation: Robust TDC has substantially smaller variance than vanilla TDC, indicating more stable behavior under model uncertainty.
  • 6.3 Comparison with The Adversarial Training Approach: Robust Q-learning achieves higher accumulated reward than RARL across the reported Taxi-v3 training comparisons.The comparison evaluates greedy policies in a worst-case testing environment under different parameters.

7 Conclusion

The paper develops online, incremental model-free robust RL algorithms for model uncertainty and establishes convergence and finite-time guarantees. Experiments and theory support robustness without extra discount-factor conditions, while several uncertainty extensions remain future work.

  • The algorithms require no additional memory beyond their non-robust counterparts and can be implemented online and incrementally.
  • Robust Q-learning converges to the optimal robust Q function, while robust TDC converges asymptotically to stationary points without additional discount-factor assumptions.
  • The finite-time error bounds for robust Q-learning and robust TDC match those of their non-robust counterparts within a constant factor.
  • The approach can be extended to robustify TD, SARSA, and other GTD algorithms.
  • Future work includes robustness to reward uncertainty and uncertainty sets defined by KL divergence, Wasserstein distance, or total variation.

Supplementary Materials

The supplementary material analyzes robust Q-learning through its Bellman operator and stochastic-approximation form. It establishes unbiased updates, contraction-based convergence, and the noise properties underlying the proof.

  • Robust Q-learning’s estimated update is an unbiased estimate of the robust Bellman operator.
  • The robust Bellman operator is shown to be a contraction for the R-contamination uncertainty set.
  • The update can be written as a stochastic approximation with a Bellman term and a noise term.The displayed recursion is Qt+1(st, at) = (1 −αt)Qt(st, at) + αt(TQt(st, at) + ηt(st, at, st+1)).
  • The noise term has zero mean and bounded variance, enabling convergence of the stochastic approximation to the fixed point of the robust Bellman operator.

B.2 Analysis

The analysis derives finite-time error bounds for robust Q-learning by decomposing trajectory-dependent error terms and controlling them with Markov-chain concentration arguments. The resulting convergence rate matches vanilla Q-learning up to a constant factor.

  • The error recursion decomposes robust Q-learning’s deviation from Q* into terms for transition estimation, sampling noise, and robust-value effects.
  • The analysis controls visitation-dependent terms using mixing properties of a time-homogeneous uniformly ergodic Markov chain.The bounds depend on trajectory visitation counts and the chain’s mixing behavior.
  • Bernstein-type concentration bounds control the stochastic terms with high probability over state-action pairs and time horizons.
  • The finite-time theorem provides a bound on ∥Qt − Q*∥∞ with probability at least 1 − 6δ.
  • The robust Q-learning convergence rate is as fast as vanilla Q-learning’s, apart from a constant factor.

C Proof of Theorem 4: Approximation of Smoothing Robust Bellman Operator

The proof establishes that the smoothed robust Bellman operator is a contraction and therefore has a fixed point, then connects the smoothing limit to the original operator.

  • The proof uses the softmax gradient of log-sum-exp and its sup-norm Lipschitz bound to establish the contraction property.
  • The smoothed robust Bellman operator is a contraction, which guarantees existence of a fixed point.
  • The smoothing argument then shows that fixed points of the smoothed operator converge to the fixed point of the original robust Bellman operator.
  • The finite-time robust TDC analysis uses projection because direct approaches for one-time-scale or linear updates do not directly handle its nonlinear two-time-scale updates.

D.2 Tracking Error

The tracking-error analysis bounds the discrepancy between the fast TDC variable and its policy-dependent target, using smoothness, Markov-noise control, and recursive error bounds.

  • The tracking error is defined as z_t = ω_t − ω(θ_t), measuring deviation of the fast variable from its policy-dependent target.
  • Lipschitz smoothness and uniform ergodicity are used to control Markovian-noise terms in the tracking-error analysis.
  • The proof bounds the tracking-error recursion by controlling update terms, Taylor remainders, parameter changes, and differences in the fast update function.
  • The resulting bound is obtained by recursively applying the error inequality and selecting step sizes α and β to control the decay and accumulated terms.
  • The subsequent robust TDC finite-time error analysis plugs the tracking-error bound into the parameter-error recursion.

E Experiments

The experiments evaluate robust learning in Frozen Lake and Taxi-v3 settings. In Taxi-v3, robust Q-learning achieves higher reward as training and test MDPs become more mismatched.

  • The experiments include a 4 × 4 Frozen Lake problem for evaluating the algorithms in the stated experimental settings.
  • Robust Q-learning achieves much higher reward than non-robust Q-learning as the mismatch between training and test MDPs increases.
  • The Taxi-v3 experiment uses α = 0.3 and γ = 0.8 to evaluate robustness under increasing model mismatch.
Loading 2109.14523v2…