PaperlayerView exact revision on arXiv

Source-linked AI summary

Safe Policy Improvement with Baseline Bootstrapping

Romain Laroche, Paul Trichelair, Rémi Tachet des Combes

arXiv:1712.06924v5cs.LGcs.AIstat.ML

TL;DR

The paper tackles safe policy improvement in Batch RL, where policies are trained offline from fixed data and should not underperform a known baseline. It introduces SPIBB, which falls back to the baseline under high uncertainty, and reports guaranteed improvement for Πb-SPIBB alongside stronger empirical performance and efficiency for its variants.

  • Problem

    Safe Batch RL seeks policies that improve over a data-collecting baseline despite fixed offline data and no direct access to the true environment.

  • Method

    SPIBB bootstraps the learned policy with the known baseline on insufficiently sampled state-action transitions, with Πb-SPIBB providing PAC-style safety guarantees.

  • Results

    SPIBB is reported to outperform existing methods in safety and mean performance, while Πb-SPIBB provides provably safe improvement and Π≤b-SPIBB performs better and safer without SPI guarantees.

  • Takeaways & Limitations

    SPIBB supports efficient offline policy improvement over a known baseline, including a model-free neural-network version for batch-data tasks without environment interaction.

  • Takeaways & Limitations

    Π≤b-SPIBB retains convergence guarantees but loses the safety-improvement guarantees of SPI, whereas Πb-SPIBB requires choosing N∧ to balance safety and improvement.

Abstract

from arXiv · show

This paper considers Safe Policy Improvement (SPI) in Batch Reinforcement Learning (Batch RL): from a fixed dataset and without direct access to the true environment, train a policy that is guaranteed to perform at least as well as the baseline policy used to collect the data. Our approach, called SPI with Baseline Bootstrapping (SPIBB), is inspired by the knows-what-it-knows paradigm: it bootstraps the trained policy with the baseline when the uncertainty is high. Our first algorithm, $Π_b$-SPIBB, comes with SPI theoretical guarantees. We also implement a variant, $Π_{\leq b}$-SPIBB, that is even more efficient in practice. We apply our algorithms to a motivational stochastic gridworld domain and further demonstrate on randomly generated MDPs the superiority of SPIBB with respect to existing algorithms, not only in safety but also in mean performance. Finally, we implement a model-free version of SPIBB and show its benefits on a navigation task with deep RL implementation called SPIBB-DQN, which is, to the best of our knowledge, the first RL algorithm relying on a neural network representation able to train efficiently and reliably from batch data, without any interaction with the environment.

1. Introduction

The paper addresses safe Batch RL for offline settings where unreliable policy updates can persist, proposing SPIBB to improve a known baseline while handling uncertainty through baseline bootstrapping.

  • Motivation: Real-world RL deployments can suffer prolonged user harm or irreversible damage when agents cannot be quickly patched or outcomes arrive years later.These constraints motivate guarantees on policy performance before wide-scale adoption.
  • Problem setting: Batch RL trains policies from fixed observations without access to the true environment, but existing methods may be unsafe or computationally costly.The paper focuses on safety with respect to parametric uncertainty.
  • Approach: SPIBB bootstraps the trained policy with the behavioral baseline on state-action transitions insufficiently probed by the dataset.The method assumes access to the baseline, matching the goal of improving an existing policy.
  • Algorithms: Πb-SPIBB approximately outperforms the baseline with high confidence, while Π≤b-SPIBB sacrifices theoretical guarantees for greater practical efficiency.The paper also develops an equivalent model-free version supporting neural-network representations.
  • Evaluation: Experiments compare SPIBB with existing algorithms in stochastic gridworlds, randomly generated MDPs, and a continuous navigation task.The reported comparisons cover safety, mean performance, and batch training with deep RL.

2. SPI with Baseline Bootstrapping

