Model-Based Reinforcement Learning with Value-Targeted Regression

• 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.Source: §1 · p. 2
• Value-targeted regression focuses model learning on task-relevant transition dynamics and can ignore dynamics irrelevant to the task.Source: §1 · p. 2
• The central question is whether value-targeted regression is sufficient and efficient for model-based online RL.Source: §1 · p. 2
• The regret bounds show that imperfect, non-stationary value targets do not cause the algorithm to get stuck, yielding sublinear regret.Source: §1 · p. 2
• 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.Source: §1 · p. 3
• For linear mixtures, the regret upper bound is ˜O(d√(H^3T)), with a corresponding lower bound described as close to it.Source: §1 · p. 3

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

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.Source: §3 · p. 5

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.Source: §3 · p. 5, §3.1 · p. 6

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.Source: §3.2 · pp. 6–7

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.Source: §3.2 · p. 7

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.Source: §3.3 · p. 7

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 ε′ ≥ ε.Source: §4 · p. 8
• 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.Source: §4 · p. 8

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.Source: §4 · p. 8

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.Source: §4 · p. 8
• 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.Source: §4 · p. 8

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.Source: §4 · pp. 8–9

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.Source: §4 · p. 9
• 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.Source: §4 · p. 9

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.Source: §5 · p. 9
• 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.Source: §5 · p. 9

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.Source: §5 · p. 9

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).Source: §5 · p. 10
• 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.Source: §5 · p. 10

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.Source: §5 · p. 10

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.Source: §5 · p. 10

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.Source: §6 · p. 10, Table 1 · p. 11

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.Source: §6.3 · p. 11, §6.1 · p. 11, Figure 1 · p. 12
• 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.Source: §6.3 · p. 12
• 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.Source: §6.3 · p. 12

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.Source: §6.3 · p. 12

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.Source: §6.1 · p. 11, §6.4 · pp. 12, 14

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.Source: §7 · p. 14
• The general regret bound depends on the Eluder dimension and metric entropy of an appropriately constructed function space.Source: §7 · p. 14
• 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.Source: §7 · p. 14
• The confidence-set analysis establishes that the true transition model belongs to Bk with probability 1 −δ for every k.Source: §A.4 · p. 21

A.5.2 Proof of Corollary 2

• N(P, α/H, ∥· ∥∞,1) is bounded by N(Θ, α/H, ∥· ∥1), linking model coverings to parameter-space coverings.Source: §A.5.2 · p. 23
• βK = H2(d + log(1/δ)) after suppressing logarithmic factors, log log terms, and constants.Source: §A.5.2 · p. 23
• 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 θ.Source: §A.5.2 · p. 23
• dimE(F, α) = ˜O(d) after dropping logarithmic terms.Source: §A.5.2 · p. 23

A.6 Proof of Theorem 5

• The construction uses conditionally σ-subgaussian martingale differences and concentration inequalities that hold simultaneously over all t.Source: §A.6 · p. 24
• 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α.Source: §A.6 · p. 25
• 4σ2 log(|G(α)|/δ) bounds the discretized concentration term after applying a union bound.Source: §A.6 · p. 25

B Proof of Theorem 3

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

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.Source: §C.1.2 · pp. 26–27

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.Source: §C.1.2 · pp. 27–28, §C.1.3 · p. 29

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.Source: §C.1.3 · p. 29

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.Source: §C.1.2 · p. 27, §C.1.3 · p. 29

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.Source: §C.2 · p. 30

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.Source: §C.4 · p. 32

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.Source: D Mixture Model · p. 32

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.Source: §D.1 · p. 33

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.Source: §D.1 · p. 33

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.Source: §D.1 · p. 33

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.Source: §D.1 · p. 33

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.Source: Figure 5 · p. 34

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.Source: §D.2 · p. 34

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.Source: §D.2 · p. 34, Figure 5 · p. 34

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.Source: §D.2 · p. 34, Figure 6 · p. 34
• 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.Source: §D.2 · p. 34