PaperlayerView exact revision on arXiv

Source-linked AI summary

The Importance of Pessimism in Fixed-Dataset Policy Optimization

Jacob Buckman, Carles Gelada, Marc G. Bellemare

arXiv:2009.06799v3cs.AIcs.LG

TL;DR

Fixed-dataset policy optimization raises the question of how to guarantee high-return policy selection when a fixed dataset may leave policy values uncertain. This paper develops a regret framework and pessimistic algorithms; its analysis contrasts their guarantees with naïve methods and compares uncertainty-aware and proximal approaches.

  • Problem

    The paper studies worst-case guarantees for fixed-dataset policy optimization, where naïve methods may need data informative about every policy’s value because overestimation can increase suboptimality.

    Source: §1 · p. 1

  • Method

    The paper bounds regret for proxy-objective decision-makers and derives uncertainty-aware and proximal FDPO algorithms that select policies using pessimistic values.

    Source: §1 · pp. 1–2, §5.1 · p. 4, §5.2 · p. 6

  • Results

    Naïve methods may require value information for every policy, whereas pessimistic methods can attain small suboptimality without it; uncertainty-aware methods are strictly better than proximal methods in the reported theory and experiments.

    Source: §1 · pp. 1–2, §7 · p. 8

  • Takeaways & Limitations

    Worst-case-value selection offers a principled FDPO alternative when informative data for every policy is difficult to obtain.

    Source: §1 · pp. 1–2

    Proximal pessimistic algorithms are not guaranteed to converge to the optimal policy, even with infinite data.

    Source: §5.2 · p. 6

Abstract

from arXiv · show

We study worst-case guarantees on the expected return of fixed-dataset policy optimization algorithms. Our core contribution is a unified conceptual and mathematical framework for the study of algorithms in this regime. This analysis reveals that for naive approaches, the possibility of erroneous value overestimation leads to a difficult-to-satisfy requirement: in order to guarantee that we select a policy which is near-optimal, we may need the dataset to be informative of the value of every policy. To avoid this, algorithms can follow the pessimism principle, which states that we should choose the policy which acts optimally in the worst possible world. We show why pessimistic algorithms can achieve good performance even when the dataset is not informative of every policy, and derive families of algorithms which follow this principle. These theoretical findings are validated by experiments on a tabular gridworld, and deep learning experiments on four MinAtar environments.

1 INTRODUCTION

The paper studies worst-case guarantees for fixed-dataset policy optimization (FDPO), where naïve methods may require data informative about every policy. It presents pessimism as a principled alternative and develops theoretical and empirical support for it.

1 INTRODUCTION

  • The paper’s central contribution is a theoretical justification of pessimism in FDPO, using a regret bound for decision-makers that optimize proxy objectives.The framework is intended to derive principled algorithms, rather than to claim novelty for pessimism itself.Source: §1 · p. 1
  • Naïve FDPO can require enough data to establish the value of every policy, because value overestimation can sharply increase suboptimality.The analysis attributes this to the optimizer’s curse and notes that it does not depend on function-approximation errors.Source: §1 · p. 1
  • Pessimistic FDPO selects a policy that maximizes a notion of worst-case expected return, avoiding the need to inform the dataset about every policy’s value.The paper derives two families of pessimistic algorithms and reports improved guarantees and gridworld confirmation.Source: §1 · p. 2
  • Deep-learning experiments in MinAtar empirically validate predictions of the analysis, complementing the gridworld experiments.The paper presents its contribution as conceptual and theoretical, complementary to existing deep-learning algorithms.Source: §1 · p. 2

2 HOW PROXY OBJECTIVES IMPACT REGRET

This section relates decision regret to the quality of a proxy objective and explains why proxy errors affect regret asymmetrically. It connects this framework to FDPO, where an overestimated selected policy can produce high regret.