SPIBB makes safe policy improvement in Batch RL tractable by restricting changes where the dataset is uncertain and bootstrapping with the baseline on rarely observed state-action pairs. Π_b-SPIBB provides high-confidence approximate safety guarantees, while Π_≤b-SPIBB and a model-free implementation improve practical efficiency but relax guarantees.

  • Batch RL learns from fixed transition data without access to the true environment, while Basic RL optimizes the estimated MDP directly.The dataset supplies state-action counts and an MLE MDP; Basic RL seeks its optimal policy.
  • SPIBB methodology: SPIBB bootstraps with the baseline on state-action pairs that are rarely observed in the dataset.The bootstrapped set B contains pairs whose counts are below the threshold N∧.
  • Π_b-SPIBB: Π_b-SPIBB optimizes estimated-MDP return over policies constrained to preserve baseline probabilities on every state-action pair.It constructs the allowed policy set Π_b and searches for its optimum using constrained policy iteration.
  • Π_b-SPIBB: With high probability 1−δ, Π_b-SPIBB is a ζ-approximately safe policy improvement over the baseline.The algorithm uses a threshold N∧ chosen to balance safety and improvement; unlike the compared bound, this threshold is an algorithm hyper-parameter.
  • Model-free SPIBB: The model-free SPIBB formulation has a unique finite-MDP fixed point matching the Q-values of model-based Π_b-SPIBB.Pseudo-counts enable the approach to work with neural-network representations, supporting SPIBB-DQN.
  • Π_≤b-SPIBB: Π_≤b-SPIBB is more efficient in practice but loses SPI guarantees, although experiments report greater safety and stronger performance in most scenarios.The reported exception is multi-batch settings, where continuing to explore bootstrapped pairs may be preferable.
  • Related work: Compared with importance-sampling SPI methods, SPIBB uses Bayesian rather than frequentist bounds, while its safety dependence on planning horizon is linear for fixed Vmax.Importance-sampling estimates have high variance and require data scaling exponentially with horizon in long-horizon problems.

3. SPIBB Empirical Evaluation

Across gridworlds, random MDPs, and navigation with deep RL, SPIBB generally improves safety and mean performance relative to existing Batch RL methods, while sensitivity to data collection, dataset size, and N∧ remains important.

  • 100k repeated dataset-generation and policy-training runs evaluate mean performance and X%-CVaR, defined over the X% worst policy outcomes.The benchmark includes Basic RL, HCPI, Robust MDP, and RaMDP alongside SPIBB methods.
  • Gridworld: In the gridworld, SPIBB is generally safe, becomes more conservative as N∧ increases, and Π≤b-SPIBB outperforms Πb-SPIBB.The main exception is Πb-SPIBB with low N∧ on 10-trajectory datasets; at N∧=20, both algorithms remain safe and near optimal on large datasets.
  • Gridworld: RaMDP and Π≤b-SPIBB win the gridworld mean-performance benchmark, while Π≤b-SPIBB remains above baseline in 1%-CVaR.Πb-SPIBB is slightly behind, whereas RaMDP’s strong mean performance hides catastrophic runs on small datasets.
  • Random behavioural policy: With uniformly random data collection, both SPIBB algorithms still significantly outperform competitors, but complete safety fails when N∧≤10 and |D|≤20.Under this setting, Πb-SPIBB slightly outperforms Π≤b-SPIBB, while Basic RL becomes safe with 100 trajectories.
  • Random MDPs: In random MDPs, Π≤b-SPIBB is safe across the tested η and dataset-size map, whereas RaMDP is unsafe across a large region.With a very good baseline, all methods fail to be safe except the SPIBB algorithms; the theory predicts a ζ-approximate safe policy improvement.
  • SPIBB-DQN: For navigation, vanilla DQN worsens the baseline, while SPIBB-DQN improves mean performance for N∧≥1 and 10%-CVaR for N∧≥8.The result is reported for datasets of 10k, 20k, and 30k transitions; evaluation errors affect the displayed baseline and trained-policy curves.

4. Conclusion and Future Work

The paper develops safe Batch RL methods that improve over a known baseline while addressing the challenges of learning from fixed experience. It provides model-based, efficient, and neural-network-compatible SPIBB variants, with guarantees applying to Πb-SPIBB.

  • SPIBB addresses safe Batch RL by training from fixed experience without direct access to the true environment.The paper frames Batch RL around a fixed transition dataset and estimates an MDP from observed rewards and transitions.
  • Πb-SPIBB optimizes the estimated MDP under constraints that preserve the baseline on insufficiently sampled state-action pairs.The policy representation is expanded to support matrix-based operations, including policy, transition, reward, and discount-rate matrices.
  • Π≤b-SPIBB is more efficient and empirically performs better and safer, but it does not provide the safety guarantees of Πb-SPIBB.The paper distinguishes the guaranteed constrained variant from the practically more efficient variant.
  • The model-free SPIBB implementation extends the approach to neural-network representations and deep batch learning without environment interaction.The paper identifies the DQN version as enabling safe policy improvement from batch data.

