PaperlayerView exact revision on arXiv

Source-linked AI summary

Model-Based Reinforcement Learning with Value-Targeted Regression

Alex Ayoub, Zeyu Jia, Csaba Szepesvari, Mengdi Wang, Lin F. Yang

arXiv:2006.01107v1cs.LGstat.ML

TL;DR

The paper asks whether value-targeted regression can support sufficient and efficient model-based online RL despite imperfect targets and ignored dynamics. It proposes optimistic planning over models selected by value-prediction losses, obtaining sublinear regret and a ˜O(H^3/2d√T) bound for linear mixtures. Experiments report competitive performance and task-focused model tuning, while leaving some model-combination and misspecification questions open.

  • Problem

    The paper asks whether value-targeted regression is sufficient and efficient for model-based online RL despite imperfect value targets and potentially ignored dynamics.

  • Method

    The algorithm constructs confidence sets using value-targeted regression and selects the next value function through optimistic planning over data-consistent models.

  • Results

    For linear mixture models, the regret is bounded by ˜O(H^3/2d√T), and experiments find competitive performance with task-focused model tuning.

  • Takeaways & Limitations

    The results support using predicted value functions as regression targets and indicate that the method can achieve low regret while ignoring a major part of the environment.

  • Takeaways & Limitations

    The current theoretical tools do not characterize expected tradeoffs among alternative target combinations, and misspecified-model extensions are left for future work.

Abstract

from arXiv · show