2 HOW PROXY OBJECTIVES IMPACT REGRET

  • Theorem 1 bounds the regret of a decision-maker optimizing a proxy objective in terms of proxy quality, and the bound is stated to be tight.The theorem applies to an arbitrary choice space and objective.Source: §2 · p. 2
  • When the proxy estimates the true objective, reduced estimation error can reduce decision regret, but overestimation and underestimation have asymmetric effects.A good choice whose value is not underestimated can suffice for one bound term, while the overestimation term considers all choices; even one large overestimate can cause significant regret.Source: §2 · p. 2
  • In FDPO, using a learned function as a proxy can lead to selecting an overestimated policy and experiencing high regret.The paper examines this effect in the specific decision-making setting of FDPO.Source: §2 · p. 2

3 FDPO BACKGROUND

This section sets up FDPO as value-based policy selection from a fixed dataset, with value uncertainty used to analyze performance.

3 FDPO BACKGROUND

  • The setup models the environment as an MDP and derives empirical reward and transition functions and an empirical policy from a dataset of transitions.The analysis also uses value-uncertainty functions that provide high-probability upper bounds on value-function error.Source: §3 · p. 3
  • Value-based FDPO evaluates policies with a fixed-dataset policy evaluation algorithm, then selects the policy with the highest assigned value.The evaluation objective is defined by a fixed-point equation.Source: §3 · p. 3
  • FDPO instantiates the general decision-making framework with policies as choices and expected returns as objectives, yielding a suboptimality bound for value-based algorithms.The corollary applies to a value-based optimizer with a fixed-dataset policy evaluation subroutine.Source: §3 · p. 3

4 NA¨IVE ALGORITHMS

Naïve FDPO treats the limited dataset as an accurate picture of the environment, but its worst-case guarantee can demand low value uncertainty across all policies.

4 NA¨IVE ALGORITHMS

  • Naïve algorithms treat limited observations as an accurate environment model and use an asymmetry-agnostic proxy objective.The paper does not study implementations of the broader fixed-point-defined family in detail.Source: §4 · p. 3
  • Certainty equivalence, FQI, and fixed-replay-buffer DQN are cited as examples related to naïve value-based FDPO.The paper also notes that many FDPE and FDPO implementations in this family are not examined in detail.Source: §4 · p. 3
  • The naïve bound is favorable when some reasonably good policy has low value uncertainty, but also requires low uncertainty for every policy.The all-policy condition is more demanding; expert demonstrations can reduce uncertainty for a good policy without resolving uncertainty elsewhere.Source: §4 · p. 4
  • The authors argue that naïve methods may perform poorly when policies are numerous, good policies are rare, and most policies have high value uncertainty.Under these assumptions, uncertain policies may be overestimated and selected; deep-RL benchmarks have shown overestimation typically correlated with poor performance.Source: §4 · p. 4

5 THE PESSIMISM PRINCIPLE

Pessimism selects policies by their worst-case expected return, reducing overestimation while accepting additional underestimation. This section develops uncertainty-aware and proximal algorithms and establishes that proximal methods are a special case of the uncertainty-aware family.

5 THE PESSIMISM PRINCIPLE

  • Pessimism chooses the policy with the best worst-case guarantee on expected return, reducing overestimation while incurring additional underestimation.The principle is framed as exploiting current knowledge about the environment.Source: §5 · p. 4

5.1 UNCERTAINTY-AWARE PESSIMISTIC ALGORITHMS

  • Uncertainty-aware algorithms penalize policies using state-wise Bellman uncertainty, and increasing α shrinks the supremum term until it vanishes at α = 1.The optimal α generally lies between the fully naïve and fully pessimistic extremes.Source: §5.1 · pp. 4–5

5.2 PROXIMAL PESSIMISTIC ALGORITHMS

  • Proximal penalties keep policies near the empirical policy, can block optimal convergence with infinite data, and equal imitation when α ≥ 1 − γ.The approach may miss highly visited states reached through many trajectories.Source: §5.2 · pp. 5–6

