Model-based RL as a Minimalist Approach to Horizon-Free and Second-Order Bounds

Learning a transition model via Maximum Likelihood Estimation (MLE) followed by planning inside the learned model is perhaps the most standard and simplest Model-based Reinforcement Learning (RL) framework. In this work, we show that such a simple Model-based RL scheme, when equipped with optimistic and pessimistic planning procedures, achieves strong regret and sample complexity bounds in online and offline RL settings. Particularly, we demonstrate that under the conditions where the trajectory-wise reward is normalized between zero and one and the transition is time-homogenous, it achieves nearly horizon-free and second-order bounds.

Published as a conference paper at ICLR 2025 first-order regret bound which scales with the expected reward of the optimal policy. Thus our instancedependent bounds can be small under situations such as nearly-deterministic systems or the optimal policy having a small value. When specializing to the case of deterministic ground truth transitions (but the algorithm does not need to know this a priori), we show that these simple MBRL algorithms demonstrate a faster convergence rate than the worst-case rates. The key message of our work is Simple and standard MLE-based MBRL algorithms are sufficient for achieving nearly horizon-free and second-order bounds in online and offline RL with function approximation.

We provide a fairly standard analysis to support the above claim. Our analysis follows the standard frameworks of optimism/pessimism in the face of uncertainty. For online RL. we use ℓ 1 Eluder dimension (Liu et al., 2022; Wang et al., 2024a), a condition that uses both the MDP structure and the function class, to capture the structural complexity of exploration. For offline RL, we use the similar concentrability coefficient in Ye et al. ( 2024) to capture the coverage condition of the offline data.

The key technique we leverage is the triangular discrimination -a divergence that is equivalent to the squared Hellinger distance up to some universal constants. Triangular discrimination was used in contextual bandit and model-free RL for achieving first-order and second-order instance-dependent bounds (Foster & Krishnamurthy, 2021;Wang et al., 2023 Wang et al., , 2024a)). Here we show that it also plays an important role in achieving horizon-free bounds. Our contributions can be summarized as follows. 1. Our results extend the scope of the prior work on horizon-free RL which only applies to tabular MDPs or MDPs with linear functions. Given a finite model class P (which could be exponentially large), we show that in online RL, the agent achieves an

regret, where K is the number of episodes, d RL is the ℓ 1 Eluder dimension, VaR π k is the variance of the total reward of policy π k learned in episode k and δ ∈ (0, 1) denotes the failure probability. Similarly, for offline RL, the agent achieves an O (

finding a comparator policy π * , where C π * is the single policy concentrability coefficient over π * , K denotes the number of offline trajectories, VaR π * is the variance of the total reward of π * . For offline RL with finite P, our result is completely horizon-free, not even with log H dependence.

2. When specializing to MDPs with deterministic ground truth transition (but rewards, and models in the model class could still be stochastic), we show that the same simple MBRL algorithms can adapt to the deterministic environment and achieve a better statistical complexity. For online RL, the regret becomes O(d RL log(KH|P|/δ)), which only depends on the number of episodes K poly-logarithmically. For offline RL, the performance gap to a comparator policy π * becomes O (C π * log(|P|/δ)/K), which is tighter than the worst-case O(1/ √ K) rate. All our results can be extended to continuous model class P using bracket number as the complexity measure.

Overall, we identify the minimalist algorithms and analysis for nearly horizon-free and instancedependent (first & second-order) online & offline RL. By saying "minimalist" we mean the algorithm designs and analysis are much simpler than previous work on horizon-free and second-order RL.

Model-based RL. Learning transition models with function approximation and planning with the learned model is a standard approach in RL and control. In the control literature, certainty-equivalence control learns a model from some data and plans using the learned model, which is simple but effective for controlling systems such as Linear Quadratic Regulators (LQRs) (Mania et al., 2019). In RL, such a simple model-based framework has been widely used in theory with rich function approximation, for online RL (