A.3. Convergence and safe policy improvement of Πb-SPIBB

The appendix establishes that Πb-SPIBB converges to a constrained optimum in the estimated MDP and yields a high-confidence approximate safety guarantee in the true MDP. Its policy-improvement step differs from Π≤b-SPIBB because the latter can remove poorly performing bootstrapped probability mass.

  • Bootstrapped semi-MDP: The bootstrapped semi-MDP replaces insufficiently sampled actions with options that initiate on adequately sampled pairs and follow the baseline during bootstrapping.The construction decomposes the baseline into non-bootstrapped and bootstrapped action probabilities and uses a common termination function.
  • Assumptions: The safety theory assumes trajectories were generated under baseline πb, so the bootstrapped options remain consistent with the dataset.This baseline-data-collection requirement is explicitly identified as a limiting factor of the theory.
  • Convergence: Πb-SPIBB converges to a policy that is Πb-optimal in the maximum-likelihood estimated MDP.The proof transforms the constrained problem into an unconstrained policy-optimization problem in a bootstrapped semi-MDP.
  • Safe policy improvement: Πb-SPIBB’s learned policy is a ζ-approximate safe improvement over baseline πb with high probability 1−δ.The guarantee applies within Πb, the policy set that follows πb on bootstrapped state-action pairs.
  • Model-free equivalence: In finite MDPs, the model-free Πb-SPIBB update has a unique fixed point matching the Q-value of the model-based trained policy.The uniqueness follows from the contraction property of the Bellman operator.
  • Policy improvement: Π≤b-SPIBB removes probability mass from bootstrapped state-action pairs whose estimated values are worse than the current Q-value estimates, unlike Πb-SPIBB.Πb-SPIBB leaves bootstrapped probabilities untouched during policy improvement.

B.1.1. PSEUDO CODE FOR THE GRIDWORLD BENCHMARK

The Gridworld benchmark pseudocode evaluates multiple algorithms across dataset sizes and hyper-parameter settings. Each trained policy is evaluated and its performance recorded for comparison.

  • The benchmark iterates over each configured dataset size.
  • For every dataset size, the procedure generates a dataset and evaluates each algorithm in the benchmark.
  • For each algorithm and hyper-parameter value, the procedure trains a policy, evaluates it, and records its performance.

B.1.2. PSEUDO CODE FOR THE RANDOM MDPS BENCHMARK

The Random MDP benchmark generates environments, baselines, datasets, and trained policies across hyperparameters, then records normalized mean and CVaR performance. It compares SPIBB with competitor algorithms under varying dataset sizes and baseline settings.

  • Benchmark procedure: The benchmark repeatedly generates an MDP, baseline, dataset, and trained policy for each algorithm and hyperparameter combination.Each trained policy is evaluated and its performance recorded.
  • Environment generation: Random MDPs use 25 states, 4 actions per state, connectivity 4, and discount factor γ = 0.95.These fixed values were selected after preliminary experiments found little sensitivity to the generation parameters.
  • Baseline generation: Baselines are parameterized by η ∈ {0.1, 0.2, 0.3, 0.4, 0.5, 0.6, 0.7, 0.8, 0.9}, which determines normalized baseline performance.The baseline is generated through softening followed by randomization of action probabilities.
  • Dataset generation: Datasets contain 10 to 2,000 trajectories in Random MDP experiments, with larger sizes additionally used for Gridworld.Trajectories are sampled from the environment and baseline until reaching the final state.
  • Evaluation: Performance is normalized relative to baseline and optimal policies, then analyzed using mean performance and X%-CVaR over the worst X% of runs.The benchmark evaluates whether policies consistently outperform the baseline across repeated datasets.

C.1. Gridworld additional results

The additional Gridworld results present benchmark curves for risk-sensitive performance and show results across several N∧ values.

  • Risk-sensitive results: The Gridworld figures report 10%-CVaR and 0.1%-CVaR benchmark curves.Additional curves use N∧ values of 5, 10, 50, and 100.

C.2. Gridworld full results with random behavioural policy

The random-behaviour-policy Gridworld results report mean and CVaR benchmark curves, with additional curves for several N∧ values.

  • Random behavioural policy: The figures show mean, 10%-CVaR, and 0.1%-CVaR benchmark curves under a random behavioural policy.Additional curves use N∧ values of 5, 10, and 50.