5.3 THE RELATIONSHIP BETWEEN UNCERTAINTY-AWARE AND PROXIMAL ALGORITHMS

  • Proximal algorithms are uncertainty-aware algorithms using a trivial value-uncertainty function, while tighter uncertainty functions can yield tighter penalties.The proximal penalty follows by upper-bounding uncertainty differences with total variation.Source: §5.3 · p. 6
  • For neural networks, only the trivial uncertainty function is currently implementable, leaving proximal pessimistic algorithms as the only theoretically motivated family.This qualification applies to the deep-learning setting described in the paper.Source: §5.3 · p. 6

6 EXPERIMENTS

Experiments in tabular and deep-learning settings qualitatively align with the theoretical predictions. In MinAtar, pessimism combines imitation of near-optimal behavior with some improvement when data is more exploratory, though FREEWAY is a notable exception.

6 EXPERIMENTS

  • Uncertainty-aware methods perform well with data from near-optimal policies or substantial data from worse policies and are reported to outperform the other approaches.The naïve method needs almost no policies with high value uncertainty; stochastic collection helps, and it approaches optimality as dataset size grows. Proximal methods roughly mirror imitation, improve on it, and do not approach optimality as data grows.Source: §6 · pp. 6–7
  • Experiments in both tabular and deep-learning settings qualitatively align with the predictions of the theoretical analysis.The tabular experiments vary data-collection policy and dataset size, while the neural-network experiments use MinAtar environments.Source: §6 · p. 7
  • The tabular experiments vary collection policy from uniform random to optimal and dataset size from 1 to 200000 samples; both show qualitatively distinct algorithm trends aligned with theory.The collection-policy comparison uses ϵ-greedy interpolation.Source: §6 · p. 7, Figure 1 · p. 7
  • In MinAtar, pessimism imitates near-optimal behavior and improves somewhat with exploratory data, but barely improves over imitation in FREEWAY.The naïve approach performs well with fully exploratory data and poorly when data comes from an optimal policy; pure imitation does better as collection approaches optimality.Source: §6 · p. 7

7 DISCUSSION AND CONCLUSION

The paper develops a framework for fixed-dataset policy optimization and identifies pessimism as a defining feature of solutions. It contrasts naïve approaches with pessimistic methods and discusses implications and open directions.

7 DISCUSSION AND CONCLUSION

  • The discussion identifies pessimism as the defining feature of solutions and describes uncertainty-aware and proximal algorithms as two pessimistic families.Both families have theoretical and empirical advantages over the naïve approach, while uncertainty-aware algorithms are strictly better than proximal algorithms in the comparisons reported.Source: §7 · pp. 7–8
  • The authors identify neural uncertainty estimation as a direction toward principled uncertainty-aware deep algorithms and advise against focusing FDPO research on proximal algorithms.They expect uncertainty-aware methods to improve performance based on their tabular results.Source: §7 · p. 8
  • Ad-hoc tuning of proximal pessimism can require evaluating policies in the environment, which fixed-dataset optimization does not permit.A principled adaptive penalty must be based on an uncertainty function, in which case the authors argue that an uncertainty-aware algorithm is preferable.Source: §7 · p. 8
  • Proximal pessimistic algorithms may select stochastic policies, making simple argmax-action policy improvement inadequate.For uncertainty-aware algorithms, this property depends on the Bellman uncertainty function.Source: §7 · p. 8
  • The paper suggests that pessimism in deep reinforcement learning could permit more training per interaction by improving the fixed point relative to naïve FDPO.The discussion frames replay buffers as temporarily fixed datasets during training and presents incorporating pessimism as future work.Source: §7 · p. 8

A BACKGROUND

  • FDPO maps a dataset to a policy, with the objective of minimizing the learned policy’s suboptimality.The paper defines suboptimality as the difference between optimal and learned-policy expected returns under the initial-state distribution.Source: A BACKGROUND · p. 13