This paper studies model-based reinforcement learning (RL) for regret minimization. We focus on finite-horizon episodic RL where the transition model $P$ belongs to a known family of models $\mathcal{P}$, a special case of which is when models in $\mathcal{P}$ take the form of linear mixtures: $P_θ = \sum_{i=1}^{d} θ_{i}P_{i}$. We propose a model based RL algorithm that is based on optimism principle: In each episode, the set of models that are `consistent' with the data collected is constructed. The criterion of consistency is based on the total squared error of that the model incurs on the task of predicting \emph{values} as determined by the last value estimate along the transitions. The next value function is then chosen by solving the optimistic planning problem with the constructed set of models. We derive a bound on the regret, which, in the special case of linear mixtures, the regret bound takes the form $\tilde{\mathcal{O}}(d\sqrt{H^{3}T})$, where $H$, $T$ and $d$ are the horizon, total number of steps and dimension of $θ$, respectively. In particular, this regret bound is independent of the total number of states or actions, and is close to a lower bound $Ω(\sqrt{HdT})$. For a general model family $\mathcal{P}$, the regret bound is derived using the notion of the so-called Eluder dimension proposed by Russo & Van Roy (2014).

1 Introduction

The paper asks whether value-targeted regression is sufficient and efficient for model-based online RL, and proposes an optimistic model-based algorithm to answer that question. Its theory establishes sublinear regret, while experiments find the combined value-targeted and optimistic approach competitive.

  • The proposed algorithm selects data-consistent models by their ability to predict next-state values under the latest value-function estimate, rather than next states or raw observations.
  • Value-targeted regression focuses model learning on task-relevant transition dynamics and can ignore dynamics irrelevant to the task.
  • The central question is whether value-targeted regression is sufficient and efficient for model-based online RL.
  • The regret bounds show that imperfect, non-stationary value targets do not cause the algorithm to get stuck, yielding sublinear regret.
  • Experiments find the algorithm competitive and indicate that value-targeted regression and optimistic planning are jointly effective, while removing either component reduces performance or sample efficiency.
  • For linear mixtures, the regret upper bound is ˜O(d√(H^3T)), with a corresponding lower bound described as close to it.

2 Problem Formulation

The paper studies episodic finite-horizon MDPs with an unknown transition model drawn from a known model family. The objective is sublinear regret, including for general and linear-mixture transition classes.

  • An episodic MDP consists of states, actions, a transition kernel, rewards, a horizon H, and an initial state.
  • The agent knows S, A, H, and r but not P, and interacts with the environment over episodes of H decisions.
  • At each stage, the agent observes a state, chooses an action, receives its reward, and transitions according to the unknown transition law.
  • The goal is to design an algorithm with guaranteed sublinear regret for any specified family of transition models.
  • The unknown transition model belongs to a known family P that may be finitely parametrized or nonparametric, including smoothly parameterized models.
  • Linear mixture models represent transitions using unknown coefficients over fixed known basis models, and include linear-factored MDPs as a special case.

3 Upper Confidence RL with Value-Targeted Model Regression

UCRL-VTR maintains data-consistent transition models using value-targeted regression, then applies optimistic planning to select each episode’s model and policy. The framework is modular but can be computationally difficult for general model families.

  • Confidence-set construction: At each episode’s start, the algorithm constructs a confidence set B_k of models consistent with previously collected data.Value-targeted regression is used to construct B_k, which is then refined after the episode.
  • Optimistic planning: The algorithm selects the model in B_k with the highest optimal value and extracts its policy through dynamic programming.Optimistic planning provides an upper value estimate when the true model remains in B_k with high probability.
  • Value-targeted regression: Value-targeted regression predicts next-state values using the latest estimated value function rather than fixed targets such as probabilities or raw states.The regression target changes as the algorithm’s value estimates become more accurate.
  • Model assumptions: The confidence-set construction exploits time-homogeneity, although it can be modified when transition kernels depend on the stage.The same transition model is used at every stage in the time-homogeneous setting.
  • Implementation: In general, UCRL-VTR requires case-by-case implementation, while linear-factor models admit efficient regression and polynomial-time optimistic planning techniques.For general model classes, optimistic planning is computationally intractable, motivating randomized or approximate dynamic programming methods.

4 Theoretical Analysis

The analysis bounds regret for general model families through Eluder dimension and metric entropy, then specializes the result to linear mixtures. The paper also establishes a lower bound and discusses the scope of the guarantees.

  • General model classes: The Eluder dimension measures how long a sequence can remain independently informative for distinguishing functions in a class at a given scale.The definition uses ε′-independence of each point from its predecessors for some ε′ ≥ ε.
  • General model classes: For general model families, the regret analysis uses the Eluder dimension and covering numbers of a function class built from model-induced value predictions.The function domain combines states, actions, and value functions associated with models in P.
  • Regret formulation: The analysis defines K-episode pseudo-regret, which determines expected T-step regret through R(KH) = E R_K.Thus, studying the episodic pseudo-regret suffices for the expected regret after T steps.
  • Upper bounds: Theorem 1 provides the main regret guarantee for Algorithm 1 under the stated assumption and confidence-sequence choice.The theorem’s general bound is parameterized by the relevant function-class complexity.
  • Upper bounds: In linear transition models, the worst-case regret bound depends linearly on the number of parameters.The corresponding guarantee is stated in Corollary 2 for mixtures of d basis transition models.
  • Lower bounds: A lower bound is established for linearly parameterized models, while the paper notes that the tightness of the upper and lower bounds remains unresolved.The lower-bound construction applies for H ≥ 1 and d ≥ 8, and the comparison is close in the stated dependence.
  • Interpretation and scope: The results support using predicted value functions as regression targets, but worst-case conclusions do not determine behavior on particular MDP instances.The paper conjectures that fitting transitions to predict future observations may provide little worst-case-regret benefit in linear mixtures.
  • Interpretation and scope: The upper bounds can be extended to misspecified settings by increasing β_k, but the details are left for future work.This extension allows the true transition model to lie outside P.

5 Related Work

Prior work spans tabular, Bayesian general-model, function-approximation, and linear-transition RL. The paper positions its contribution as worst-case regret analysis for general model families and linear mixtures.

  • Tabular and general-model RL: Tabular RL has established provable regret bounds for both model-based and model-free episodic algorithms.Earlier work also addressed the technically more challenging continuing setting.
  • Tabular and general-model RL: Prior tabular lower bounds extend to episodic settings through horizon- or diameter-based reductions, with near-matching upper bounds in several cases.The cited results include homogeneous and inhomogeneous episodic MDPs.
  • Function approximation: Function-approximation research includes provably efficient methods based on linear action-value representations, simulation oracles, linear factor models, and related structural assumptions.These works cover several model-free and model-based settings beyond tabular MDPs.
  • Linear transition models: For linear transition models, MatrixRL obtains a regret bound of approximately O(H^2d√T) in a matrix-embedding setting.Here d denotes the dimension of the state representation φ(s, a).
  • Linear transition models: The paper’s related setting includes linear MDP and ensemble-transition work with complexity bounds involving feature and basis-model dimensions.These results include both model-free and model-based approaches.
  • Tabular and general-model RL: General-model RL has been studied through posterior sampling, including Bayesian regret bounds involving Kolmogorov and Eluder dimensions.The paper distinguishes these Bayesian results from its focus on worst-case regret.
  • Positioning: The paper states that, to the authors’ knowledge, prior work had not designed low-regret algorithms for MDPs with a general model family.Its worst-case result is contrasted with earlier Bayesian analyses of general model classes.

6 Numerical Experiments

The experiments compare value-targeted and canonical model fitting with optimistic planning and ϵ-greedy exploration in RiverSwim and WideTree. Results show that optimism is crucial for value-targeted regression, which can achieve low regret even with poor model accuracy.

  • Experimental design: The experiments compare model fitting based on next-state prediction with value-targeted regression, each paired with either optimistic planning or ϵ-greedy exploration.Mixed-target algorithms use both targets.
  • RiverSwim: RiverSwim uses S ∈ {3, 4, 5} states with horizon 4S, testing algorithms in an environment where swimming against the current requires smart exploration.The environment has a small reward at the leftmost state and a larger reward farther right.
  • RiverSwim: UCRL-VTR achieves low regret in RiverSwim, indicating that fitting the state-value function provides enough signal for learning.Its regret is significantly better than EGRL-VTR and even than EG-Freq in the smallest environment.
  • RiverSwim: Value-targeted regression with optimistic exploration outperforms optimism using the canonical model-estimation procedure in RiverSwim.The authors attribute this to faster learning of a model that predicts optimal values well.
  • Interpretation: The small weighted model error achieved by value-targeted regression in RiverSwim appears to be accidental rather than a general property of the method.The authors use subsequent experiments to investigate this effect.
  • WideTree: In WideTree, UCRL-VTR quickly learns a good policy despite learning a poor model, while EG-Freq and EG-VTR perform equally poorly.WideTree has horizon H = 2 and is designed so that only one action affects the outcome.

7 Conclusions

The paper proposes UCRL-VTR, an optimistic model-based method that selects transition models by value-prediction accuracy and plans optimistically over consistent models. Its regret is controlled by model-class complexity, with competitive theoretical and empirical results.

  • 7 Conclusions: UCRL-VTR evaluates models by their ability to predict value functions constructed during learning.The algorithm uses value-targeted regression to construct confidence sets and then applies optimistic planning.
  • 7 Conclusions: The general regret bound depends on the Eluder dimension and metric entropy of an appropriately constructed function space.
  • 7 Conclusions: The experiments found low regret even when the algorithm ignored modeling a major part of the environment.This result supports task-focused model tuning in the chosen environment.
  • 7 Conclusions: The confidence-set analysis establishes that the true transition model belongs to Bk with probability 1 −δ for every k.

A.5.2 Proof of Corollary 2

For linear mixture models, the proof bounds confidence-set complexity through covering numbers and Eluder dimension, both of which scale with the parameter dimension up to logarithmic factors.

  • A.5.2 Proof of Corollary 2: N(P, α/H, ∥· ∥∞,1) is bounded by N(Θ, α/H, ∥· ∥1), linking model coverings to parameter-space coverings.
  • A.5.2 Proof of Corollary 2: βK = H2(d + log(1/δ)) after suppressing logarithmic factors, log log terms, and constants.
  • A.5.2 Proof of Corollary 2: The Eluder dimension of the induced function class satisfies dimE(F, α) ≤ dimE(Lin(Z, Θ), α).The reduction represents each value-prediction function as a linear map in the parameter vector θ.
  • A.5.2 Proof of Corollary 2: dimE(F, α) = ˜O(d) after dropping logarithmic terms.

A.6 Proof of Theorem 5

The proof derives a uniform nonlinear least-squares confidence bound using subgaussian concentration, covering-number discretization, and union bounds over time and the function class.

  • A.6 Proof of Theorem 5: The construction uses conditionally σ-subgaussian martingale differences and concentration inequalities that hold simultaneously over all t.
  • A.6 Proof of Theorem 5: The proof controls approximation error by replacing ˆft with a nearby function from an α-cover under the sup norm.The cover contributes through its covering number Nα.
  • A.6 Proof of Theorem 5: 4σ2 log(|G(α)|/δ) bounds the discretized concentration term after applying a union bound.

B Proof of Theorem 3

The lower-bound proof embeds a hard tabular MDP into a linear mixture model family, transferring the known tabular regret lower bound to the paper’s setting.

  • B Proof of Theorem 3: The proof reduces the regret lower bound to a known result for tabular MDPs.
  • B Proof of Theorem 3: The construction uses S = 2 states and A = d/4 actions, so |S × A × S| = d.
  • B Proof of Theorem 3: The transition probabilities are parametrized as P(s′|s, a) = Pd i=1 θiPi(s′|s, a).
  • B Proof of Theorem 3: HdT is the resulting regret lower bound for the linear mixture model family.

C Implementation

The implementation derives tighter linear confidence intervals for UCRL-VTR by adapting linear-bandit concentration results to the linear MDP setting. It also specifies the corresponding estimator, assumptions, and implementation procedure.

  • Estimator: The estimator is obtained by minimizing a regularized least-squares loss, with λ serving as the regularizer.The linear-bandit formulation is used as the analytical analogue for the linear MDP problem.
  • Assumptions: The confidence-set derivation assumes a filtration generated by past states and actions, a true MDP model, conditionally subgaussian noise, and λ > 0.The matrix used in the MDP setting combines a regularizer with rank-one updates.
  • Noise assumptions: The target noise in the linear MDP setting is H/2-subgaussian because bounded value targets lie in [0, H].The analysis also states that the noise has conditional mean zero.
  • Confidence bounds: The linear MDP analysis adapts linear-bandit confidence bounds to construct tighter confidence sets for UCRL-VTR.The adaptation replaces the linear-bandit matrix and features with their linear-MDP counterparts.
  • Algorithm implementation: The implementation presents UCRL-VTR with tighter confidence bounds and initializes its matrix, weight vector, and parameter estimate.The implementation uses Algorithm 3 for the numerical experiments.
  • Tabular implementation: In tabular experiments, Ψ and Φ are identity matrices, while EG-Frequency stores transition counts and fits the estimated model.Tabular environments are treated as a special case of the linear model.

C.4.1 Futher Implementation Notes

UCRL-MIX combines the VTR and canonical models for optimistic planning while maintaining separate computations and confidence sets. Its implementation uses value iteration to select which model supplies each update.

  • Algorithm: UCRL-MIX introduces, analyzes, and evaluates a linear model-based RL algorithm using both canonical and VTR models for planning.The algorithm is implemented as a mixture of the two model-based approaches.
  • Planning procedure: The algorithm computes Algorithm 3 and UC-MatrixRL simultaneously, then performs value iteration at the end of each episode.The terminal value is set to zero before backward value updates.
  • Implementation: The implementation uses simultaneous model computation and conditional planning updates, with separate model-specific confidence calculations.This structure supports switching between VTR and canonical planning within each episode.
  • Planning procedure: During value iteration, UCRL-MIX uses the VTR model when its confidence bonus condition is met and otherwise updates Q using the canonical model.The value function is obtained by maximizing Q over actions.
  • Confidence sets: Using two models changes the confidence parameter from δ to δ/2, producing log(2/δ) inside the confidence-bound term.The adjustment follows from applying a union bound.

D.2 Numerical Results

The RiverSwim experiments compare UCRL-MIX’s regret and model errors with the corresponding VTR and canonical approaches. UCRL-MIX achieves nearly identical regret to UCRL-VTR and overwhelmingly plans with the VTR model.

  • Model error: Figure 5 plots model error for both the VTR and canonical models, which are both updated at the end of each episode.Only one model is used during planning in a given update.
  • Regret: UCRL-MIX’s cumulative regret is almost identical to UCRL-VTR’s cumulative regret on RiverSwim.The comparison is reported against Figure 2 from Section 6.3.
  • Model error: The VTR and canonical model errors are almost identical to those of UCRL-VTR and UC-MatrixRL, respectively.Figure 5 reports errors for both models even though only one is used for planning at a time.
  • Model selection: On RiverSwim, UCRL-MIX almost always uses the VTR model for planning rather than the canonical model.The frequency is calculated from observed VTR and canonical planning steps.
  • Model selection: The authors attribute the VTR preference to faster-shrinking confidence intervals and a narrower task-focused exploration objective.The canonical model explores more state-action-next-state tuples because it seeks a globally optimal model.
Loading 2006.01107v1…