PaperlayerView exact revision on arXiv

Source-linked AI summary

Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraints

Tianhao Wang, Dongruo Zhou, Quanquan Gu

arXiv:2101.02195v2cs.LGmath.OCstat.ML

TL;DR

RL with linear function approximation must operate under limited adaptivity because frequent policy updates can be costly or impractical. The paper develops batch and rare-switch algorithms for episodic linear MDPs, matching fully adaptive regret with far fewer updates, while proving a tight batch-budget dependence and identifying an unresolved rare-switch lower-bound question.

  • Problem

    The paper addresses RL with linear function approximation under batch and rare-policy-switch constraints, where frequent policy updates may be impractical.

  • Method

    It proposes LSVI-UCB-Batch and LSVI-UCB-RareSwitch for episodic linear MDPs with unknown linear transition and reward functions.

  • Results

    The algorithms achieve the same regret as fully adaptive LSVI-UCB with substantially fewer batches or policy switches, and the batch regret’s dependence on B is suggested to be tight.

  • Takeaways & Limitations

    Approximately √(T/dH) batches or dH log T policy switches suffice to obtain eO(√(d^3H^3T)) regret.

  • Takeaways & Limitations

    A fine-grained regret lower bound explicitly depending on the adaptivity budget B remains open for the rare policy switch model.

Abstract

from arXiv · show

We study reinforcement learning (RL) with linear function approximation under the adaptivity constraint. We consider two popular limited adaptivity models: the batch learning model and the rare policy switch model, and propose two efficient online RL algorithms for episodic linear Markov decision processes, where the transition probability and the reward function can be represented as a linear function of some known feature mapping. In specific, for the batch learning model, our proposed LSVI-UCB-Batch algorithm achieves an $\tilde O(\sqrt{d^3H^3T} + dHT/B)$ regret, where $d$ is the dimension of the feature mapping, $H$ is the episode length, $T$ is the number of interactions and $B$ is the number of batches. Our result suggests that it suffices to use only $\sqrt{T/dH}$ batches to obtain $\tilde O(\sqrt{d^3H^3T})$ regret. For the rare policy switch model, our proposed LSVI-UCB-RareSwitch algorithm enjoys an $\tilde O(\sqrt{d^3H^3T[1+T/(dH)]^{dH/B}})$ regret, which implies that $dH\log T$ policy switches suffice to obtain the $\tilde O(\sqrt{d^3H^3T})$ regret. Our algorithms achieve the same regret as the LSVI-UCB algorithm (Jin et al., 2019), yet with a substantially smaller amount of adaptivity. We also establish a lower bound for the batch learning model, which suggests that the dependency on $B$ in our regret bound is tight.

1 Introduction

The paper studies linear-function-approximation RL when policies cannot be updated every episode, focusing on batch learning and rare policy switches. It proposes algorithms that match fully adaptive regret with substantially less adaptivity and proves a batch-model lower bound.

  • Motivation: Linear MDPs model unknown transition probabilities and rewards as linear functions of a known feature mapping, addressing possibly infinite state and action spaces.The feature mapping has dimension d.
  • Motivation: Frequent policy updates can be unrealistic because of large datasets, limited computing resources, and switching costs.The paper motivates batching data and updating policies only at selected times.
  • Contributions: The paper proposes LSVI-UCB-Batch for the batch learning model and LSVI-UCB-RareSwitch for the rare policy switch model.Both algorithms target episodic linear MDPs under adaptivity constraints.
  • Batch learning: The batch algorithm achieves eO(√(d^3H^3T) + dHT/B) regret, and approximately √(T/dH) batches suffice for eO(√(d^3H^3T)) regret.Here d is feature dimension, H is episode length, T is interactions, and B is the number of batches.
  • Lower bounds: A batch-learning regret lower bound suggests that the dependence on B in the proposed batch regret bound is tight.The paper notes that the rare-switch model still lacks a fine-grained lower bound for arbitrary adaptivity budget B.
  • Rare policy switches: The rare-switch algorithm achieves eO(√(d^3H^3T[1 + T/(dH)]^(dH/B))) regret, while dH log T policy switches suffice for eO(√(d^3H^3T)) regret.The resulting policy-switch count is smaller than the batch-learning counterpart when T is large.

2 Related Works