B UNCERTAINTY

  • The analysis separates uncertainty estimation from decision-making, with value uncertainty representing accumulated Bellman-update errors.Bellman uncertainty captures how well an approximate update matches the true environment.Source: B UNCERTAINTY · pp. 13–14

B.1 STATE-ACTION-WISE BOUND

  • Hoeffding bounds applied across state-actions with a union bound provide a high-probability bound on Bellman-update error.The construction intersects this bound with the general 1/(1−γ) bound.Source: §B.1 · p. 15

B.2 STATE-WISE BOUND

The state-wise bound can be tighter for stochastic policies than the state-action-wise bound, while alternative concentration methods offer further tightening opportunities with trade-offs.

B.2 STATE-WISE BOUND

  • The state-wise bound can tighten uncertainty estimates because policy probabilities move inside the square root, although its local-policy-set factor may loosen the bound.For deterministic local policies, it is equivalent to the state-action-wise bound.Source: §B.2 · p. 16
  • Stochastic policies can sometimes have lower evaluation error than deterministic policies under the state-wise bound.The example uses one state, two actions, and two observations of each state-action; selecting stochastic policies requires including them in the local policy set, which increases the overall bound.Source: §B.2 · p. 16

B.3 OTHER BOUNDS

  • Good-Turing intervals and empirical Bernstein intervals may tighten bounds for relatively deterministic transitions and low-variance rewards or transitions, respectively.These are presented as possible improvements to the Hoeffding-based bounds.Source: §B.3 · pp. 16–17
  • Directly bounding value error across multiple timesteps may tighten value uncertainty, but sacrifices the monotonic improvement property needed for policy-iteration convergence.The paper notes a parallel with robust MDP methods beyond s-rectangular approaches.Source: §B.3 · p. 17

C.1 PROOF OF THEOREM 1

  • The objective difference f(x∗) − f(ˆx∗) can be rewritten by adding and subtracting proxy-objective values ˆf(x) and ˆf(ˆx∗); this identity holds for any x ∈ X.Source: §C.1 · p. 17

C.2 TIGHTNESS OF THEOREM 1

This section gives an example establishing tightness of Theorem 1 and states a lemma relating value error to Bellman residuals.

C.2 TIGHTNESS OF THEOREM 1

  • A two-point example with a tied proxy argmax makes the two sides of Theorem 1’s bound equal.Source: §C.2 · p. 17

C.3 RESIDUAL VISITATION LEMMA

  • The residual visitation lemma expresses value error as one-step Bellman residual accumulated over the policy’s visitation distribution.The authors include the proof for clarity, noting that the result is well known.Source: §C.3 · p. 17

C.4 NA¨IVE FDPE ERROR BOUND

The naïve evaluation bound connects policy error to uncertainty along visited state-actions, while the next section introduces relative value uncertainty for constructing proximal algorithms.

C.4 NA¨IVE FDPE ERROR BOUND

  • The naïve FDPE error bound controls evaluation error using value uncertainty at state-actions visited by the policy.The paper derives the bound by viewing the naïve fixed point as the Bellman fixed point of the empirical MDP.Source: §C.4 · p. 18
  • Reducing Bellman uncertainty on frequently visited state-actions improves evaluation guarantees, and the bound remains non-vacuous when some state-actions have no data.Unlike prior l∞ bounds, this component-wise bound responds to uncertainty in individual rewards and transitions and does not require equal sample counts across states.Source: §C.4 · p. 18

C.5 RELATIVE VALUE UNCERTAINTY

  • The key to constructing proximal pessimistic algorithms is a relationship between the value uncertainties of any two policies for state-action-wise decomposable uncertainty functions.Source: §C.5 · p. 19

C.6 NA¨IVE FDPE RELATIVE ERROR BOUND

These appendices develop error and suboptimality bounds for naïve and pessimistic fixed-dataset policy optimization, then give example algorithms. The pessimistic analyses include uncertainty-aware and proximal families, while the implementation discussion notes convergence properties and scope.