C.3. Full Random MDPs experiment results

The full Random MDP results visualize normalized performance across dataset sizes, baseline η values, and several risk or mean-performance measures. A separate helicopter environment specification describes the continuous navigation task’s dynamics, rewards, states, and actions.

  • Random MDP heatmaps: Random MDP heatmaps use dataset size on the x-axis, baseline η on the y-axis, and color to encode normalized performance relative to baseline.Red, yellow, and green indicate below, equal to, and above baseline performance.
  • Random MDP benchmarks: Random MDP benchmark figures report 1%-CVaR, 10%-CVaR, and mean normalized performance for multiple η values.The displayed η values include 0.1, 0.3, 0.5, 0.7, and 0.9; additional values are provided in supplementary material.
  • Helicopter environment: The helicopter navigation environment uses four continuous state features and discrete thrust actions along two dimensions.The state includes position and velocity coordinates, while each thrust component is selected from {-1, 0, 1}.
  • Helicopter dynamics: The helicopter transitions update position and velocity with thrust, time step τ = 0.1, and Gaussian position and velocity noise.The noise standard deviations are σs = 0.025 for position and σv = 0.05 for velocity.
  • Reward and evaluation: The helicopter reward is zero in non-terminal states and −1 when velocity or position leaves its allowed range, ending the episode.Evaluation uses an undiscounted return, although SPIBB-DQN training uses a discount factor below 1.

D.3. Details about the DQN and SPIBB-DQN implementations

The implementations replace environment sampling with fixed datasets and modify DQN targets for SPIBB. Experiments use pseudo-counts, target networks, Double-DQN, and a specified neural-network training configuration.

  • Batch DQN trains by sampling transitions from the fixed dataset rather than interacting with the environment.
  • SPIBB uses modified Bellman targets, reverting to traditional Bellman targets when the bootstrap set B is empty.
  • The implementation combines pseudo-counts with target networks and Double-DQN.
  • The benchmark network has three hidden layers with 32, 128, and 32 neurons and nine outputs for the nine actions.
  • Training uses RMSProp with momentum 0.95, ϵ = 10^-7, mini-batches of 32, and an initially 0.01 learning rate.

D.4. Preliminary SPIBB-DQN experiments

Preliminary experiments examined seed sensitivity and hyper-parameter choices for SPIBB-DQN and Reward-adjusted MDP. Vanilla DQN was unreliable on the helicopter dataset, whereas SPIBB-DQN was stable for sufficiently large minimum counts.

  • Preliminary SPIBB-DQN experiments: Vanilla DQN produced substantially different Q-networks and policies across random seeds on a 10k-transition dataset.
  • Preliminary SPIBB-DQN experiments: Mean performance was 1.7 on the preliminary dataset versus -0.5 in the main document, but vanilla DQN remained unreliable.
  • Preliminary SPIBB-DQN experiments: SPIBB-DQN showed stability for N^≥4 in the preliminary experiments.
  • Preliminary SPIBB-DQN experiments: The RaMDP search evaluated κadj values from 0.001 to 0.1, including κadj = 0 corresponding to vanilla DQN.
  • Preliminary SPIBB-DQN experiments: The paper frames these experiments within an objective of improving reinforcement-learning robustness, reliability, reusability, and reproducibility.

E.1. Pineau’s checklist (slide 33)

The checklist documents the algorithms, environments, experimental procedures, metrics, reproducibility materials, and computing infrastructure. It also records complexity statements and implementation components that are not included.

  • Complexity: The finite-MDP complexity increase over standard policy iteration is described as insignificant, while pseudo-count computation may significantly increase SPIBB-DQN complexity.
  • Reproducibility: The code is provided in separate finite-MDP and SPIBB-DQN projects, with commands and dependencies documented for reproducing experiments.
  • Experimental protocol: Experiments use complete datasets for training without validation sets, while testing is performed in the true environment.
  • Evaluation: Results report mean and conditional value at risk, with 100,000+ evaluation runs for finite-MDP experiments and 300 for SPIBB-DQN.
  • Included materials: The release includes Basic RL, both SPIBB variants, HCPI methods, Robust MDP, Reward-adjusted MDP, and Gridworld and Random MDP environments.
  • Not included: The hyper-parameter search, figure generator, and multi-CPU/multi-GPU implementation are not included.
Loading 1712.06924v5…