Related work spans linear-function-approximation RL, limited-adaptivity online learning, and switching-constrained RL. Prior results motivate the paper’s focus on obtaining efficient RL under explicit batch or policy-switch budgets.

  • RL with linear function approximation: Prior RL work studies linear MDPs in which transition probabilities and rewards are linear in a feature mapping.Jin et al. proposed an efficient algorithm for this setting, alongside work on other MDP settings.
  • Online learning with limited adaptivity: Limited adaptivity has been studied in batch-learning and rare-policy-switch models across prediction, bandits, and online convex optimization.These models constrain when an algorithm can incorporate new observations into its decisions.
  • Batch learning: For prediction-from-experts, the batch regret exhibits a phase transition as the number of batches crosses a scale proportional to √T log n.The cited result gives eO(√T log n) regret for B = Ω(√T log n) and min(eO(T log n/B), T) for smaller B.
  • Batch learning: Prior batched bandit results establish regret dependencies on the batch budget, including a lower bound of Ω(T/B) for batched multi-armed bandits.Batched linear-bandit work gives eO(√(dT) + dT/B) under adversarial contexts.
  • Switching-constrained RL: Prior RL results under switching constraints include local-switching guarantees for tabular MDPs and global-switching guarantees for time-homogeneous tabular MDPs.These results concern finite-state or finite-action settings rather than the linear-function-approximation setting emphasized here.

3 Preliminaries

The preliminaries define time-inhomogeneous episodic MDPs, linear MDP structure, and two limited-adaptivity models. The goal is to achieve fully adaptive regret with bounded batches or policy switches.

  • Markov decision processes: A time-inhomogeneous episodic MDP has stage-dependent rewards and transition probabilities over episodes of length H.The state space may be infinite, and feasible actions may vary by stage.
  • Linear function approximation: In a linear MDP, transition probabilities and rewards are represented as linear functions of a known feature mapping φ:S×A→R^d.The feature norm is assumed to be at most 1.
  • Linear function approximation: With known features, estimating stage-specific weight vectors is sufficient to recover action-value functions.This is the core algorithmic idea identified for linear MDPs.
  • Objective: The stated objective is to achieve the regret of fully adaptive LSVI-UCB while imposing a budget on batches or policy switches.The paper treats the two adaptivity constraints as alternative online-learning models.
  • Batch learning model: In the batch model, batch boundaries are fixed in advance and one policy is followed throughout each batch.Adaptivity is measured by the number of batches B.
  • Rare policy switch model: In the rare policy switch model, the agent decides whether to switch policies, and adaptivity is measured by the number of policy switches.This quantity is identified with the global switching cost.

4 RL in the Batch Learning Model

The batch-learning approach fixes batch boundaries in advance, updates policies only at batch starts, and uses LSVI-UCB-style estimation within each batch. Its regret matches fully sequential LSVI-UCB at a substantially smaller batch count, while a lower bound supports the dependence on the number of batches.

  • Algorithm: The algorithm takes the number of batches, confidence radius, and regularization parameter as inputs, using uniform batch grids.Each batch begins at a predetermined grid point, and the policy remains unchanged until the next batch.
  • Algorithm: At each batch start, it estimates parameters by ridge regression, constructs confidence-based Q-values, and selects a greedy policy.Within a batch, the previously selected policy is reused without updating.
  • Comparison: When B = K, LSVI-UCB-Batch degenerates to LSVI-UCB, while its batch-grid design also relates to SBUCB for linear bandits.SBUCB is identified as the H = 1 special-case setting.
  • Regret guarantee: Theorem 4.1 bounds regret by a leading eO(√(d^3H^3T)) term plus a batch-dependent dHT/B term.The theorem is stated under Assumption 3.2 with λ = 1 and a specified confidence-radius choice.
  • Regret guarantee: The leading eO(√(d^3H^3T)) regret matches LSVI-UCB, while B = Ω(√(T/dH)) batches suffice to attain that rate.This can require far fewer batches than the K batches used by fully sequential LSVI-UCB.
  • Lower bound: For B ≥ (d−1)H/2, every batch-learning algorithm has a linear-MDP instance with a lower-bounded regret, supporting the stated dependence on B.The paper relates the batches required for standard √T-regret to a lower-bound order also seen in batched linear bandits.

5 RL in the Rare Policy Switch Model