C.6 NA¨IVE FDPE RELATIVE ERROR BOUND

  • The naïve evaluation bound is constructed to support policy optimization without computing value uncertainties, using looser upper bounds instead.The proof bounds state-action Bellman uncertainty and decomposable value uncertainty before applying earlier lemmas.Source: §C.6 · pp. 19–20

C.7 SUBOPTIMALITY OF UNCERTAINTY-AWARE PESSIMISTIC FDPO ALGORITHMS

  • The uncertainty-aware pessimistic analysis bounds both underestimation and overestimation errors before deriving a suboptimality result.It uses the UA family's fixed-point property and invokes a probability-1−δ bound.Source: §C.7 · p. 20

C.8 SUBOPTIMALITY OF PROXIMAL PESSIMSITIC FDPO ALGORITHMS

  • For proximal pessimism, the analyzed evaluator and its full form return policies with equivalent suboptimality.The proof bounds both error directions and derives a bound for algorithms using the proximal-full evaluator.Source: §C.8 · pp. 21–22

C.9 STATE-WISE PROXIMAL PESSIMISTIC ALGORITHMS

  • State-action-density proximal pessimistic algorithms have a suboptimality bound with a state-action-wise decomposable value uncertainty function.The appendix says this variant has essentially the same properties as the state-conditional density approach emphasized in the main text.Source: §C.9 · p. 22

D ALGORITHMS

  • The appendix presents example algorithms to illustrate the naïve and pessimistic families, rather than to provide a comprehensive set or detailed convergence analysis.It notes that standard policy-iteration reasoning applies to the pessimistic updates, whose state-wise penalties yield strict monotonic value improvement and eventual convergence to an optimal penalized-value policy.Source: D ALGORITHMS · p. 23, §D.2 · p. 24

D.1 NA¨IVE

  • Naïve tabular methods apply standard dynamic programming to the empirical MDP built from the dataset.The appendix supplies pseudocode for tabular evaluation, policy iteration, and value iteration, as well as a neural value-iteration implementation.Source: §D.1 · p. 23

D.2.1 UNCERTAINTY-AWARE

The appendix gives pseudocode and implementation details for uncertainty-aware and proximal pessimistic methods. It also relates these families to prior approaches, while noting that neural uncertainty estimation remains unresolved for the uncertainty-aware implementation.

D.2.1 UNCERTAINTY-AWARE

  • The neural uncertainty-aware pseudocode is incomplete because count-based Bellman uncertainty does not apply to non-tabular environments and neural epistemic uncertainty remains open.A full implementation would need to specify a way to compute the Bellman uncertainty function.Source: §D.2.1 · p. 24

D.2.2 PROXIMAL

  • Proximal pessimistic updates penalize deviations from the empirical policy, and their discrete-action optimization has a closed-form solution.The optimal policy may be stochastic because the penalty is minimized when the policy matches the empirical policy, which may itself be stochastic.Source: §D.2.2 · pp. 25–26

E RELATED WORK

  • Unlike imitation learning, pessimistic FDPO can imitate the dataset when other actions are uncertain and sometimes deviate to improve.Imitation learning cannot improve on the empirical policy's quality in the FDPO setting.Source: E RELATED WORK · p. 26
  • The paper distinguishes its pessimism guarantees for expected suboptimality from safety guarantees, while connecting uncertainty-aware methods to robust MDPs.The uncertainty-aware approach is equivalent to constructing a robust MDP from data using concentration inequalities and optimizing against adversarial parameters.Source: E RELATED WORK · p. 27
  • Several prior fixed-dataset methods fit the proximal family through regularizers upper-bounding total variation, while model-based methods fit the uncertainty-aware family.The paper says its bounds justify these families, but notes that ensemble-based uncertainty penalties in the model-based methods are not theoretically well motivated.Source: E RELATED WORK · pp. 27–28