The rare policy switch model lets the agent adaptively choose batch sizes, and LSVI-UCB-RareSwitch switches policies using a determinant-based information criterion. Its regret decreases as the switching budget increases, reaching the fully adaptive rate with O(dH log T) switches.

  • Algorithm: The algorithm maintains stage-specific matrices Λ_h and compares updated matrices using determinants before switching.The determinant criterion reflects how much additional information has been collected and how the confidence bound has tightened.
  • Algorithm: LSVI-UCB-RareSwitch adaptively chooses when to switch policies and is controlled by the hyperparameter η.The algorithm retains the previous policy unless a determinant-based criterion indicates sufficient information growth.
  • Regret guarantee: Theorem 5.1 guarantees that η = (1 + K/d)^(dH/B) keeps the number of policy switches at most B.The theorem specifies λ = 1 and β = c dH√log(2dT/δ) alongside this choice of η.
  • Implications: The rare-switch regret bound exhibits a trade-off: increasing the adaptivity budget B decreases the regret bound.The paper also notes that a fine-grained lower bound depending on B remains open for this model.

6 Numerical Experiment

The experiments evaluate both proposed algorithms on a synthetic hard-to-learn linear MDP against fully adaptive LSVI-UCB. They show comparable regret under adaptivity constraints, with rare policy switching remaining closer to the fully adaptive baseline throughout learning.

  • Setup: The experiments compare LSVI-UCB-Batch and LSVI-UCB-RareSwitch with fully adaptive LSVI-UCB on a synthetic linear MDP.The instance uses H = 10, K = 2500, δ = 0.35, d = 13, and 1024 actions.
  • Setup: Figure 1 plots average regret Regret(T)/K against the number of episodes, averaging 50 rounds with [20%, 80%] empirical confidence intervals.The batch algorithm is tested with B = 10, 20, 30, 40, 50, while the rare-switch algorithm uses η = 2, 4, 8, 16, 32.
  • Results: When B ≈ K, LSVI-UCB-Batch achieves regret similar to fully adaptive LSVI-UCB as more trajectories are collected.The performance gap between the batch method and LSVI-UCB is small mainly when the episode count is large.
  • Results: With constant η, LSVI-UCB-RareSwitch has a similar regret order to LSVI-UCB and remains consistently close throughout learning.The experiments therefore indicate better adaptivity for the rare-switch method than for the batch method in this setting.
  • Trade-off: More limited adaptivity, represented by smaller B or larger η, produces a larger regret gap from fully adaptive LSVI-UCB.The results support comparable performance under adaptivity constraints and corroborate the theoretical analysis.

7 Conclusions

The paper proposes two algorithms for linear-function-approximation RL under batch and rare policy-switch constraints. Their regret matches fully adaptive LSVI-UCB with fewer updates, and the batch-model dependence on B is supported by a lower bound.

  • Contributions: The paper studies online RL with linear function approximation under both batch learning and rare policy switching constraints.It proposes LSVI-UCB-Batch and LSVI-UCB-RareSwitch for the two settings.
  • Theoretical results: The batch algorithm has Õ(√(d^3H^3T) + dHT/B) regret, while the rare-switch algorithm has Õ(√(d^3H^3T[1 + T/(dH)]^(dH/B))) regret.These bounds quantify how limited adaptivity affects regret in the two models.
  • Implications: Both algorithms achieve the fully adaptive LSVI-UCB regret with substantially fewer batches or policy switches.The paper also proves a batch-model regret lower bound indicating that the dependence on B is tight.
  • Future work: A future direction is to prove a rare-policy-switching lower bound that explicitly depends on the adaptivity budget B.The conclusion identifies this as an unresolved theoretical question.

Checklist

The checklist reports that the paper addresses claims, assumptions, limitations, and experiment reporting, while noting that reproduction code, data, and instructions were not included.

  • Research practices: The checklist marks the paper’s contribution and limitation descriptions as complete and reports no societal-impact concern for this theoretical work.It also states that the work does not involve human subjects.
  • Theory: The paper states that theoretical assumptions and complete proofs are provided.This checklist response concerns the theoretical results rather than the numerical experiments.
  • Experiments: The experiments report training details, repeated-run error bars, and compute resources, but not reproducibility code, data, or instructions.The checklist marks experiment reproducibility materials as absent while marking training details and error bars as reported.
  • Assets and participants: The paper reports no use of existing assets and marks asset licensing, consent, and personally identifiable-information discussion as not applicable.These responses appear in the checklist’s asset and human-subjects sections.
  • Figure 2: Figure 2 presents average regret against episode count on a log scale with 50-run empirical confidence intervals.The checklist section includes the Figure 2 caption but does not provide a result comparison from the plot.

A Additional Details on the Numerical Experiments

The experiments evaluate the proposed algorithms under misspecified linear MDPs and find reasonably good performance across substantial misspecification levels. Their average-regret curves have slopes similar to fully adaptive LSVI-UCB in the reported log-scaled comparison.

  • Results: The average-regret curves for the proposed algorithms have slopes similar to fully adaptive LSVI-UCB in the log-scaled plot.The reported slopes indicate an eO(1/...) average-regret trend, with the expression truncated in the passage.
  • Misspecified-model setup: The experiments corrupt transitions using ζ-approximate linear MDPs, where ζ ∈ (0, 1) controls the level of model misspecification.The additional functions f and g are randomly sampled before running the algorithms.
  • Experimental settings: The misspecification levels tested are ζ = 0.05, 0.1, 0.2, and 0.4, using B = 50 for LSVI-UCB-Batch and η = 8 for LSVI-UCB-RareSwitch.Average regret is plotted for these settings in Figure 3.
  • Results: The proposed algorithms achieve reasonably good performance under considerable levels of model misspecification.This conclusion is based on the average-regret plots for the tested misspecification levels.

B Proofs of Theorem 4.1

The proof of Theorem 4.1 bounds batch-learning regret by controlling delayed exploration bonuses. It compares delayed and per-episode bonuses, limits the number of large-ratio indices, and combines concentration and determinant-based arguments.

  • Proof strategy: Algorithm 1 uses information available before the current batch, so its regret analysis must control delayed bonuses relative to per-episode bonuses.The delayed-bonus effect is identified as the main difficulty caused by batch learning.
  • Bonus decomposition: The proof introduces virtual per-episode bonuses and bounds their total sum before analyzing the difference from delayed bonuses.The per-episode bonuses facilitate the analysis but are not generated directly by the algorithm.
  • Large-ratio indices: The set of indices whose delayed-to-per-episode bonus ratio exceeds 2 has size at most dHK log(K/d + 1)/(2B log 2).This bound quantifies how often the delayed bonuses can be substantially larger than the per-episode bonuses.
  • Regret bound: The resulting regret bound contains an additive batch-dependent term proportional to dHT/B, as shown in the proof's final inequality.The displayed fragment includes the term dHT/(2B) multiplied by logarithmic factors.
  • Concentration arguments: The regret proof uses high-probability optimism and concentration results for the LSVI-UCB estimates, including a confidence parameter β proportional to dH√log(dT/δ).The proof also invokes a martingale-difference bound using Azuma-Hoeffding and a union bound.

C Proof of Theorem 5.1

The proof of Theorem 5.1 controls policy-switching frequency through determinant growth and bounds regret using the same bonus framework. Choosing the switching parameter yields the stated switch-count control and completes the high-probability regret argument.

  • Switching criterion: The switching analysis uses determinant growth to compare confidence norms associated with successive policy updates.The key matrix comparison applies when one positive-definite design matrix dominates another.
  • Switching criterion: Algorithm 2's global switching cost is bounded through a determinant-based update criterion parameterized by η > 1 and λ > 0.Each policy update is linked to determinant growth at some stage.
  • Switching bound: With the theorem's choice of η and λ = 1, the proof obtains N_switch ≤ B.This follows by substituting the parameter choice into the switching-cost lemma.
  • Regret analysis: The regret proof reuses the high-probability bound from Lemma B.1 and bounds the delayed bonus sum using the algorithm design and determinant comparison lemma.The final probability guarantee follows after substituting the chosen η into the resulting inequality.

D Proofs of Theorem 4.2

The lower-bound proof constructs a deterministic family of linear MDPs in which batch-level decisions can be anticipated by the environment. This forces wrong actions in selected batches and yields the dHT/B dependence.

  • Hard-instance construction: The hard instance has d + 1 states, two actions, and a feature mapping parameterized by vectors b_h,i across stages and states.The construction uses an absorbing state x0 and states x1 through xd.
  • Regret structure: Episodes starting from x0 incur no regret, while an episode starting from xi incurs H − h regret if the first wrong action occurs at stage h.Each xi can transition only to x0 or itself.
  • Lower-bound conclusion: The lower bound for deterministic algorithms is dHT/B, and random algorithms inherit it through Yao's minimax principle.The proof separately combines this term with the existing √(d^3H^3T) lower bound.
  • Batch placement: The proof selects dH batches whose starting states are chosen from the hard states, while other batches start from the absorbing state x0.This isolates regret to selected batch positions.
  • Adversarial anticipation: Because actions, transitions, and rewards are deterministic within a batch, the environment can predict the agent's selection and choose the other action as the right-action complement.The construction therefore forces the agent to choose the wrong action when first visiting the relevant state.
Loading 2101.02195v2…