F EXPERIMENTAL DETAILS

The experiments describe a tabular gridworld and MinAtar evaluation setup, alongside a bandit-like example illustrating the risk of empirical-mean selection. In that example, pessimistic lower bounds favor the correct action where empirical means usually select a suboptimal one.

F.1 TABULAR

  • The tabular study averages 1000 trials in an 8×8 gridworld with four actions, stochastic transitions, and rewards whose state-action means are sampled from Beta(3,1).It compares imitation, naïve, uncertainty-aware pessimistic, and proximal pessimistic approaches; α=1 for both pessimistic methods.Source: §F.1 · p. 28

F.2 DEEP LEARNING

  • The deep-learning evaluation uses four MinAtar environments and reports averages over three trials, with ranges between maximum and minimum values.The study implements proximal pessimistic methods in a Neural Fitted Q-Iteration style and sets α=0.25.Source: §F.2 · p. 28
  • All experiments used identical hyperparameters; tuning was very minimal, using a small manual search on just two setups: BREAKOUT with ϵ = 0 and BREAKOUT with ϵ = 1.Source: §F.2 · p. 28
  • In the bandit-like MDP, empirical-mean selection almost always picks a suboptimal action, whereas selecting the highest lower bound almost always picks the correct action.The figure identifies μ as each action's true mean, n_D as dataset pull counts, and μ_D as empirical mean estimates.Source: Figure 3 · p. 29

G.1 AN ILLUSTRATIVE EXAMPLE

  • With 1000 actions, empirical-mean selection almost never chooses the best arm: another arm has empirical mean 1 with probability 1−4×10^-5.The best arm has mean 0.99 and is sampled 10,000 times, while each of the other arms has mean 0.01 and is sampled once.Source: §G.1 · p. 29
  • The example argues that its large, skew-covered action space resembles multi-state MDPs, where policies are exponentially numerous and data may come from only a few similar policies.The authors offer this as an analogy to skewed data coverage in practical settings.Source: §G.1 · p. 29

G.2 EXTREME PESSIMSIM: VALUE LOWER BOUND ALGORITHMS

Value lower-bound methods remove the generic suboptimality bound's requirement that all policies be well estimated, leaving a condition on at least one suitable policy. The practical considerations section highlights sensitivity to training dynamics and implementation choices.

G.2 EXTREME PESSIMSIM: VALUE LOWER BOUND ALGORITHMS

  • A value-lower-bound FDPO algorithm's suboptimality bound retains the infimum term but removes the supremum over policies, requiring a suitable condition for only one policy.The authors say this is easier to satisfy than a condition required for all policies.Source: §G.2 · p. 30
  • Any amount of pessimism that reduces overestimation can lessen dependence on a global condition, but uniform downward shifts do not help.Productive pessimism must vary across states so that the infimum term does not increase by the same amount.Source: §G.2 · p. 30

G.3 PRACTICAL CONSIDERATIONS

  • Deep-learning performance oscillated with target-network updates and sometimes crashed after initially high scores, motivating predetermined training duration and long runs.The authors warn against selecting steps in a way that unintentionally cherry-picks results.Source: §G.3 · p. 30
  • Poor inner-loop minimization negatively affected performance and sometimes led to divergence; low target-update error is the condition cited for guaranteed convergence near the fixed point.The authors identify this as a tradeoff under computational restrictions.Source: §G.3 · p. 30
  • The original DQN-sized network fit MinAtar, but smaller networks degraded performance and preliminary experiments suggested full Atari may require a larger network.The appendix also reports that about 250,000 gradient steps per target update were needed to consistently minimize error enough to avoid divergence.Source: §G.3 · p. 31
  • The authors reinitialized the neural network at each target-network update to reliably find a good solution to the new supervised-learning problem.They note that neural-network training dynamics remain incompletely understood and cite initialization's importance.Source: §G.3 · p. 31
Loading 2009.06799v3…