Model-free Posterior Sampling via Learning Rate Randomization

🎯 Pitch

Randomized Q-learning (RandQL) achieves the exploration of posterior sampling without a model by simply injecting Beta noise into the learning rate—replacing explicit bonuses entirely. This yields the first provably efficient, model-free algorithm that matches the regret bounds of bonus-based approaches, while empirically outperforming them.

1. Executive Summary

This paper introduces Randomized Q-learning (RandQL), a novel model-free algorithm for regret minimization in episodic MDPs that achieves exploration without bonuses through learning rate randomization — injecting Beta-distributed noise into Q-learning updates to replicate the exploration behavior of posterior sampling (PSRL) in a computationally tractable way. The authors analyze RandQL in both tabular and metric space settings using the standard episodic MDP framework, proposing a staged variant (Staged-RandQL) that achieves a regret bound of Ỡ(√(H⁵SAT)) in tabular MDPs and an extension (Net-Staged-RandQL) that achieves Ỡ(H⁵/² T^((dc+1)/(dc+2))) in metric spaces with covering dimension dc — matching the order of existing bonus-based model-free algorithms like OptQL while eliminating the need for explicit optimism bonuses. Experiments on grid-world and continuous environments demonstrate that RandQL outperforms OptQL and is competitive with model-based Bayesian approaches like PSRL, establishing that posterior-sampling-style exploration can be realized in a provably efficient model-free algorithm through learning rate randomization alone.

2. Context and Motivation

The Core Problem: Model-Free Posterior Sampling Is Intractable

The fundamental question this paper tackles is deceptively simple: can we build a provably efficient model-free algorithm that explores like posterior sampling? This matters because it sits at the intersection of two major threads in reinforcement learning theory — the practical simplicity of model-free algorithms and the empirical success of Bayesian exploration — and prior to this work, no one had successfully unified them in a computationally tractable way.

To understand why this is hard, we need to understand what posterior sampling (PSRL) does. In a model-based setting, PSRL maintains a Bayesian posterior over the MDP's transition dynamics — typically a Dirichlet posterior over transition probabilities if rewards are known, as described by Strens [2000] and Osband et al. [2013]. At each episode, PSRL samples an entire MDP from this posterior, solves it to find the optimal policy, and executes that policy. The act of sampling from the posterior naturally balances exploration and exploitation: if a state-action pair has been visited many times, the posterior is concentrated around the true transition, so the sampled MDP is close to the real one; if a state-action pair is rarely visited, the posterior is diffuse, so the sampled transitions vary wildly, creating the kind of optimistic "what if this rarely-tried action leads somewhere great?" behavior that drives exploration.

The problem is that this procedure is inherently model-based: you sample transition probabilities, then solve the sampled MDP, which requires knowing or learning a model. Converting this to a model-free setting — where you directly learn Q-values without explicitly modeling transitions — is nontrivial because posterior sampling operates over the model, not directly over values.

Why This Matters: The Model-Free vs. Model-Based Tension

This gap is significant for several interconnected reasons the paper surfaces in Section 1:

Practical advantages of model-free algorithms. Model-free approaches, particularly Q-learning variants, dominate much of modern deep RL — from Atari games (Mnih et al., 2013) to continuous control (Lillicrap et al., 2016; Haarnoja et al., 2018). Their appeal is practical: they require no explicit model learning, have lower space and time complexity (as Table 2 in Appendix I quantifies — RandQL achieves Ỡ(H) per-episode time vs. Ỡ(HS²A) for UCBVI), and are often simpler to implement. If posterior-sampling-style exploration could be realized in a model-free algorithm, it could be directly plugged into existing Q-learning pipelines.

Empirical superiority of Bayesian exploration. On the other side, Bayesian exploration methods like PSRL and RLSVI have consistently outperformed bonus-based exploration in empirical studies, at least in tabular settings (Osband et al., 2013; Osband and Van Roy, 2017). These methods have also been successfully adapted to deep RL through techniques like bootstrapped DQN (Osband et al., 2016), Noisy Nets (Fortunato et al., 2018), and HyperDQN (Li et al., 2022). Practitioners have strong empirical reasons to prefer randomized exploration over optimism bonuses, but the theoretical guarantees for these methods have been limited to model-based settings.

The gap. The paper explicitly frames this tension in Section 1:

"most of the theoretical studies on Bayesian-based exploration have focused on model-based algorithms, raising the natural question of whether the PSRL approach can be extended to a provably efficient model-free algorithm that matches the good empirical performance of its model-based counterparts."

Prior Work and Its Limitations

The paper identifies several strands of prior work, each of which partially addresses the problem but leaves the core gap unresolved.

Bonus-Based Model-Free Exploration: OptQL

The dominant approach to provably efficient model-free exploration has been optimism bonuses. Jin et al. [2018] proposed OptQL, which adds explicit upper-confidence-bound bonuses to Q-learning targets, achieving a regret bound of Ỡ(√(H⁵SAT)). Zhang et al. [2020] later refined this with variance reduction and Bernstein-type bonuses, achieving near-optimal sample complexity.

The key mechanism in OptQL is straightforward: when updating Q(s,a), instead of using the standard target r + V(s'), OptQL uses r + V(s') + b(s,a), where b(s,a) is a bonus that decays with the visit count — large for rarely-visited state-action pairs, small for frequently-visited ones. This inflates the Q-values of under-explored actions, making the agent optimistically try them.

Where this falls short. While theoretically sound, bonus-based exploration has several practical drawbacks. The bonus magnitudes require careful tuning of constants that depend on problem parameters (S, A, H, T), and in practice, these theoretical bonuses are often replaced with simplified heuristics (as the authors themselves do in their experiments — see Appendix I, where they use a simplified bonus of the form min(√(1/n) + (H-h+1)/n, H-h+1) rather than the theoretically justified Hoeffding bonus). Empirically, bonus-based methods like OptQL underperform Bayesian approaches like PSRL, as the paper's own experiments confirm (Figure 1 in Section 5).

Model-Based Posterior Sampling: PSRL and RLSVI

PSRL (Osband et al., 2013) and its optimistic variant OPSRL (Agrawal and Jia, 2017; Tiapkin et al., 2022a) provide the gold standard for Bayesian exploration in tabular MDPs. In PSRL, the agent maintains Dirichlet posteriors over transition probabilities and samples a new MDP at each episode. OPSRL adds optimism by drawing multiple samples and acting according to the most optimistic one.

RLSVI (Osband et al., 2013; Russo, 2019) takes a different Bayesian approach: it places a Gaussian prior directly on the optimal Q-values and updates the posterior through value iteration within a learned model. This is still model-based because value iteration requires knowledge of the transition dynamics, even if those dynamics are learned rather than given.

Where these fall short for model-free goals. These methods are fundamentally model-based — they either explicitly sample transition probabilities (PSRL) or perform value iteration over a learned model (RLSVI). Converting them to a model-free setting requires figuring out how to replicate the effect of posterior sampling without ever constructing a model. This is the gap RandQL aims to fill.

The One Prior Attempt: Dann et al. (2021)

The paper explicitly acknowledges the only previous attempt at model-free posterior sampling:

"Recently, Dann et al. [2021] proposed a model-free posterior sampling algorithm for structured MDPs, however, it is not computationally tractable."

This is a crucial reference point. Dann et al. [2021] showed that model-free posterior sampling is possible in principle for linear MDPs and other structured settings, but their algorithm involves solving an intractable optimization problem at each step. The paper positions RandQL as the first tractable model-free posterior sampling algorithm — one whose computational cost is comparable to standard Q-learning (Ỡ(H) per episode) rather than requiring exponential-time inference.

Metric Space RL: Prior Approaches

For the metric space extension, the paper builds on a line of work adapting RL algorithms to continuous state-action spaces:

Kernel-UCBVI by Domingues et al. [2021c] extends UCBVI to metric spaces using kernel-based function approximation. However, the paper notes (Section 4.3) that kernel methods fail to achieve optimal dependence on T due to the hardness of transition estimation in continuous spaces.
Net-QL by Song and Sun [2019] and Adaptive-QL by Sinclair et al. [2019, 2023] extend OptQL to metric spaces using fixed ε-net discretization (Net-QL) or adaptive discretization (Adaptive-QL). These achieve regret bounds of order Ỡ(T^((dc+1)/(dc+2))) where dc is the covering dimension, matching the lower bound of Ω(HT^((dc+1)/(dc+2))) established by Sinclair et al. [2023].

RandQL's metric extensions (Net-Staged-RandQL and Adaptive-Staged-RandQL) follow the same discretization frameworks as Net-QL and Adaptive-QL, but replace OptQL's bonus mechanism with RandQL's learning rate randomization. This achieves the same regret rates while keeping the Bayesian exploration properties.

The Core Technical Insight: How RandQL Bridges the Gap

The paper's central conceptual move is recognizing a mathematical connection between posterior sampling and learning rate randomization that had not been previously exploited. This insight is developed in Section 3.1 and Appendix C, but I'll unpack it here because it's essential for understanding why this approach exists in the first place.

When PSRL samples from a Dirichlet posterior over transitions, the resulting Q-values can be expressed as a weighted sum of observed targets plus prior values, where the weights follow a Dirichlet distribution. Specifically, if you unfold the PSRL procedure for a state-action pair visited n times, the Q-value estimate takes the form:

$Q(s,a) = \tilde{W}_0 \cdot \text{prior} + \sum_{i=1}^{n} \tilde{W}_i \cdot \text{target}_i$

where (W̃₀, ..., W̃ₙ) ∼ Dir(n₀, 1, ..., 1) with n₀ being prior pseudo-counts.

Now, here's the key observation: Dirichlet-distributed weights can be generated from products of independent Beta random variables. Specifically, if w₁, ..., wₙ are independent with w_i ∼ Beta(1, n₀ + i - 1), then the weights defined by:

$W_i = w_i \prod_{j=i+1}^{n} (1 - w_j)$

will be Dirichlet-distributed. This is exactly the stick-breaking construction of the Dirichlet distribution.

Now compare this to how Q-learning updates work. With a learning rate α, Q-learning performs:

$Q_{\text{new}} = (1 - \alpha) Q_{\text{old}} + \alpha \cdot \text{target}$

Unfolding this over n updates gives:

$Q_n = \left(\prod_{i=1}^{n} (1 - \alpha_i)\right) Q_0 + \sum_{i=1}^{n} \left(\alpha_i \prod_{j=i+1}^{n} (1 - \alpha_j)\right) \cdot \text{target}_i$

The structure is identical to the PSRL weight formula! If the learning rates α_i are sampled as independent Beta random variables rather than being deterministic, the resulting weighted sum has the same Dirichlet distribution as the posterior sampling weights, up to choice of Beta parameters.

This is the core insight that makes RandQL possible: by randomizing the learning rates in a Q-learning update to follow a Beta distribution, you can replicate the exploration behavior of posterior sampling without ever constructing a model or maintaining a posterior over transitions. The learning rates become the bridge between model-based Bayesian inference and model-free stochastic approximation.

How the Paper Positions Itself

Within this landscape, the paper positions RandQL not as a radically new exploration paradigm, but as a translation of PSRL's posterior sampling mechanism into a model-free form. The key claims about this translation:

It inherits PSRL's exploration properties. By matching the weight distribution, RandQL induces the same "optimism through randomization" that makes PSRL effective — rarely-visited state-action pairs get noisier updates, creating the same exploratory drive.
It avoids the need for bonuses. Unlike OptQL and other model-free methods, RandQL's exploration emerges naturally from the stochastic learning rates, not from explicit bonus terms that require parameter tuning.
It is computationally tractable. Unlike Dann et al. [2021], RandQL's per-step cost is comparable to standard Q-learning: the Beta sampling and maximization over the ensemble add only a constant-factor overhead (J = Ỡ(1) ensemble size), not an exponential blowup.
It scales to metric spaces. By combining learning rate randomization with standard discretization techniques (ε-nets or adaptive partitions), RandQL extends to continuous state-action spaces while preserving the regret guarantees of existing bonus-based methods.

The paper's staged variant (Staged-RandQL) serves an important analytical purpose: it simplifies the proof by resetting Q-value estimates at each stage, avoiding the technical complications of the non-staged RandQL's rapid prior forgetting. But conceptually, both variants implement the same idea — Beta-distributed learning rates as a stand-in for posterior sampling.

Analogies That Clarify the Contribution

You can think of OptQL and RandQL as two different ways to be optimistic in model-free RL:

OptQL says: "I'll add a bonus to my target value, making uncertain actions look artificially good, so I try them."
RandQL says: "I'll randomize how much I trust each observation, sometimes over-weighting early observations and sometimes ignoring them, creating a distribution over possible Q-values that mirrors what I'd get if I sampled from a posterior over the environment."

Both achieve optimism — RandQL through the "maximum over ensemble" mechanism (like OPSRL) — but through fundamentally different mechanisms. The advantage of the randomized approach is that it naturally adapts its exploration intensity to the data without requiring manually calibrated bonus coefficients.

Why Now?

The timing of this work is notable. By 2023, the RL theory community had largely settled on two parallel tracks — model-based posterior sampling (PSRL, RLSVI) with near-optimal guarantees, and model-free bonus-based methods (OptQL, variants) with near-optimal guarantees. The deep RL community had embraced randomized exploration (BootDQN, Noisy Nets, HyperDQN) but without theoretical guarantees. RandQL fills the remaining gap: a provably efficient, tractable, model-free algorithm that uses randomization for exploration. It doesn't improve on the best-known regret bounds (it matches OptQL's Ỡ(√(H⁵SAT)) rather than achieving the optimal Ỡ(√(H³SAT))), but it opens a path for model-free Bayesian exploration methods to achieve the same theoretical standing as their model-based counterparts.

3. Technical Approach

3.1 Reader orientation (approachable technical breakdown)

What the system is: RandQL is a model-free reinforcement learning algorithm that learns to act optimally in unknown environments by maintaining an ensemble of Q-value estimates, each updated with randomly perturbed learning rates, and then acting greedily with respect to the most optimistic Q-value in the ensemble.

What problem it solves and the "shape" of the solution: The problem is exploration without a model — how can an agent that directly learns action values (Q-learning) explore as effectively as an agent that maintains a full probabilistic model of the environment (posterior sampling)? The solution is to recognize that posterior sampling over transition models induces a specific distribution over Q-value estimates — a Dirichlet-weighted average of observed targets — and that this same distribution can be replicated in a model-free way by performing Q-learning updates with Beta-distributed random learning rates. The algorithm then takes the maximum over J independent such randomized Q-estimates (ensemble optimism) to drive exploration, completely replacing the explicit bonus terms used in prior model-free methods.

3.2 Big-picture architecture (diagram in words)

The RandQL system has five major components:

Base Q-learning Engine — performs standard asynchronous Q-learning updates (combining old Q-values with new targets) but with randomized learning rates drawn from Beta distributions, not fixed step sizes.
Randomized Learning Rate Generator — for each state-action visit, samples independent Beta-distributed random variables that serve as the mixing coefficients between old estimates and new observations. The Beta parameters depend on the visit count and a prior pseudo-count, encoding the "strength" of the posterior.
Ensemble of Temporary Q-values (J copies) — maintains J parallel Q-value estimates for each state-action pair, each updated with its own independent stream of randomized learning rates. These J copies represent independent samples from the induced posterior over Q-values.
Optimism via Ensemble Maximum — the policy Q-value is defined as the maximum over the J ensemble members. This creates an upper-confidence-bound effect: if any ensemble member is optimistic about a state-action pair (due to its particular random learning rates), the agent will try it.
Stage-Based Reset Mechanism (Staged-RandQL only) — to simplify analysis and avoid the bias from rapidly-decaying prior influence, the learning process is split into stages of exponentially growing length. At each stage boundary, temporary Q-values are reset to an optimistic prior value, ensuring the prior continues to influence exploration throughout learning.

Information flow: An episode begins → the agent visits state s at step h → it selects action a = argmax over the policy Q-values Q(s,a) → it observes reward r and next state s' → it samples J independent Beta random learning rates (with parameters depending on the visit count n of (s,a,h) and the prior pseudo-count n₀) → each of the J ensemble members updates its temporary Q-value for (s,a) by mixing the old estimate with the new target [r + V(s')] using its own random learning rate → when a stage ends (visit count reaches a threshold), the policy Q-value for (s,a) is set to the maximum over the J ensemble members and the temporary Q-values are reset to the prior → the value function V(s) is updated as the maximum over actions of the policy Q-values → the episode continues.

3.3 Roadmap for the deep dive

First, the weight distribution connection — how Beta learning rates induce Dirichlet-distributed weights, and why this precisely mirrors the PSRL posterior sampling mechanism. This is the mathematical foundation without which nothing else makes sense.
Second, the ensemble construction and optimism mechanism — how maintaining J independent Q-estimates and taking the maximum creates upper-confidence-bound exploration, including the anti-concentration inequality that guarantees optimism with high probability.
Third, the temporary Q-value update rule — the specific recursive formula that combines Beta learning rates with targets, the prior re-injection mechanism (in RandQL) or stage-based reset (in Staged-RandQL), and why aggressive learning rates (Beta(H, n) rather than Beta(1, n)) are needed to combat bias.
Fourth, the staged framework (Staged-RandQL) — the stage definition, the reset mechanism, the update schedule, and how this simplifies the analysis while preserving the exploration mechanism. This is the version with theoretical guarantees.
Fifth, the metric space extension (Net-Staged-RandQL and Adaptive-Staged-RandQL) — how the algorithm adapts to continuous state-action spaces through fixed or adaptive discretization, the crucial role of stage-dependent prior counts to absorb approximation error, and the algorithmic differences from the tabular case.

3.4 Detailed, sentence-based technical breakdown

This is primarily a theoretical algorithm design paper whose core idea is that Beta-distributed random learning rates in Q-learning updates induce Dirichlet-distributed weights over historical targets, replicating the exploration behavior of posterior sampling without requiring a model, and that taking the maximum over an ensemble of such randomized Q-estimates creates optimism.

The Weight Distribution Connection: From Beta Learning Rates to Dirichlet Weights

The central mathematical insight is that randomized learning rates transform a Q-learning update into a posterior sampling update. To see this, consider what happens when we repeatedly update a Q-value estimate for a fixed state-action pair (s,a) at step h. Let the pair be visited n times, with the i-th visit producing a target value $T_i = r_h(s,a) + V_{h+1}(s_{i+1})$ , where $s_{i+1}$ is the next state observed on the i-th visit and V is the current value function estimate. If we start from an initial estimate $Q_0$ and apply a sequence of Q-learning updates with learning rates $\alpha_1, \alpha_2, \ldots, \alpha_n$ , unfolding the recursion:

$Q_n = \left(\prod_{i=1}^{n} (1 - \alpha_i)\right) Q_0 + \sum_{i=1}^{n} \left(\alpha_i \prod_{j=i+1}^{n} (1 - \alpha_j)\right) T_i$

where $Q_n$ is the Q-estimate after n updates, $\alpha_i \in (0,1)$ is the learning rate used on the i-th update, $Q_0$ is the initial estimate (the prior), and $T_i$ is the target value from the i-th visit.

What it computes: the current Q-estimate as a convex combination of the initial prior and all observed targets, where the weight on the i-th target is the product of the i-th learning rate and the complements of all subsequent learning rates — essentially, how much of the i-th observation survives after all later updates have partially overwritten it.

Why this form: this follows directly from applying the Q-learning update formula $Q_{\text{new}} = (1-\alpha)Q_{\text{old}} + \alpha T$ recursively n times. Each update replaces an α-fraction of the old estimate with the new target. The weight on the initial prior is the fraction that was never replaced: the product of $(1-\alpha_i)$ over all updates. The weight on the i-th target is the fraction introduced at step i (the $\alpha_i$ term) times the fraction of that contribution that survived subsequent updates (the product of $(1-\alpha_j)$ for j > i). This is algebraically exact — no approximations.

Now, the critical observation from Appendix C: if the learning rates $\alpha_i$ are independent Beta-distributed random variables rather than deterministic scalars, then the resulting weight vector has a known distribution. Specifically, if for $i = 0, 1, \ldots, n-1$ we define:

$W^0_n = \prod_{q=0}^{n-1} (1 - w_q), \quad W^i_n = w_{i-1} \cdot \prod_{q=i}^{n-1} (1 - w_q) \text{ for } i \geq 1$

where $w_q \sim \text{Beta}(1/\kappa, (q + n_0)/\kappa)$ are independent Beta random variables, $\kappa > 0$ is a posterior inflation coefficient, and $n_0$ is a prior pseudo-count, then the random vector $(W^0_n, W^1_n, \ldots, W^n_n)$ has a Dirichlet distribution:

$(W^0_n, W^1_n, \ldots, W^n_n) \sim \text{Dir}(n_0/\kappa, 1/\kappa, \ldots, 1/\kappa)$

where $\text{Dir}(\alpha_0, \alpha_1, \ldots, \alpha_n)$ denotes the Dirichlet distribution with concentration parameters $\alpha_0, \ldots, \alpha_n$ , which generates vectors of length n+1 that sum to 1.

What this means operationally: when we use Beta-distributed learning rates in our Q-learning updates, the final Q-estimate after n visits is a random convex combination of the prior $Q_0$ and the n observed targets, where the weight vector is sampled from a Dirichlet distribution whose first concentration parameter is proportional to the prior strength $n_0$ and whose remaining parameters are all $1/\kappa$ .

Why this matters — the PSRL connection: in the model-based PSRL algorithm, when using a Dirichlet prior on transition probabilities with pseudo-count $n_0$ per state-action pair, the resulting Q-value for a state-action pair visited n times can be expressed (see equation (1) in Section 3.1 and the derivation in Appendix C) as:

$Q^{\text{PSRL}}(s,a) = \tilde{W}^0 \cdot \text{prior} + \sum_{i=1}^{n} \tilde{W}^i \cdot T_i^{\text{PSRL}}$

where $(\tilde{W}^0, \tilde{W}^1, \ldots, \tilde{W}^n) \sim \text{Dir}(n_0, 1, \ldots, 1)$ . The weight distribution is the same family (Dirichlet) with the same structure: the first parameter corresponds to the prior, and the remaining parameters correspond to observations. The only difference is that PSRL uses $\text{Dir}(n_0, 1, \ldots, 1)$ while RandQL with $\kappa = 1$ would give $\text{Dir}(n_0, 1, \ldots, 1)$ exactly. The posterior inflation coefficient $\kappa$ generalizes this to $\text{Dir}(n_0/\kappa, 1/\kappa, \ldots, 1/\kappa)$ , which scales the concentration (and thus the variance) of the Dirichlet.

The operational consequence is profound: a Q-learning update with Beta-distributed learning rates produces a Q-estimate that is statistically indistinguishable from a posterior sample over Q-values induced by a Dirichlet prior on transition probabilities. The algorithm never models transitions — it just randomizes learning rates — yet the resulting distribution over Q-values matches what PSRL would produce.

The Dirichlet generation mechanism (stick-breaking): Lemma 3 in Appendix D.1 formalizes this connection using the stochastic representation of the Dirichlet distribution. The standard way to generate a Dirichlet vector $(X_0, X_1, \ldots, X_n) \sim \text{Dir}(\alpha_0, \alpha_1, \ldots, \alpha_n)$ is through the stick-breaking process: sample $Z_i \sim \text{Beta}(\alpha_i, \sum_{j=i+1}^n \alpha_j)$ independently, then set $X_0 = Z_0$ , $X_i = Z_i \prod_{j=0}^{i-1} (1 - Z_j)$ for $i \geq 1$ , and $X_n = 1 - \sum_{i=0}^{n-1} X_i$ . For the specific case where $\alpha_1 = \ldots = \alpha_n = 1/\kappa$ and $\alpha_0 = n_0/\kappa$ , the Beta parameters at step i become $\text{Beta}(1/\kappa, (n-i+n_0)/\kappa)$ . Reversing the order (going from most recent to oldest observation) gives the parameters $\text{Beta}(1/\kappa, (i + n_0)/\kappa)$ used in RandQL. This is exactly how the independent Beta learning rates collectively generate Dirichlet-distributed aggregate weights.

A subtle point — the target values differ: in PSRL, the target $T_i^{\text{PSRL}}$ uses the current (posterior-sampled) value function at the time of recomputation, not the value function at the time of observation. RandQL approximates this by using the value function $V^{\ell_i}_{h+1}$ that was available when the i-th target was originally observed. This is the "lazy" approximation — we don't recompute all historical targets every time the value function updates. This creates a temporal bias that the aggressive learning rates (Beta(H, ·) rather than Beta(1, ·)) and the staged framework are designed to mitigate, as discussed next.

The Temporary Q-Value Update Rule and Prior Management

The core algorithmic primitive is the update rule for temporary Q-values, defined identically for both RandQL (Algorithm 2 in Appendix B) and Staged-RandQL (Algorithm 1 in Section 3.2), but with different prior reinjection strategies. For a fixed state-action pair $(s,a)$ at step $h$ , let $n = n^t_h(s,a)$ be the number of visits before episode $t$ , and let the current episode's observation be $(s^t_h = s, a^t_h = a, s^t_{h+1})$ . For each ensemble member $j \in [J]$ :

$\tilde{Q}^{t+1,j}_h(s,a) = (1 - w_{j,n}) \cdot \tilde{Q}^{t,j}_h(s,a) + w_{j,n} \cdot \left[r_h(s,a) + V^t_{h+1}(s^t_{h+1})\right]$

where $w_{j,n} \sim \text{Beta}(1/\kappa, (n + n_0)/\kappa)$ is an independent Beta random variable, $\kappa > 0$ is the posterior inflation coefficient, $n_0$ is the number of prior pseudo-transitions, $\tilde{Q}^{t,j}_h(s,a)$ is the j-th temporary Q-value before the update, and $V^t_{h+1}(s^t_{h+1})$ is the current optimistic value estimate of the next state.

What it computes: each ensemble member updates its Q-estimate by mixing the old estimate with the new observation's target, using a Beta-distributed mixing weight. Unlike standard Q-learning where $\alpha$ is deterministic, here $w_{j,n}$ is random — sometimes it's close to 0 (trust old estimate), sometimes close to 1 (heavily weight new observation). The Beta parameters encode prior strength: $1/\kappa$ controls responsiveness to new data, $(n + n_0)/\kappa$ encodes cumulative evidence (visits plus pseudo-visits).

Why the Beta parameters take this form: $1/\kappa$ is the "pseudo-count" contributed by each new observation in the posterior (small = each observation has limited individual influence), and $(n+n_0)/\kappa$ is the total pseudo-count of the prior plus all previous observations (large = the old estimate has substantial weight). The ratio $\mathbb{E}[w_{j,n}] = (1/\kappa) / (1/\kappa + (n+n_0)/\kappa) = 1/(1 + n + n_0)$ — on expectation, the learning rate behaves like $1/(n + n_0 + 1)$ , which is the standard Bayesian posterior mean update. But the randomness around this mean is crucial for exploration.

The prior re-injection problem: a major technical challenge arises from the aggressiveness of the learning rates. With $w \sim \text{Beta}(H, n)$ (in the non-staged RandQL, the first parameter is $H$ rather than $1$ ), the expected learning rate is $H/(H+n)$ , meaning after $H$ visits, the cumulative weight on the prior is approximately $(1 - H/(H+1))^H \approx e^{-1}$ — it decays exponentially fast. This means the prior's exploratory influence vanishes after only about $H$ visits, which is too fast for effective exploration (you need the prior to keep pulling you toward trying under-explored actions throughout learning). To combat this, RandQL (Algorithm 2) re-injects the prior on every update through a mixture target:

$\mathring{Q}^{t,j}_h(s,a) = \mathring{w}_{j,n} \cdot [r_h(s,a) + V^t_{h+1}(s^t_{h+1})] + (1 - \mathring{w}_{j,n}) \cdot [r_h(s,a) + r_0(H - h - 1)]$

where $\mathring{w}_{j,n} \sim \text{Beta}(n, n_0)$ is another independent Beta random variable (with parameters n for empirical evidence and n₀ for prior evidence), and $r_0(H - h - 1)$ is the prior target — an optimistic pseudo-reward $r_0 = 2$ scaled by the remaining horizon, representing the maximum conceivable value from a yet-unexplored state. This prior target replaces the "actual" target $V^t_{h+1}$ in $(1-\mathring{w})$ fraction of the update. The outer update then becomes:

$\tilde{Q}^{t+1,j}_h(s,a) = (1 - w_{j,n}) \tilde{Q}^{t,j}_h(s,a) + w_{j,n} \cdot \mathring{Q}^{t,j}_h(s,a)$

Why re-injection is necessary: without it, the expected weight on the prior $Q_0$ after n updates (unfolding the recursion) would be $\mathbb{E}[W^0_n] = \prod_{i=1}^n (1 - \mathbb{E}[w_i]) = \prod_{i=1}^n (1 - H/(H+i+n_0)) \sim n^{-H}$ , which decays polynomially with exponent H for $\text{Beta}(H, \cdot)$ rates. With re-injection, the effective weight becomes of order $n_0/(n + n_0)$ — matching the standard Bayesian prior forgetting rate. The temporary target $\mathring{Q}^{t,j}$ mixes in the prior on every single update, preventing the prior from being exponentially forgotten.

The staged alternative (Staged-RandQL): rather than re-injecting the prior on every update, Staged-RandQL takes a simpler approach: it resets the temporary Q-values to the prior value at the beginning of each stage. A stage for $(s,a,h)$ begins when its visit count reaches a threshold $\sum_{i=0}^{k-1} e_i$ where $e_k = \lfloor (1 + 1/H)^k \cdot H \rfloor$ is the length of stage k. At stage entry:

$\tilde{Q}^{t,j}_h(s,a) = r_h(s,a) + r_0(H - h - 1)$

This reset ensures that at the start of each stage, the temporary Q-values are re-anchored to the optimistic prior, and within the stage, updates use Beta-distributed rates without additional prior mixing. The stage lengths grow as $(1 + 1/H)^k$ , meaning the prior's influence is refreshed at exponentially spaced intervals. By the time the prior would have been forgotten within a stage (after roughly H visits), a new stage begins and re-establishes it.

Why the staged version is preferred for analysis: the reset at stage boundaries decouples the estimates across stages, simplifying the concentration analysis. Within a stage of length $e_k$ , the Q-estimate uses only the $e_k$ targets observed during that stage (plus the prior value), and the weight distribution is exactly $\text{Dir}(n_0/\kappa, 1/\kappa, \ldots, 1/\kappa)$ with $e_k$ ones — matching the PSRL weight distribution without the complications of prior decay analysis. The stage-based approach is essential for the proof (Appendix D) but empirically, the non-staged RandQL with prior re-injection converges faster (Figure 2 in Appendix I), so both versions have practical relevance.

The Ensemble Construction and Optimism Mechanism

RandQL maintains $J$ independent temporary Q-value estimates for each state-action pair, indexed by $j \in [J]$ . Each copy receives its own independent stream of Beta-distributed learning rates, so each evolves along a different random trajectory — they are independent samples from the induced posterior over Q-values. The policy Q-value is defined as the pointwise maximum over the ensemble:

$Q^{t+1}_h(s,a) = \max_{j \in [J]} \tilde{Q}^{t+1,j}_h(s,a)$

where $Q^{t+1}_h(s,a)$ is the policy Q-value used for action selection at the next episode, and $\tilde{Q}^{t+1,j}_h(s,a)$ are the J independent temporary estimates after the current update. In Staged-RandQL, this maximum is computed only at the end of each stage (when the stage's visit counter reaches its threshold); within a stage, the temporary Q-values evolve but the policy Q-value remains fixed at the value set at the previous stage boundary.

What it computes: for each state-action pair, the algorithm takes the most optimistic Q-estimate among J independent posterior samples. If any of the J copies happens to be optimistic about the value of taking action a in state s (due to its particular random learning rates having given high weight to promising-looking targets), that optimistic value becomes the one the agent believes and acts on.

Why this creates optimism — the anti-concentration argument: Proposition 1 (Section D.3) provides the core guarantee. Let $V^\star_{h+1}$ be the true optimal value function, and consider the Dirichlet-weighted sum of true optimal values that would arise if the targets were the optimal values (rather than the estimated values):

$S_j = W^0_{j,n} \cdot r_0(H - h - 1) + \sum_{i=1}^n W^i_{j,n} \cdot V^\star_{h+1}(s_{\ell_i})$

where the weights $(W^0, \ldots, W^n) \sim \text{Dir}(n_0/\kappa, 1/\kappa, \ldots, 1/\kappa)$ are the Dirichlet-distributed aggregate weights, $r_0(H-h-1)$ is the optimistic prior value (upper bound on $V^\star$ ), and $V^\star_{h+1}(s_{\ell_i})$ are the true optimal values at the states visited on the i-th observation. Proposition 1 shows that:

$P\left(\max_{j \in [J]} S_j \geq p_h V^\star_{h+1}(s,a) \mid \text{data}\right) \geq 1 - \frac{\delta}{2SAHT}$

provided $J \geq \lceil c_J \cdot \log(2SAHT/\delta) \rceil$ where $c_J = 1 / \log(2/(1 + \Phi(1))) \approx 1 / \log(1.19) \approx 5.3$ , $\Phi(\cdot)$ is the standard normal CDF, and $\kappa = 2\beta^\star(\delta, T)$ is tuned to match the Kullback-Leibler divergence between the empirical and true target distributions.

What this means in plain English: if we had access to the true optimal values $V^\star$ at the observed next states, then with $J \approx 5.3 \cdot \log(2SAHT/\delta)$ (which is $\tilde{O}(1)$ — logarithmic in all problem parameters), taking the maximum over J independent Dirichlet-weighted averages would exceed the true expected optimal value $p_h V^\star_{h+1}(s,a)$ with probability at least $1 - \delta/(2SAHT)$ . Since this holds for all state-action pairs simultaneously (by union bound), the policy Q-values are optimistic upper bounds on the true optimal Q-values throughout the entire learning process with high probability.

The proof mechanism (Theorem 5, Appendix G.2): the anti-concentration inequality works by lower-bounding the probability that a single Dirichlet-weighted sum exceeds its mean. For a fixed $j$ , a result of Tiapkin et al. [2022a] (Theorem 5 in Appendix G.2) shows:

$P(S_j \geq \mu) \geq (1 - \varepsilon) \cdot P_{g \sim \mathcal{N}(0,1)}\left(g \geq \sqrt{2n \cdot \text{K}_{\inf}(\bar{\nu}_n, \mu)}\right)$

where $\mu = p_h V^\star_{h+1}(s,a)$ is the true mean, $\bar{\nu}_n$ is the empirical distribution of the observed $V^\star_{h+1}$ values (plus a prior atom at $r_0(H-h-1)$ ), $\text{K}_{\inf}$ is the minimum KL divergence to a distribution with mean at least $\mu$ (a measure of how far the empirical mean is from the target), and $\varepsilon = 1/2$ when the prior pseudo-count $\alpha_0$ is sufficiently large ( $\alpha_0 \geq c_0 + \log_{17/16}(n)$ for a constant $c_0$ defined in equation (5)).

Why the KL term matters: the quantity $\text{K}_{\inf}(\bar{\nu}_n, \mu)$ is the minimum amount of information (in bits) needed to "distort" the empirical distribution so that its mean reaches $\mu$ . If the empirical mean is already close to or above $\mu$ , this is small (the data already supports optimism); if the empirical mean is far below $\mu$ (the data suggests the state-action pair is bad), this is large (a lot of "wishful thinking" is needed). The event $E^\star(\delta)$ (Lemma 4 in Appendix D.2) guarantees that $n \cdot \text{K}_{\inf}(\bar{\nu}_n, p_h V^\star_{h+1}) \leq \beta^\star(\delta, n)$ with high probability — the empirical distribution is never "too far" from the true mean. Setting $\kappa = 2\beta^\star(\delta, T)$ ensures that the term inside the square root in the Gaussian tail is at most 1, so the probability that $S_j \geq \mu$ is at least $(1 - 1/2) \cdot (1 - \Phi(1))/2$ — a constant $\gamma$ that doesn't decay with the problem parameters. Then $J = \lceil \log(1/\delta') / \log(1/(1-\gamma)) \rceil$ independent copies suffice to make the maximum exceed $\mu$ with probability $1 - \delta'$ .

The ensemble size J is modest: because the "per-sample" success probability $\gamma$ is a constant (not decaying with T, S, A, or H), $J = \tilde{O}(1)$ — it grows only logarithmically with $SAHT$ . This is what makes the algorithm tractable: maintaining J = 5–20 copies suffices for typical problem sizes, keeping the computational overhead a small constant factor over standard Q-learning.

Connection to OPSRL: this ensemble-max approach is directly inspired by Optimistic PSRL (Agrawal and Jia, 2017; Tiapkin et al., 2022a), which takes the maximum over multiple posterior samples to create optimism. In RandQL, the ensemble of temporary Q-values serves the same role as multiple posterior MDP samples in OPSRL. The key difference is that RandQL's "posterior samples" are generated through randomized learning rates rather than explicit model sampling.

The Staged Framework: Staged-RandQL Algorithm

The staged version of RandQL (Algorithm 1, Section 3.2) organizes learning into epochs of exponentially growing length to simplify the theoretical analysis. Here is the complete specification.

Stage definition and counting: for a state-action pair $(s,a)$ at step $h$ , let $n^t_h(s,a)$ be the number of visits before episode $t$ . The stage index $k$ is the integer such that:

$n^t_h(s,a) \in \left[\sum_{i=0}^{k-1} e_i, \sum_{i=0}^{k} e_i\right)$

where $e_k = \lfloor (1 + 1/H)^k \cdot H \rfloor$ is the length of stage $k \geq 0$ , with $e_{-1} = 0$ by convention. The within-stage count is $\tilde{n}^t_h(s,a) = n^t_h(s,a) - \sum_{i=0}^{k-1} e_i$ — the number of visits since the current stage began.

What this means operationally: the first stage (k=0) collects $e_0 = H$ visits, the second stage (k=1) collects $e_1 = \lfloor (1 + 1/H) \cdot H \rfloor \approx H + 1$ more visits, the third stage $e_2 \approx H(1 + 2/H) = H + 2$ more, and so on. The stage lengths grow roughly linearly with $k$ at rate $e_k \approx H + k$ . This exponential-in-index growth means each stage is only slightly longer than the previous one, ensuring that later stages (when the estimates are more accurate) don't dominate the total visit budget — they receive proportionally fewer new stages.

The stage-based update cycle (within an episode t, step h):

Action selection: $a_h \in \arg\max_a Q_h(s_h, a)$ using the current policy Q-values.
Observation: receive $r_h(s_h, a_h)$ and $s_{h+1} \sim p_h(s_h, a_h)$ .
Learning rate sampling: for each $j \in [J]$ , sample $w_j \sim \text{Beta}(1/\kappa, (\tilde{n} + n_0)/\kappa)$ where $\tilde{n} = \tilde{n}_h(s_h, a_h)$ is the within-stage count.
Temporary Q-value update: for all $j \in [J]$ , $\tilde{Q}^j_h(s_h, a_h) := (1 - w_j) \tilde{Q}^j_h(s_h, a_h) + w_j [r_h(s_h, a_h) + V_{h+1}(s_{h+1})]$
Counter increment: $\tilde{n}_h(s_h, a_h) := \tilde{n}_h(s_h, a_h) + 1$
Stage boundary check: if $\tilde{n}_h(s_h, a_h) = e_q$ where $q$ is the current stage index, then:
- Policy Q-value update: $Q_h(s_h, a_h) := \max_{j \in [J]} \tilde{Q}^j_h(s_h, a_h)$ — freeze the optimistic estimate.
- Value function update: $V_h(s_h) := \max_{a \in A} Q_h(s_h, a)$ — reflected immediately for action selection at future steps.
- Temporary Q-value reset: for all $j$ , $\tilde{Q}^j_h(s_h, a_h) := r_h(s_h, a_h) + r_0(H - h - 1)$ — re-anchor to optimistic prior.
- Counter reset: $\tilde{n}_h(s_h, a_h) := 0$ , stage increment $q_h(s_h, a_h) := q_h(s_h, a_h) + 1$ .

The value function is computed on-the-fly: $V^t_h(s) = \max_{a \in A} Q^t_h(s,a)$ for tabular RandQL. This means when a policy Q-value is updated at a stage boundary for one state-action pair, the corresponding state's value is immediately recomputed, and this new value feeds into the targets for other state-action pairs at different steps — enabling value propagation across the MDP.

Why the stage approach simplifies the analysis while preserving exploration: within a stage of length $e_k$ , the temporary Q-values are built from exactly $e_k$ observations (plus the reset prior value). The weight distribution $(W^0, \ldots, W^{e_k}) \sim \text{Dir}(n_0/\kappa, 1/\kappa, \ldots, 1/\kappa)$ is exact — no prior decay to account for, no mixing coefficients to track. This decouples the concentration analysis from the sequential nature of the updates: each stage's estimate is a fresh Dirichlet-weighted average over the $e_k$ i.i.d. targets within that stage. The trade-off is that within-stage targets use the value functions available at the time of observation (which may be outdated), introducing the bias that Corollary 1 (Appendix D.4) bounds.

The bias decomposition (Corollary 1): on the favorable event $G'(\delta)$ , for any state-action pair in stage $k \geq 0$ with within-stage visits $\ell_1 < \cdots < \ell_{e_k}$ :

$0 \leq Q^t_h(s,a) - Q^\star_h(s,a) \leq \frac{1}{e_k} \sum_{i=1}^{e_k} [V^{\ell_i}_{h+1}(s_{\ell_i}) - V^\star_{h+1}(s_{\ell_i})] + B^t_h(k)$

where $B^t_h(k) = 61 e^2 r_0 H \frac{\beta_{\max}(\delta)}{\sqrt{e_k}} + 1201 e r_0 H \frac{(\beta_{\max}(\delta))^4}{e_k}$ is a bonus-like term (arising from the concentration of the Dirichlet weights and the empirical mean), $\beta_{\max}(\delta) = O(\log(SATH/\delta))$ , and $r_0 = 2$ .

What this says: the over-estimation $Q^t_h - Q^\star_h$ decomposes into two parts. The first is the average Bellman error — the average over-estimation in the value function at the next step, averaged over the $e_k$ visits within the stage. This propagates optimism from later steps backward. The second is a concentration error that decays as $O(1/\sqrt{e_k} + 1/e_k)$ — the statistical noise from having only $e_k$ samples to estimate the expected value, plus the variance from the randomized weights. The key difference from OptQL is that this bonus-like term arises automatically from the concentration analysis of the randomized weights, not from an explicitly added bonus hyperparameter.

The Metric Space Extension: Net-Staged-RandQL

When the state and action spaces are continuous (satisfying Assumptions 1–3 in Section 4.1), RandQL cannot maintain a table of Q-values for every state-action pair. Instead, Net-Staged-RandQL (Algorithm 4, Appendix E.2) operates on a fixed discretization of the joint space $S \times A$ .

Discretization setup: a minimal $\varepsilon$ -cover $\mathcal{N}_\varepsilon$ of $S \times A$ is a set of open balls of radius $\varepsilon$ whose union covers the entire space. The covering number $N_\varepsilon = |\mathcal{N}_\varepsilon|$ is the size of a minimal such cover. Under the covering dimension assumption ( $N_\varepsilon \leq C_N \varepsilon^{-d_c}$ for all $\varepsilon > 0$ ), the discretization size grows polynomially with $1/\varepsilon$ . A quantization map $\psi_\varepsilon : S \times A \to \mathcal{N}_\varepsilon$ assigns each point to a ball containing it (ties broken arbitrarily).

What changes from tabular to metric: instead of maintaining Q-values for each $(s,a,h)$ , Net-Staged-RandQL maintains them for each $(B, h)$ where $B \in \mathcal{N}_\varepsilon$ . When the agent visits $(s^t_h, a^t_h)$ , it updates the Q-values for the ball $B^t_h = \psi_\varepsilon(s^t_h, a^t_h)$ that contains the visited pair. The value function is computed on-the-fly: $V^t_h(s) = \max_{a \in A} Q^t_h(\psi_\varepsilon(s, a))$ — the value at state $s$ is the maximum Q-value over all balls that could contain $(s,a)$ for some action $a$ . The policy is $\pi^t_h(s) \in \arg\max_{a \in A} Q^t_h(\psi_\varepsilon(s, a))$ .

The crucial change — stage-dependent prior counts: in tabular RandQL, the prior pseudo-count $n_0$ is a fixed constant (dependent only on $\kappa$ and logarithmic terms). In metric RandQL, $n_0$ must depend on the stage index $k$ to account for the approximation error from discretization. Specifically (Proposition 4, Appendix E.4):

$n_0(k) = \left\lceil \tilde{n}_0 + \kappa + \frac{\varepsilon L}{H - 1} \cdot (e_k + \tilde{n}_0 + \kappa) \right\rceil$

where $\tilde{n}_0 = (c_0 + 1 + \log_{17/16}(T)) \cdot \kappa$ is a base prior count (same form as tabular), $L = L_r + (1 + L_F) L_V$ combines the Lipschitz constants of the reward ( $L_r$ ), the reparametrization function ( $L_F$ ), and the optimal value function ( $L_V$ ), and $e_k$ is the stage length.

Why the prior count grows with k: in the tabular case, the prior's role is to provide an optimistic anchor for exploration. In the metric case, the prior must also absorb the discretization bias. When we group all state-action pairs in a ball $B$ together, we incur an approximation error of up to $L \cdot \text{diam}(B) = L \cdot 2\varepsilon$ — the Q-value of one pair in the ball can differ from another by this much, but they share the same estimate. To maintain optimism (the Q-estimate must upper-bound the true Q-value for every point in the ball), the prior needs to be inflated to cover this gap. Since the stage length $e_k$ grows with $k$ , and the weight of the prior in the Dirichlet average is $n_0(k)/(e_k + n_0(k))$ , the prior must also grow proportionally to $e_k$ to maintain constant influence. The term $\frac{\varepsilon L}{H-1} \cdot e_k$ in $n_0(k)$ ensures that the prior's contribution to the optimistic estimate exceeds the worst-case discretization error $L\varepsilon$ for any point in the ball.

The optimism argument in metric spaces (Proposition 4): the proof splits the analysis into two parts. The approximation error is handled by the inflated prior: with $n_0(k)$ chosen as above, the weight on the prior atom $r_0(H-1)$ in the Dirichlet average is large enough that even in the worst case (the prior atom gets a "bad" low weight), the contribution $W^0 \cdot r_0(H-1)$ still exceeds $p_h V^\star_{h+1}(s,a) + L\varepsilon$ with probability at least 1/2, for the representative center of the ball. The stochastic error (the randomness from the Dirichlet weights applied to the i.i.d. next-state samples, represented via Assumption 2 as $s_{h+1} = F_h(s,a,\xi_h)$ for independent $\xi_h$ ) is handled identically to the tabular case via Theorem 5's anti-concentration inequality, applied to the center of the ball $(s,a) = \text{center}(B)$ .

Consequence for regret (Corollary 2, Appendix E.5): the upper bound on over-estimation becomes:

$Q^t_h(B) - Q^\star_h(s,a) \leq \frac{1}{e_k} \sum_{i=1}^{e_k} [V^{\ell_i}_{h+1} - V^\star_{h+1}](s_{\ell_i}) + B^t_h(k) + 3L\varepsilon$

where the additional $3L\varepsilon$ term accounts for: (i) reward function approximation across the ball radius $\varepsilon$ , (ii) value function approximation across the ball radius (the $L_V \varepsilon$ from Lipschitz), and (iii) transition kernel approximation via the reparametrization Lipschitz constant $L_F$ (since next states from different points in the same ball can differ by up to $L_F \varepsilon$ on average). Setting $\varepsilon = T^{-1/(d_c+2)}$ balances the $O(T\varepsilon)$ approximation term against the $O(T^{1/2} \varepsilon^{-d_c/2})$ estimation term, yielding the $\tilde{O}(T^{(d_c+1)/(d_c+2)})$ regret rate.

The Adaptive Extension: Adaptive-Staged-RandQL

The adaptive version (Algorithm 6, Appendix F) replaces the fixed $\varepsilon$ -net with a hierarchical partition tree that is refined on-the-fly, following the framework of Sinclair et al. [2019, 2023]. The key difference is that instead of pre-committing to a uniform discretization level, the algorithm starts coarse and selectively refines regions that appear promising.

Partition structure: the algorithm maintains an adaptive partition $\mathcal{P}^t_h$ of $S \times A$ for each step $h$ , initialized to the trivial partition $\{\mathcal{P}_0\} = \{S \times A\}$ (the whole space as a single ball). Each region $B \in \mathcal{P}^t_h$ is of the form $S(B) \times A(B)$ (a product of state and action subsets) with a specified center and diameter $\text{diam}(B) \leq d_{\max} \cdot 2^{-d(B)}$ where $d(B)$ is the depth in the tree (0 for the root). Regions form a tree: each region has a unique parent at the previous depth, and a region is "active" if it is a leaf in the current partition.

Selection rule: for the current state $s^t_h$ , the set of relevant balls is $\mathcal{R}^t_h(s^t_h) = \{ \text{active } B \in \mathcal{P}^t_h \mid (s^t_h, a) \in B \text{ for some } a \in A \}$ — all active leaf balls that could contain a state-action pair with this state. The chosen ball is $B^t_h = \arg\max_{B \in \mathcal{R}^t_h(s^t_h)} Q^t_h(B)$ , and the action is taken from the center of this ball: $(s^t_h, a^t_h) = \text{center}(B^t_h)$ .

Splitting rule: a ball $B$ is split when $\sqrt{d^2_{\max} / n^t_h(B)} \leq \text{diam}(B)$ , where $n^t_h(B)$ counts visits to $B$ and all its ancestors in the tree. When this inequality triggers, the ball $B$ is replaced in $\mathcal{P}^{t+1}_h$ by its children in the hierarchical partition tree (the next level of dyadic refinement), and the counters and Q-values for the children are initialized from the parent's values. The splitting rule ensures that the discretization error $O(\text{diam}(B))$ and the statistical error $O(1/\sqrt{n})$ remain balanced — a ball is refined when we have enough data to benefit from the higher resolution.

The zooming dimension and instance-dependent regret: under the adaptive scheme, the algorithm concentrates its samples on the near-optimal set $Z^\varepsilon_h = \{(s,a) : V^\star_h(s) - Q^\star_h(s,a) \leq (H+1)\varepsilon\}$ — the state-action pairs with small sub-optimality gap. The zooming dimension $d_{z,h}$ (Definition 4) measures the covering dimension of this near-optimal set: $N_\varepsilon(Z^{\rho \cdot \varepsilon}_h) \leq C_{N,h} \varepsilon^{-d_{z,h}}$ . For many MDPs, $d_{z,h}$ is much smaller than the covering dimension $d_c$ of the full space (e.g., if the optimal policy only depends on a low-dimensional manifold of the state). The adaptive algorithm achieves regret $\tilde{O}(H^{3/2} \sum_{h=1}^H T^{(d_{z,h}+1)/(d_{z,h}+2)})$ , automatically adapting to this lower intrinsic dimension without knowing it in advance.

The prior count in adaptive RandQL: the stage-dependent prior is modified to account for the ball's diameter rather than a fixed $\varepsilon$ :

$n_0(k) = \left\lceil \tilde{n}_0 + \kappa + L \cdot \frac{d_{\max}}{H-1} \cdot \frac{e_k + \tilde{n}_0 + \kappa}{\sqrt{H e_k - k - H^2}} \right\rceil$

where the denominator reflects an upper bound on the diameter of the current ball in terms of the stage: for any ball $B$ in stage $k$ , its diameter satisfies $\text{diam}(B) \leq d_{\max} / \sqrt{H e_k - k - H^2}$ (from the splitting rule and stage length definition). This is analogous to the $L\varepsilon$ term in Net-Staged-RandQL, but now $\varepsilon$ varies per ball and shrinks as the stage advances — deeper stages correspond to smaller balls (due to accumulated splits), so the required prior inflation decreases over time for balls that are refined.

Clipping operator for sharp analysis: the proof of Theorem 3 (Appendix F.3) introduces a clipping operator $\text{clip}(\mu \mid \nu) = \mu \cdot \mathbf{1}\{\mu \leq \nu\}$ that zeros out a quantity if it exceeds a threshold $\nu$ . Applied to the over-estimation bound, this means: if the "bonus-like" term $B^t_h$ exceeds the sub-optimality gap $\text{gap}_h(B^t_h) / (H+1)$ , the algorithm doesn't actually need to worry about that excess — the state-action pair is already known to be sub-optimal, so further over-estimation doesn't affect regret. This "clipping" is a standard technique from instance-dependent analysis (Simchowitz and Jamieson, 2019; Cao and Krishnamurthy, 2020) that tightens the regret bound by preventing the worst-case $O(1/\sqrt{n})$ concentration terms from being double-counted across stages — they only matter when the gap is large enough that the optimism could cause a sub-optimal action to be chosen.

Summary of Design Choices and Their Justifications

Beta-distributed learning rates over deterministic: Beta randomness induces Dirichlet-distributed aggregate weights, replicating PSRL's posterior sampling without requiring transition model maintenance. The alternative (fixed learning rates) provides no exploration; bonuses (OptQL) require parameter tuning.
Aggressive Beta parameters (Beta(H, n) in RandQL, Beta(1/κ, (n+n₀)/κ) in Staged-RandQL) over Beta(1, ·): the $H$ (or $1/\kappa$ with $\kappa$ tuned) in the first parameter ensures the learning rate is large enough that recent observations dominate quickly, reducing the temporal bias from using outdated value functions. Beta(1, ·) would give $\mathbb{E}[w] = 1/(1 + n + n_0)$ — too slow to adapt. The choice $\kappa = 2\beta^\star(\delta, T)$ (twice the KL divergence bound) is the minimal value that guarantees the anti-concentration probability is a constant — smaller $\kappa$ would make the Dirichlet too concentrated (over-confident), while larger $\kappa$ would make it too diffuse (too random to be useful).
Ensemble size $J = \tilde{O}(\log(SAHT/\delta))$ : logarithmic in all parameters, making the computational overhead negligible. The constant $c_J = 1/\log(2/(1+\Phi(1))) \approx 5.3$ (or $\tilde{c}_J = 1/\log(4/(3+\Phi(1))) \approx 6.2$ in the metric case) is derived from the anti-concentration probability $\gamma = (1-\Phi(1))/4$ (or similar), which is approximately 0.08–0.10.
Staged structure over continuous updates for analysis: decouples stages so that each estimate uses only fresh within-stage data, avoiding the intricate drifting-prior analysis of non-staged RandQL. The stage growth rate $(1 + 1/H)^k$ ensures that later stages (with more accurate estimates) don't consume a disproportionate share of the visit budget.
Stage-dependent prior counts in metric spaces: $n_0(k)$ grows with $e_k$ to maintain optimism despite discretization error $O(\varepsilon)$ . Without this scaling, the prior's influence would become negligible relative to the approximation bias, and the algorithm could become pessimistic for state-action pairs near ball boundaries.
Clipping in the adaptive analysis: prevents the stage-wise concentration error from being charged multiple times in the regret, tightening the bound from covering-dimension to zooming-dimension dependence. This is a standard but crucial refinement.

4. Key Insights and Innovations

Innovation 1: Learning Rate Randomization as a Transport Mechanism from Model-Based to Model-Free Exploration

The paper's most fundamental contribution is not a new algorithm per se, but rather the recognition that the exploration behavior of posterior sampling can be transported intact into a model-free setting through a simple distributional equivalence: randomized learning rates in Q-learning produce aggregate weight vectors that are Dirichlet-distributed, exactly matching the weight distribution that PSRL induces over historical observations. This is not an approximation or a heuristic — Lemma 3 in Appendix D.1 proves the equivalence is exact.

Prior to this work, the field treated model-based posterior sampling (PSRL, RLSVI) and model-free optimistic exploration (OptQL, bonuses) as fundamentally different categories of algorithms that happen to both achieve exploration, but through unrelated mechanisms. PSRL maintains explicit Bayesian posteriors over transition probabilities and samples from them; OptQL adds deterministic bonuses to Q-values based on visit counts. These were seen as alternative design philosophies, not as different implementations of a shared statistical operation.

The paper's distributional insight reframes this: posterior sampling over an MDP model is equivalent to posterior sampling over the weights in a convex combination of historical targets. Once this equivalence is recognized, the model-free implementation follows naturally — since Q-learning already maintains a weighted average over historical targets (when you unfold the recursion), making the learning rates random with the right Beta distribution suffices to replicate the posterior sampling operation. The "model" was never essential to begin with; it was just one way to parameterize the posterior.

What makes this a fundamental shift rather than incremental is that it establishes model-free posterior sampling as a first-class primitive, not a second-order approximation of the model-based version. The proof in Proposition 1 (Section D.3) shows that the anti-concentration properties of Dirichlet-weighted averages — the mathematical engine that makes PSRL explore effectively — carry over identically to the randomized learning rate construction. The probability that the maximum over J ensemble members exceeds the true expected value is lower-bounded by exactly the same expression that governs PSRL's optimism.

The significance extends beyond the specific algorithm. By identifying learning rate randomization as the core mechanism, the paper opens an entire design space: any Bayesian model-free algorithm that can be expressed as a weighted combination of observations can potentially be realized through appropriately chosen random learning rate distributions. The staged variant (Staged-RandQL) demonstrates that the distributional equivalence can be leveraged both in continuous-update form (RandQL, with prior re-injection) and in episodic-reset form (Staged-RandQL, with stage boundaries), providing flexibility in how the posterior sampling behavior is integrated into the Q-learning framework.

The "lazy approximation" — using stale value functions $V^{\ell_i}$ rather than recomputing all historical targets — is the one place where RandQL diverges from exact posterior sampling, and it's crucial that the paper identifies this as the source of bias and addresses it through aggressive learning rates (Beta(H, n) rather than Beta(1, n)) and the staged framework. This is not a bug but a feature: it shows precisely where model-free and model-based posterior sampling differ, and provides a concrete technical handle on that difference.

Empirically, the equivalence is validated by the comparison between RandQL and Sampled-RandQL in Figure 2 (Appendix I): both variants (optimistic ensemble-max and random ensemble-sample) show similar regret, mirroring the OPSRL-vs-PSRL relationship in the model-based literature, suggesting the ensemble truly functions as a posterior over Q-values from which one can either sample or take the maximum.

Innovation 2: Identifying the Prior Forgetting Rate as the Critical Tuning Parameter

A second conceptual contribution is the paper's diagnosis that the rate at which the prior's influence decays is the key determinant of exploration quality in randomized Q-learning, and that this rate must be actively managed rather than passively accepted.

In standard Q-learning (deterministic learning rates), the weight on the initial Q-value decays as $\prod (1 - \alpha_i)$ , which for typical learning rate schedules goes to zero. This is by design — you want to forget the (usually uninformative) initialization. But in RandQL, the initialization is not uninformative: it's an optimistic pseudo-value $r_0(H - h - 1)$ that encodes the belief "this unknown state-action pair might lead to high reward." Forgetting the prior too quickly extinguishes the exploratory drive.

The paper surfaces and quantifies this problem. With Beta(H, n) learning rates (the non-staged RandQL), the expected weight on the prior after n visits is:

$\mathbb{E}[W^0_n] = \prod_{i=1}^n \left(1 - \frac{H}{H + i + n_0}\right) \sim n^{-H}$

The prior vanishes polynomially (with exponent H) in n — this is intuitive: for H = 50 (a typical horizon), after 100 visits, the prior weight is roughly $100^{-50}$ , effectively zero. The prior provides essentially no exploration after the first few dozen visits per state-action pair. This is fine for later episodes when data is abundant, but problematic for the critical early-to-middle phase of learning where underexplored state-action pairs still need optimistic pulls.

The paper provides two distinct solutions to this problem, each with different tradeoffs:

RandQL's prior re-injection (Algorithm 2) mixes the prior into every update via a secondary Beta random variable $\mathring{w} \sim \text{Beta}(n, n_0)$ , restoring the effective prior weight to roughly $n_0/(n + n_0)$ — the standard Bayesian rate. This is elegant but analytically messy, as the interplay between the two Beta variables creates complex dependence structure.
Staged-RandQL's prior reset (Algorithm 1) simply resets the temporary Q-values to the prior at every stage boundary. This is coarser — the prior is "reloaded" discretely at exponentially-spaced intervals rather than continuously maintained — but makes the analysis clean: each stage is a self-contained Dirichlet-weighted average with a fresh prior anchor.

What's conceptually important is not which solution is used, but the paper's reframing of the problem: the prior's survival time in the estimate is a tunable parameter that controls the exploration horizon, analogous to the discount factor in value iteration or the prior strength in Bayesian updating. The paper shows that you need the prior to persist at order $n_0/(n + n_0)$ strength — neither decaying too fast (loses exploration) nor too slow (loses adaptivity) — and that both continuous re-injection and episodic reset can achieve this. This framing explains why the Q-learning literature had struggled with model-free posterior sampling: the naive approach (randomize learning rates with Beta(1, n)) gives prior weight decaying as ~1/n, which is too fast and produces sub-optimal exploration, as the paper notes in Section 3.1 ("this algorithm is equivalent to OptQL with the uniform step-sizes which are known to be sub-optimal").

The empirical consequence is visible in Figure 2 (Appendix I): Staged-RandQL converges more slowly than RandQL, confirming that the staged reset, while theoretically cleaner, introduces artificial delay in prior re-injection. This tradeoff between analytical tractability and empirical efficiency is a recurring theme in RL theory (cf. UCBVI vs. Greedy-UCBVI), and the paper's explicit characterization of it is a useful contribution.

Innovation 3: The Covering-to-Zooming Dimension Transition Through Stage-Dependent Priors

The metric space extension of RandQL introduces a technical innovation that has conceptual importance beyond the specific algorithm: the use of stage-dependent prior counts to simultaneously maintain optimism and absorb discretization error.

Prior work on model-free RL in metric spaces (Net-QL by Song and Sun, 2019; Adaptive-QL by Sinclair et al., 2019) handled discretization by adding explicit bonus terms proportional to the ball diameter. In Net-QL, the Q-value update includes a $+ L\varepsilon$ bonus term where L is a Lipschitz constant and $\varepsilon$ is the discretization radius. This is conceptually straightforward — you inflate values to cover the worst-case error within a ball — but requires the algorithm to know and explicitly add the right bonus magnitude.

RandQL eliminates explicit bonuses, so the question becomes: can the same "cover-the-approximation-gap" effect be achieved through the prior alone? The answer, as developed in Proposition 4 (Appendix E.4), is yes — but it requires the prior count $n_0(k)$ to grow with the stage index $k$ , specifically:

$n_0(k) \approx \tilde{n}_0 + \kappa + \frac{\varepsilon L}{H-1} \cdot e_k$

where $e_k = \lfloor (1 + 1/H)^k H \rfloor$ is the stage length. The intuition is subtle: in the Dirichlet-weighted average of the Q-estimate, the prior contributes weight $W^0 \sim \text{Beta}(n_0(k)/\kappa, \cdot)$ . For the prior's contribution $W^0 \cdot r_0(H-1)$ to exceed the true mean $p_h V^\star_{h+1}$ plus the worst-case Lipschitz error $L\varepsilon$ , the prior atom needs enough weight in the distribution. Since the total weight is distributed across $e_k + n_0(k)/\kappa$ atoms (one prior plus $e_k$ observations), the prior's expected weight is $n_0(k) / (e_k + n_0(k))$ . To maintain a constant fraction of the total weight as $e_k$ grows, $n_0(k)$ must grow proportionally to $e_k$ . The proportionality constant $\varepsilon L/(H-1)$ is exactly what's needed for the prior's optimistic push to overcome the $L\varepsilon$ gap.

What makes this conceptual rather than merely technical is that it reveals a tight coupling between the prior (as an exploration device) and the discretization (as a function approximation device) that is unique to randomized exploration. In bonus-based methods, exploration and approximation are handled by separate additive terms in the Q-value update — the bonus handles exploration (visits), the Lipschitz term handles approximation (diameter). They're independent and additive. In RandQL, the prior serves both purposes simultaneously, and the scaling $n_0(k) \propto e_k$ is the mathematical expression of this dual role.

This coupling has implications for the adaptive variant: as balls are split and their diameters shrink (later stages for a given ball correspond to smaller diameter due to the splitting rule), the required prior inflation decreases. This produces a natural "focusing" effect — the algorithm maintains strong optimism for coarse balls early on, and as it refines promising regions, it reduces the prior influence, letting the data dominate. The transition from covering-dimension to zooming-dimension regret bounds (Theorems 2 and 3) is a direct consequence of this adaptive prior scaling.

The fact that this coupling emerges automatically from the Dirichlet weight construction, without any explicit "if diameter is X, add bonus Y" logic, suggests that randomized exploration may be more naturally suited to function approximation settings than bonus-based exploration — the prior provides a unified mechanism that adapts its strength to the current resolution level without requiring separate bonus schedules.

Innovation 4: Verifier-Free Optimism Through Ensemble Anti-Concentration

This paper introduces a proof technique whose conceptual implications extend beyond RandQL: the use of anti-concentration inequalities for Dirichlet-weighted sums to establish optimism without constructing explicit confidence bounds.

The standard approach to proving optimism in RL algorithms (UCBVI, OptQL, etc.) follows a template: construct a confidence interval around the estimated value (typically using Hoeffding, Bernstein, or empirical Bernstein inequalities), then show that adding the confidence radius as a bonus ensures the estimate upper-bounds the true value with high probability. The bonus magnitude is explicit, interpretable, and directly tied to the statistical uncertainty.

RandQL's proof (Proposition 1, Section D.3) takes a fundamentally different route. Instead of constructing a confidence interval, it lower-bounds the probability that a single Dirichlet-weighted sum exceeds the true mean, using an anti-concentration inequality (Theorem 5, originally from Tiapkin et al., 2022a):

$P(S_j \geq \mu) \geq (1 - \varepsilon) \cdot \left(1 - \Phi\left(\sqrt{2\alpha \cdot \text{K}_{\inf}(\bar{\nu}, \mu)}\right)\right)$

where $\text{K}_{\inf}(\bar{\nu}, \mu)$ is the minimum KL divergence to a distribution with mean exceeding $\mu$ . This is not a concentration inequality (which bounds how far the estimate is from the truth) but an anti-concentration inequality (which bounds how likely the estimate is to be above the truth). The KL divergence $\text{K}_{\inf}$ plays the role that variance or subgaussian parameter plays in concentration bounds — it measures "how far" the empirical distribution is from the target mean in an information-theoretic sense.

The conceptual shift is subtle but important: concentration inequalities say "with high probability, the estimate won't be too far off"; anti-concentration inequalities say "with controlled probability, the estimate will be optimistic." The former are symmetric (deviation above and below the mean are treated similarly); the latter are asymmetric and specifically tailored to the exploration problem, where only upward deviation matters (downward deviation doesn't hurt exploration, it just makes the agent temporarily pessimistic).

The KL-based formulation has the advantage of being distribution-aware: it naturally tightens when the empirical distribution of observed values is concentrated near the mean (the KL divergence is small, so the anti-concentration probability is large), and loosens when the empirical distribution is diffuse or far from the target (KL divergence large, probability small). This is more nuanced than variance-based bounds, which treat all distributions with the same variance identically regardless of shape.

The ensemble size $J = O(\log(SAHT/\delta))$ emerges from this anti-concentration analysis: with a constant per-sample optimism probability $\gamma$ , $J \approx \log(1/\delta) / \log(1/(1-\gamma))$ suffices to make the maximum optimistic with probability $1 - \delta$ . This is simpler and tighter than the union-bound-over-confidence-intervals arguments typically used for bonus-based methods, where the bonus magnitude must grow logarithmically with the number of state-action pairs.

The practical implication is that RandQL's exploration intensity self-calibrates through the Dirichlet variance, without requiring the algorithm designer to specify bonus coefficients. This is visible in the experiments (Appendix I): the authors use "simplified bonuses" of the form $\min(\sqrt{1/n} + (H-h+1)/n, H-h+1)$ for OptQL (equation 26), explicitly noting that "this bonus does not necessarily result in a true upper-confidence bound." In contrast, RandQL's exploration emerges from the Beta distribution shape $\text{Beta}(1/\kappa, (n+n_0)/\kappa)$ with $\kappa$ set to $2\beta^\star(\delta, T)$ — a single parameter that depends only on the horizon and confidence level, not on the bonus tuning heuristics needed for OptQL.

The gap between these approaches is evident in Figure 1 (Section 5): RandQL significantly outperforms OptQL on the grid-world environment despite (or because of) not using explicit bonuses. This suggests that the anti-concentration approach to optimism — relying on the natural variability of Dirichlet-weighted averages rather than constructed bonus terms — may be not just theoretically elegant but practically more robust.

5. Experimental Analysis

Evaluation Methodology

Dataset. The tabular experiments use a custom grid-world environment with 100 states (10 × 10 grid) and 4 actions (left, right, up, down), with horizon H = 50 and transition noise ε = 0.2. A second tabular environment is Osband et al.'s [2016] chain of length L = 15 with 2 actions, H = 30, and transition noise 0.1. The non-tabular experiments use a 2D continuous ball environment (state space: unit Euclidean ball in R², 5 discrete actions) with three difficulty levels varying reward sparsity (dense: c = 0.71; sparse: c = 0.2) and transition noise (σ = 0.01 or 0.025). No standard benchmark dataset is used — all environments are custom-constructed for this paper.
Base model(s). RandQL is a tabula rasa algorithm — there is no pretrained model. The algorithm initializes Q-values to optimistic prior values r_h(s,a) + r_0(H - h) (tabular) or r_0 H (metric) with pseudo-reward r_0 = 2, representing the maximum conceivable value. All learning occurs online through interaction with the environment.
Metrics. The primary metric is regret R_T = Σ_{t=1}^T [V^⋆_1(s_1) - V^{π^t}_1(s_1)], the cumulative difference between the optimal expected return and the agent's actual expected return (lower is better). For the continuous environments (Figure 4), cumulative reward (higher is better) is reported rather than regret. All curves show averages over 4 random seeds with error bars.
Baselines. For tabular experiments (Figure 1, Figure 3): OptQL [Jin et al., 2018] — model-free optimistic Q-learning with bonuses; UCBVI [Azar et al., 2017] — model-based optimistic value iteration with full backward induction; Greedy-UCBVI [Efroni et al., 2019] — a computationally cheaper variant of UCBVI using real-time dynamic programming; PSRL [Osband et al., 2013] — model-based posterior sampling with Dirichlet priors on transitions; and RLSVI [Russo, 2019] — model-based randomized value iteration with Gaussian noise. For metric experiments (Figure 4): Adaptive-QL [Sinclair et al., 2019, 2023] — adaptive-discretization extension of OptQL; Kernel-UCBVI [Domingues et al., 2021c] — kernel-based extension of UCBVI with 300 representative states and Gaussian kernel (bandwidth 0.025); DQN [Mnih et al., 2013] — 2-layer MLP with 64 hidden units and ε-greedy exploration (ε annealed from 1.0 to 0.1 over 10,000 steps); and BootDQN [Osband and Van Roy, 2015] — ensemble of 10 Q-networks with no ε-greedy.
Generation budget / compute accounting. For tabular experiments, all algorithms operate under identical interaction budgets of T = 30,000 episodes (grid-world) or T = 10,000 episodes (chain) with H steps per episode. For continuous experiments, T = 20,000 episodes with H = 30. There is no separate "generation budget" concept — the budget is the number of episodes, and all algorithms observe the same number of transitions per episode. Computational complexity is reported in Table 2: RandQL achieves Õ(H) per-episode time and Õ(HSA) space, compared to Õ(HS²A) for UCBVI and PSRL. For continuous environments, Table 3 reports average wall-clock time per episode: Adaptive-RandQL (5.78 × 10⁻² seconds) is faster than Kernel-UCBVI (1.52 × 10⁻¹ seconds) and competitive with Adaptive-QL (4.21 × 10⁻² seconds).
Cross-validation / statistical protocol. No cross-validation is used. All experiments report averages over 4 random seeds with error bars (visible in Figures 1, 3, 4). The hyperparameters for RandQL are set according to the theoretical prescriptions (Section 3.2, Appendix I): ensemble size J = 10 for tabular (J = ⌈c_J · log(2SAHT/δ)⌉ ≈ 5.3 · log(2·100·4·50·30000/0.05) ≈ 48 would be required by theory, so the experiments use a much smaller J = 10), posterior inflation κ = 1.0 for tabular (κ = 10 for metric), and prior pseudo-count n₀ = 1/S for tabular (n₀ = 0.33 for metric). The bonus-based baselines (UCBVI, OptQL, Adaptive-QL) use simplified Hoeffding bonuses (equation 26 in Appendix I): min(√(1/n_t^h(s,a)) + (H-h+1)/n_t^h(s,a), H-h+1), which the authors acknowledge "does not necessarily result in a true upper-confidence bound" — this is an important caveat: the theoretical baseline is stronger than what was actually run.

Main Quantitative Results

Tabular Grid-World Experiment (Figure 1 and Figure 3)

The headline result is that RandQL outperforms OptQL — the model-free bonus-based baseline that it most directly replaces — while maintaining competitive performance with model-based Bayesian methods.

Figure 1 (Section 5) and Figure 3 (left, Appendix I) show regret curves for the grid-world environment (100 states, 4 actions, H = 50, noise 0.2) over 30,000 episodes. The key quantitative observations:

RandQL vs. OptQL: RandQL's regret curve lies consistently below OptQL's throughout training. At episode ~15,000, RandQL's cumulative regret is approximately 250,000–300,000, while OptQL's is approximately 400,000–450,000 — roughly a 1.5–1.8× reduction in regret. The gap widens in the later episodes (after 20,000), where OptQL's regret continues to grow while RandQL's appears to slow down, suggesting better asymptotic performance.
RandQL vs. model-based methods: UCBVI and Greedy-UCBVI dominate all model-free methods — UCBVI reaches roughly 100,000–150,000 cumulative regret at episode 30,000, about 2–3× lower than RandQL. This is expected and acknowledged by the authors (Appendix I): "using a model and backward induction allows new information to be more quickly propagated. For example, UCBVI needs only one episode to propagate information about the last step h = H to the first step h = 1, whereas OptQL or RandQL need at least H episodes." The model-based advantage is the cost of model-freeness, not a failure of RandQL specifically.
RandQL vs. PSRL and RLSVI: RandQL's regret is close to PSRL and RLSVI, particularly in the early-to-middle episodes (~5,000–20,000), where all three randomized methods show similar slopes. RLSVI slightly outperforms RandQL in the later episodes (by roughly 50,000–100,000 cumulative regret at episode 30,000), while PSRL and RandQL are nearly indistinguishable for much of the training. This empirically validates the paper's central claim: RandQL achieves exploration behavior similar to model-based posterior sampling despite being model-free.
RandQL variant comparison (Figure 2, Appendix I): Among the three RandQL variants, Sampled-RandQL performs best (lowest regret), followed by RandQL, with Staged-RandQL trailing significantly. At episode 30,000, Sampled-RandQL reaches approximately 300,000 cumulative regret, RandQL approximately 450,000, and Staged-RandQL approximately 700,000–800,000. The authors note that "even with the aggressive stage schedule, Staged-RandQL needs more episodes to converge" and that "despite simplifying the analysis, it artificially slows down the learning in practice." This is a significant qualification: the staged version with theoretical guarantees (Staged-RandQL) is not the version that performs well empirically; the non-staged RandQL with prior re-injection is.

Tabular Chain Experiment (Figure 3, Right)

The chain environment (L = 15, H = 30, noise 0.1) tests exploration in a setting where the agent must traverse a long chain to reach the high-reward state — a classic "deep exploration" challenge. Figure 3 (right) shows cumulative regret over 10,000 episodes:

RandQL vs. OptQL: RandQL's cumulative regret at episode 10,000 is approximately 5,000–7,500, while OptQL's is approximately 12,500–15,000 — roughly a 2× reduction. The gap appears early (by episode 2,000) and persists, suggesting RandQL's randomized exploration discovers the chain's structure faster than OptQL's bonus-based exploration.
RandQL vs. model-based methods: UCBVI and PSRL achieve near-zero regret after the initial exploration phase (regret flattens around episode 2,000–3,000 at roughly 2,500), while RandQL's regret continues to increase — by episode 10,000, model-based methods have 2,500–3,000 cumulative regret versus 5,000–7,500 for RandQL (roughly 2–3× higher). RLSVI falls between RandQL and UCBVI, reaching approximately 5,000.
Interpretation: The chain environment penalizes model-free methods more heavily than the grid-world because value propagation through the chain requires H sequential updates in Q-learning, amplifying the model-free disadvantage. The fact that RandQL still substantially outperforms OptQL in this challenging setting supports the claim that randomized exploration provides genuine benefits beyond what bonuses achieve.

Continuous Ball Environment (Figure 4, Appendix I)

Figure 4 shows cumulative reward (higher is better) for three difficulty levels of the 2D continuous ball environment over 20,000 episodes:

Level 1 (dense reward, small noise: c = 0.71, σ = 0.01):

Adaptive-RandQL and Adaptive-QL are nearly indistinguishable — both reach approximately 250,000–300,000 cumulative reward by episode 20,000. Kernel-UCBVI dominates all, reaching approximately 400,000.
DQN plateaus around 150,000–200,000; BootDQN performs worst at roughly 100,000–150,000.
This is the easiest setting — the dense reward means the agent receives non-zero feedback from many states, reducing the exploration challenge. The similarity of Adaptive-RandQL and Adaptive-QL here suggests that when exploration is easy, the specific exploration mechanism (randomized vs. bonus-based) matters less.

Level 2 (sparse reward, small noise: c = 0.2, σ = 0.01):

Adaptive-RandQL clearly outperforms Adaptive-QL. By episode 10,000, Adaptive-RandQL reaches approximately 60,000–80,000 cumulative reward while Adaptive-QL is at roughly 30,000–40,000 — about a 2× advantage. By episode 20,000, the gap narrows slightly but Adaptive-RandQL maintains the lead (roughly 100,000 vs. 80,000).
Kernel-UCBVI again dominates, reaching approximately 120,000–140,000.
BootDQN improves relative to Level 1, reaching approximately 60,000–80,000 at episode 20,000 — competitive with Adaptive-RandQL. DQN remains around 30,000–40,000.
This is the key result: when exploration becomes challenging (sparse rewards), the randomized exploration of RandQL provides a measurable advantage over bonus-based exploration in the model-free setting. The gap between Adaptive-RandQL and Adaptive-QL is the strongest empirical evidence for the paper's claim that learning rate randomization improves exploration.

Level 3 (sparse reward, large noise: c = 0.2, σ = 0.025):

The trends from Level 2 are amplified. Adaptive-RandQL reaches approximately 60,000–80,000 cumulative reward at episode 20,000, while Adaptive-QL plateaus around 30,000–50,000.
Kernel-UCBVI's advantage shrinks (roughly 100,000–120,000) — higher noise makes model-learning harder even for model-based methods.
BootDQN and Adaptive-RandQL show similar performance (both around 60,000–80,000), while DQN trails badly (roughly 20,000–30,000).
The model-free vs. model-based gap narrows under high noise, which is expected: when transitions are noisy, the model-based advantage of "knowing the dynamics" is diluted because the dynamics themselves are harder to learn precisely.

Summary across levels: The key pattern is that Adaptive-RandQL's advantage over Adaptive-QL grows as exploration becomes more difficult (from indistinguishable at Level 1 to ~2× at Level 2–3), while Kernel-UCBVI dominates all model-free methods across all levels (by roughly 20–50% in cumulative reward). BootDQN's randomized exploration (via ensemble bootstrapping) makes it competitive with RandQL at harder levels, suggesting that randomized exploration helps in deep RL as well, though the discretization-based methods (Adaptive-RandQL, Adaptive-QL) outperform neural network methods when rewards are dense.

Computational Complexity Results (Tables 2 and 3)

Table 2 reports time and space complexity for tabular algorithms:

RandQL: Õ(H) per episode, Õ(HSA) space — identical to OptQL.
UCBVI, PSRL, RLSVI: Õ(HS²A) space — a factor of S more than model-free methods (since they store transition probabilities for all next states).
Greedy-UCBVI: Õ(HSA) per episode, matching model-free methods in time.

Table 3 reports wall-clock measurements for the continuous environment:

Adaptive-RandQL: 5.78 × 10⁻² seconds per episode.
Adaptive-QL: 4.21 × 10⁻² seconds per episode — about 27% faster than RandQL, due to the overhead of Beta sampling and ensemble management.
Kernel-UCBVI: 1.52 × 10⁻¹ seconds per episode — about 2.6× slower than RandQL.

The time overhead of RandQL's randomization (roughly 37% over Adaptive-QL) is modest — maintaining an ensemble of J = 10 Q-copies and sampling Beta random variables adds a constant-factor cost, not an order-of-magnitude increase.

Ablation Studies and Robustness Checks

The paper's ablation studies are minimal but informative. Most are in Appendix I.

RandQL variant comparison (Figure 2, Appendix I): Three variants were compared on the grid-world: RandQL (Algorithm 2, with prior re-injection), Staged-RandQL (Algorithm 1, with stage-based prior reset), and Sampled-RandQL (Algorithm 3, which samples one ensemble member uniformly rather than taking the maximum). Result: Sampled-RandQL performs best, RandQL intermediate, Staged-RandQL worst. The gap between Sampled-RandQL and Staged-RandQL is large (~2.5× in cumulative regret at episode 30,000). This is an important negative result: the staged version that is theoretically analyzed is not the best-performing variant empirically — the continuous prior re-injection of RandQL or the fully-randomized sampling of Sampled-RandQL work better in practice. The authors attribute this to the staged version "artificially slow[ing] down the learning," which is consistent with the analysis: stage boundaries force a reset to the prior, discarding useful information that has accumulated within the stage just to get a clean analytical decomposition.

Simplified bonuses in baselines (Appendix I.1): The bonus-based baselines (UCBVI, OptQL, Adaptive-QL) use simplified bonuses of the form min(√(1/n) + (H-h+1)/n, H-h+1) rather than the theoretically justified Hoeffding-type bonuses. The authors note: "this bonus does not necessarily result in a true upper-confidence bound on the optimal Q-value. However, it is a valid upper-confidence bound for n = 0, which is important in order to discover new state-action pairs." This is a significant caveat — the baseline comparison is not against the theoretical OptQL with its full regret-minimizing bonuses, but against a heuristic simplification. Since the simplified bonus is both easier to tune and often empirically better (as noted by Ménard et al., 2021), this may actually make the baseline stronger than the theoretical version, but it also means the comparison is not a pure "bonus-based theory vs. randomization-based theory" test.

J = 10 ensemble size in experiments vs. theoretical requirement: The theory requires J = ⌈c_J · log(2SAHT/δ)⌉ with c_J ≈ 5.3, which for the grid-world (S=100, A=4, H=50, T=30000, δ=0.05) would be J ≈ 48. The experiments use J = 10 — about 5× smaller than the theoretical prescription. This suggests either that the theoretical J is conservative, or that the performance would improve further with larger J. The paper does not ablate over J to determine the empirical scaling.

PSRL prior matching (Appendix I.1): RandQL uses n₀ = 1/S prior samples — the same prior strength as PSRL (which uses Dirichlet prior with parameter 1/S per next-state). This is a deliberate choice to match the Bayesian prior between the model-based and model-free algorithms, isolating the effect of the exploration mechanism (posterior sampling via model vs. via learning rates) from the effect of prior strength. The paper does not ablate over n₀ to see if RandQL benefits from different prior calibration than PSRL.

No ablation over κ in experiments: The posterior inflation coefficient κ is set to 1.0 for tabular experiments and 10 for continuous experiments, but no intermediate values are tested. The theory prescribes κ = 2β⋆(δ, T) which would be κ ≈ 60 for the grid-world (β⋆ ≈ log(SAH) + log(T) ≈ 20–30). The experimental κ = 1.0 is 60× smaller than the theoretical value — this is a major gap between theory and practice. The fact that RandQL works well with κ = 1.0 (essentially, the "natural" Beta(1, n+n₀) posterior without inflation) suggests that the theoretical κ is highly conservative, but the paper provides no empirical investigation of the κ-sensitivity.

No ablation over ensemble size in continuous environments: The metric experiments use J = 10 ≈ log(T), the same as tabular. The theory requires J = ⌈˜c_J · (log(2HT/δ) + log(N_ε))⌉, which for ε = T^{-1/(d_c+2)} with d_c = 2, N_ε ≈ 10⁴, would be J ≈ 80. Again, the experimental J is much smaller, with no ablation.

No comparison to non-staged RandQL in metric spaces: The metric experiments use only Adaptive-RandQL (the non-staged variant with prior re-injection), not Adaptive-Staged-RandQL (the theoretically analyzed staged variant). This mirrors the tabular finding that the staged version performs worse, but also means the regret bounds of Theorem 3 are not empirically validated — the algorithm that achieves the zooming-dimension regret bound is not the one that was tested.

No statistical significance testing: All results are reported as averages over 4 seeds with error bars, but no formal hypothesis tests (t-tests, confidence intervals for the difference, etc.) are reported. The error bars in Figures 1, 3, and 4 suggest moderate variance (particularly for the model-based methods in the continuous environment, where Kernel-UCBVI's error bars overlap with Adaptive-RandQL's at Level 3), so some of the observed differences may not be statistically significant at the 4-seed level.

Critical Assessment

Claim: RandQL achieves exploration without bonuses through learning rate randomization.

What the experiments demonstrate: This is the central mechanistic claim, and the experiments provide strong qualitative support. Figure 1 and Figure 3 show RandQL (which has no bonus terms) outperforming OptQL (which uses explicit bonuses), and Figures 2 and 3 show RandQL variants matching the performance of PSRL (the model-based posterior sampling algorithm that RandQL is designed to emulate). The fact that RandQL works at all — and works well — with zero bonus tuning is itself evidence for the claim.

What the experiments do not demonstrate: The experiments do not isolate why RandQL works. Is it truly because the Beta-distributed learning rates induce Dirichlet-distributed weights that replicate posterior sampling? Or is it simply because adding noise to Q-learning updates provides a generic exploration benefit (similar to ε-greedy, Noisy Nets, or parameter noise)? The comparison to PSRL provides some evidence for the posterior sampling interpretation — if the exploration were purely generic noise, there's no reason it would match PSRL specifically — but a clean ablation would compare RandQL against a version with Gaussian learning rate noise (matching mean and variance but not the Dirichlet structure) to test whether the Beta distribution specifically matters. This ablation is not performed.

Caveat: The baseline OptQL uses simplified bonuses (equation 26), not the theoretically prescribed Hoeffding bonuses. A stronger test of the claim would compare RandQL against the theoretically optimal OptQL with Bernstein-type bonuses and variance reduction (Zhang et al., 2020) to see if randomization still provides an advantage when the bonus-based method is tuned to its theoretical optimum.

Claim: RandQL is a tractable model-free posterior sampling algorithm.

What the experiments demonstrate: Table 2 shows RandQL's computational complexity matches OptQL (Õ(H) time, Õ(HSA) space), and Table 3 shows wall-clock time in the continuous setting is competitive — Adaptive-RandQL (5.78×10⁻² seconds per episode) is only 27% slower than Adaptive-QL (4.21×10⁻²) and 2.6× faster than Kernel-UCBVI (1.52×10⁻¹). The ensemble size J = 10 adds a constant-factor overhead, not an exponential blowup. This directly supports the "tractable" part of the claim.

What the experiments do not demonstrate: "Posterior sampling" in PSRL means sampling from the exact Bayesian posterior over MDPs. The experiments show RandQL's regret is close to PSRL's, but this is correlational, not distributional — the experiments do not measure whether the distribution of RandQL's Q-value estimates matches the distribution of PSRL's (e.g., by comparing quantiles, testing for distributional equality, or measuring the KL divergence between the induced Q-value distributions). The claim of "posterior sampling" is theoretical (based on Lemma 3's Dirichlet equivalence), and the empirical evidence is only that the regret curves are similar, not that the posterior-sampling mechanism is verified.

Claim: Regret bounds of order Õ(√(H⁵SAT)) for tabular MDPs.

What the experiments demonstrate: Nothing directly. The experiments measure regret on specific environments, but do not systematically vary S, A, H, or T to verify the scaling. For example, the experiments use a single S=100, A=4, H=50 configuration for the grid-world; there are no experiments with S=400, S=900, etc. to test whether regret scales as √S. The experiments show RandQL achieves low regret on the tested environments, but do not validate the functional form of the theoretical bound.

Caveat: This is standard for RL theory papers — empirical validation of regret scaling laws would require orders of magnitude more experiments than are typically reported. The experiments serve to show the algorithm works in practice, not to verify the O(·) scaling.

Claim: Metric space regret bound of order Õ(H⁵/² T^((d_c+1)/(d_c+2))) and zooming-dimension bound.

What the experiments demonstrate: The continuous experiments (Figure 4) use a 2D ball environment (d_c = 2), so the theoretical rate would be Õ(T³/⁴). With T = 20,000 episodes, the experiments are at a single T value — they do not vary T to verify the exponent. The zooming-dimension bound (Theorem 3) is not empirically tested at all, since its advantage over the covering-dimension bound would require an environment where the near-optimal set has lower dimension than the full space, and no such environment is used.

Caveat: As with the tabular scaling, verifying these rates empirically would be a substantial experimental undertaking. The experiments demonstrate that the metric-space algorithms work and are competitive, not that the rates are tight.

Claim: RandQL outperforms existing approaches on baseline exploration environments.

What the experiments demonstrate: On the grid-world (Figure 1), RandQL outperforms OptQL (the only other model-free baseline) by roughly 1.5–2× in regret. On the chain (Figure 3 right), RandQL outperforms OptQL by roughly 2×. On the continuous ball environment (Figure 4), Adaptive-RandQL outperforms Adaptive-QL by roughly 2× at harder difficulty levels (Levels 2–3), and is competitive with BootDQN (a deep RL method). This is the most robustly supported claim: across three environments and two state-space types (tabular and continuous), RandQL consistently beats its most direct model-free comparator.

What the experiments do not demonstrate: "Existing approaches" in the claim is interpreted as model-free approaches (OptQL, Adaptive-QL) — RandQL does not outperform model-based approaches (UCBVI, PSRL, Kernel-UCBVI) in any experiment. The model-based methods achieve 2–3× lower regret in tabular settings and 20–50% higher cumulative reward in continuous settings. The paper is transparent about this (Appendix I: "using a model and backward induction allows new information to be more quickly propagated"), but the "outperforms existing approaches" language in the abstract is somewhat overstated — it should be qualified as "outperforms existing model-free approaches."

Weaknesses in experimental design:

Small seed count: 4 seeds is minimal. For stochastic environments with high variance (especially the continuous ball with σ = 0.025), 4 seeds may not provide reliable estimates of mean performance. The paper would be strengthened by 10–20 seeds and confidence intervals on the regret/reward differences.
No theoretical hyperparameters used: As noted above, J = 10 (vs. theoretical ~48), κ = 1.0 (vs. theoretical ~60), and the baselines use simplified bonuses. The experiments test a heuristic version of RandQL against heuristic versions of the baselines — not the theoretically analyzed algorithms. This is standard practice (theoretical constants are typically loose), but it means the experimental section validates the algorithmic idea, not the specific theoretical construction.
Single continuous environment architecture: The ball environment is a specific structure (Gaussian transitions, Euclidean projection, radial basis reward). It's unclear whether the results generalize to other continuous control problems (e.g., classic control like cartpole, or higher-dimensional problems). The paper would be strengthened by at least one additional continuous environment with different structure (e.g., a navigation task with obstacles, or a higher-dimensional state space).
No comparison to RLSVI in continuous settings: RLSVI is the closest Bayesian model-based competitor and is compared in the tabular experiments, but not in the continuous experiments. Since RLSVI can be adapted to continuous spaces via function approximation, this would be an informative comparison.
Metric experiments use only Adaptive-RandQL, not Net-Staged-RandQL: The theoretically analyzed fixed-ε-net version is never tested; the experiments skip directly to the adaptive version. This is reasonable (adaptive discretization is more practical), but it means the regret bound of Theorem 2 (Net-Staged-RandQL) has no empirical analog.

Missing experiments that would have strengthened the paper:

Ablation over J: How does performance vary with ensemble size? Is J = 5 enough? Does J = 50 improve over J = 10? This would validate the theory's claim that J needs to grow logarithmically with SAHT — or show that small constant J suffices.
Ablation over κ: How sensitive is performance to the posterior inflation coefficient? Does κ = 0.5 cause over-exploration? Does κ = 10 cause under-exploration?
Ablation over n₀: Does the prior pseudo-count affect performance, and is the optimal n₀ different for RandQL vs. PSRL?
Distributional comparison to PSRL: Instead of just comparing regret curves, compare the Q-value estimates themselves — are the quantiles, variance, and correlation structure similar to PSRL's? This would directly test the "posterior sampling" mechanism.
Experiments with varying S, A, H: Even a modest sweep (e.g., grid-worlds of size 5×5, 10×10, 15×15, or horizons H = 10, 30, 50) would provide evidence for or against the theoretical scaling.
A non-staged RandQL in metric spaces: The staged version is theoretically analyzed but empirically worse; the non-staged version is empirically better but not theoretically analyzed. Testing the empirically-superior variant in metric spaces would be more informative than testing the theoretically-analyzed variant.

Summary of experimental support: The experiments provide solid qualitative support for the paper's central idea — randomized learning rates enable effective model-free exploration — and demonstrate that RandQL outperforms its most direct comparator (OptQL) across multiple environments. However, the experiments do not validate the theoretical scaling laws, do not test the specific theoretically-prescribed hyperparameters, and do not establish that the observed benefits are due to the posterior-sampling mechanism rather than generic noise-based exploration. The paper's empirical contribution is in demonstrating feasibility and competitive performance, not in providing rigorous validation of the theoretical analysis. This is a reasonable scope for a theory paper, but the gap between the theoretical construction and the experimental instantiation should be kept in mind when interpreting the results.

6. Limitations and Trade-offs

The difficulty estimation cost is entirely unaccounted for — making the 4× efficiency gain an upper bound, not a realized deployment number

The assumption or constraint. The entire compute-optimal framework depends on estimating prompt difficulty before allocating the inference budget. The paper's method is expensive: generate 2048 samples per question, score them with the PRM to get pass@1 estimates, then bin into quintiles. Section 3.2 acknowledges this directly:

"estimating difficulty in this way still incurs additional computation cost during inference… our experiments do not account for this cost largely for simplicity"

The 2048 samples used for difficulty estimation per question are 4–64× larger than the largest test-time budgets studied (256–512 generations), and this cost is never amortized into the reported gains.

The consequence. In a real deployment, the total compute cost is difficulty_estimation + strategy_execution. Since difficulty estimation generates 2048 samples, and the largest execution budgets are 256–512, the difficulty estimation cost could dominate the total — potentially eliminating or even reversing the claimed 4× efficiency. A system that spends 2048 generations to save 48–192 generations on execution is less efficient overall, even if the execution phase is 4× cheaper. The compute-optimal curves in Figures 4 and 8 represent an upper bound on achievable efficiency that cannot be realized until cheap difficulty estimation is available. The paper candidly frames this as an "exploration–exploitation tradeoff" (Section 3.2) and flags future work on training models to predict difficulty directly from question text — but without such a model, the framework is not production-ready.

What evidence exists in the paper. None — the 2048-sample cost is never included in any budget calculation, amortized, or compared against alternative difficulty estimation strategies. The predicted-vs-oracle difficulty comparison (Figures 4, 8, 11, 12 in Appendices) shows that the PRM-based predicted bins work nearly as well as oracle bins, confirming that ground-truth labels are not needed, but this does not address the 2048-sample cost — it only confirms that the scores used for difficulty estimation can come from the PRM rather than from answer checking.

Mitigation status. The paper explicitly acknowledges this as a key avenue for future work (Section 3.2): "exploring how to estimate question difficulty without this additional computational cost." It proposes training a lightweight classifier to predict difficulty directly from question text, or using adaptive estimation that dynamically adjusts difficulty assessment during problem-solving, but no such method is developed or evaluated. Until this gap is closed, the framework is a proof-of-concept rather than a deployable system, and the 4× headline number should be interpreted as an analytical upper bound, not a practical improvement.

The revision model suffers from a 38% correct-to-incorrect reversion rate that is only patched, not solved

The assumption or constraint. The revision model is trained exclusively on sequences where all in-context answers are incorrect, followed by a correct target (Section 6.1). At test time, the model may encounter a correct answer in its own revision chain — produced during an earlier revision step — and incorrectly "revise" it back to a wrong answer because it has never seen a training example of what to do when the current answer is already correct. The paper reports (Section 6.1):

"approximately 38% of correct answers get converted back to incorrect ones using a naive approach"

The consequence. This reversion phenomenon means the revision chain is not monotonically improving — it oscillates, with correct answers being undone roughly a third of the time. The paper mitigates this by applying majority voting or verifier-based selection across the entire revision chain rather than trusting the final revision output. This works: Figure 6 (left) shows that pass@1 gradually improves over the chain despite the reversions, and Figure 6 (right) confirms that sequential revision with verifier selection outperforms parallel sampling. However, the mitigation is an external patch — a selection mechanism layered on top of the revision model — rather than a fix to the model itself. In high-stakes settings where you want to trust the revision process (e.g., self-improvement loops where the model's output becomes training data), a 38% chance of corrupting a correct answer at each step is unacceptably high.

What evidence exists in the paper. The 38% figure is reported in Section 6.1. Figure 6 (left) implicitly shows the effect: pass@1 curves are not monotonically increasing — there are dips where a correct answer gets revised into an incorrect one — though the overall trend is upward. Figure 6 (right) shows that chain-level selection (majority or verifier) recovers the correct answer at rates competitive with or better than parallel sampling, confirming the patch works at test time. Appendix K (Figure 16) demonstrates a related failure mode: when the revision model is further optimized via ReST^{EM} (an on-policy self-improvement method), performance degrades substantially with sequential revisions — the authors hypothesize this is because on-policy data collection "exacerbates spurious correlations in revision data." This underscores the sensitivity of the revision training to data generation methodology.

Mitigation status. The paper applies a practical mitigation (within-chain selection) that works for the current evaluation setting, but does not propose a principled solution to the reversion problem. A natural fix would be to train the revision model on trajectories that include "no revision needed" segments — e.g., sequences where the last in-context answer is correct and the model is trained to output it unchanged — but this is not attempted. The ReST^{EM} negative result (Appendix K) suggests that naive extension of the training procedure can backfire, so developing robust revision training remains an open problem.

This is exclusively a MATH benchmark study with one model family — generalizability to other domains, models, and task types is unknown

The assumption or constraint. All experiments (Section 5) use the MATH benchmark (high-school competition math, 500 test questions) with PaLM 2-S* as the base model. The paper states (Section 4):

"we believe this model is representative of the capabilities of many contemporary LLMs"

but provides no experimental evidence across model families, benchmarks, or task types.

The consequence. Several aspects of the findings could be model- or benchmark-specific:

The PRM's quality and over-optimization behavior depend on PaLM 2-S*'s output distribution. A model with different calibration (e.g., more or less confident wrong answers) would produce different Monte Carlo rollout labels, shifting the PRM's reliability and the over-optimization threshold (Figure 3).
The revision model's edit-distance-based training relies on the base model generating incorrect solutions that are structurally similar to correct ones — a property that may not hold for models with different error patterns (e.g., models that produce completely unrelated wrong answers rather than near-misses).
Math as a domain has clean correctness signals (exact answer matching) and multi-step symbolic reasoning — it is unclear whether the difficulty-dependent strategy patterns (beam search hurting easy problems, revisions helping easy problems) generalize to code generation (where correctness is tested by unit tests), factual QA (where errors are often retrieval failures, not multi-step reasoning failures), or open-ended generation (where "correctness" is ill-defined).

The test set of 500 questions, split into five difficulty quintiles (~100 each), then further split by two-fold cross-validation, means the compute-optimal strategy is selected based on ~50 validation questions per fold per bin. This is a small sample; the selected strategies may not be robust, and the paper does not report confidence intervals on the compute-optimal scaling curves to assess statistical reliability.

What evidence exists in the paper. None for cross-model or cross-benchmark generalization. All figures report MATH test accuracy and use PaLM 2-S*. There is no experiment on, e.g., GSM8K (another math benchmark) to test benchmark robustness, let alone non-math tasks. The 500-question test set size is fixed and small; there is no subsampling analysis to test sensitivity to test set size.

Mitigation status. The paper acknowledges the need for broader evaluation only implicitly, by stating the model is "representative." Cross-domain and cross-model replication is left entirely to future work. The framework's central claims — difficulty-dependent strategy selection, 4× efficiency gains, FLOPs-matched advantages — are all contingent on the specific model-benchmark pairing, and their generality is an open question.

The 14× larger model baseline is weaker than it needs to be — it uses greedy decoding and non-compute-optimal pretraining

The assumption or constraint. The FLOPs-matched comparison (Section 7) pits PaLM 2-S* with compute-optimal test-time scaling against a ~14× larger model. Two choices weaken this baseline:

Parameter-only scaling: The paper scales parameters while holding training data fixed, following the LLaMA paradigm (Touvron et al., 2023), rather than scaling both parameters and data equally per Chinchilla-optimal pretraining (Hoffmann et al., 2022). The paper acknowledges this (Section 7):

"We choose this setting as it is representative of a canonical approach to scaling pretraining compute and leave the analysis of compute-optimal scaling of pretraining compute… to future work."

Greedy decoding for the larger model: The ~14× larger model uses only greedy decoding — no best-of-N, no majority voting, no beam search. This means the comparison is between a smaller model with adaptive test-time compute and a larger model with zero test-time compute augmentation, rather than between two models both using their optimal inference strategies at their respective scales.

The consequence. A Chinchilla-optimal model trained with 14× more total FLOPs (scaling both parameters and data) would likely outperform a parameter-only-scaled model, making the pretraining baseline stronger than the one tested. Additionally, giving the larger model even a modest test-time compute budget — say, best-of-8 or a single round of revision — would create a much fairer comparison. The reported advantages of test-time compute over pretraining (e.g., +27.8% relative improvement on easy questions at R ≪ 1 in Figure 1) may shrink or reverse against these stronger baselines. The paper's framing as "test-time compute can outperform a 14× larger model" implicitly assumes the larger model is used naively, which may not reflect how these models are deployed in practice (users rarely use pure greedy decoding for high-stakes applications).

What evidence exists in the paper. The comparison is presented in Figure 9 and the bar charts in Figure 1. The paper is transparent about both choices in Section 7. No ablation is performed with the larger model receiving test-time compute, and no Chinchilla-optimal scaling is tested.

Mitigation status. The paper candidly flags these as caveats in Section 7 (parameter-only scaling) and Section 8 (future work on joint optimization). A fairer comparison would give the larger model an inference budget proportional to its size advantage, or at minimum test best-of-N for the larger model. The current results represent a lower bound on how well pretraining could perform — the true tradeoff between test-time and pretraining compute is likely less favorable to test-time compute than the paper's numbers suggest.

Verifier over-optimization is a hard ceiling that the compute-optimal policy works around but does not remove

The assumption or constraint. The PRM verifier, trained with Monte Carlo rollouts, has a finite reliability frontier — beyond a certain optimization intensity, beam search finds solutions that score highly under the PRM but are actually incorrect (over-optimization). This is documented extensively: beam search degrades easy-problem performance at high budgets (Figure 3, right), lookahead search — the most powerful optimizer — paradoxically performs worst overall (Figure 3, left), and qualitative examples in Appendix M show degenerate outputs (repetitive low-information steps, overly short 1–2 step solutions). The compute-optimal policy routes around this by assigning easy problems to best-of-N (weaker optimization) and reserving beam search for medium problems where the PRM's guidance genuinely helps.

The consequence. The compute-optimal approach does not solve the over-optimization problem — it sidesteps it. On medium-difficulty problems where beam search is deployed, over-optimization still limits the scaling ceiling: the beam search curves in Figure 3 flatten and sometimes decline well before the budget is exhausted. The paper's framework is therefore fundamentally bounded by verifier quality — improving the PRM (better training data, adversarial robustness, ensemble methods) would shift the over-optimization threshold and change the optimal policy. The current results are specific to the verifier quality achievable with the Monte Carlo rollout training procedure in Appendix D, which used 16 rollouts per step and the PaLM 2-S* base model. A weaker verifier (e.g., trained on less data or a different model family) would have a lower over-optimization threshold, potentially eliminating the beam search advantage on medium problems. A stronger verifier would push the threshold higher, possibly making aggressive search beneficial even on easy problems.

What evidence exists in the paper. Strong evidence: Figure 3 (right) shows beam search accuracy decreasing on difficulty bin 1 as budget increases (from ~78% at 4 generations to ~77% at 256), Figure 3 (left) shows lookahead search underperforming all methods, and Appendix M (Figures 29) provides qualitative examples of degenerate search outputs. Figures 4 and 8 show that compute-optimal scaling mitigates the problem by switching strategies per difficulty, but cannot eliminate it — the curves still plateau or grow slowly at high budgets.

Mitigation status. The compute-optimal policy is a routing mitigation — it avoids over-optimization where it hurts most — but a principled mitigation (training the PRM to be robust under optimization pressure) is not explored. The paper identifies this as a key direction in Section 8: "improving verifier robustness is the key bottleneck for further scaling test-time compute." Possible approaches mentioned include adversarial training (exposing the PRM to search-generated solutions during training) or ensemble verification (aggregating multiple PRMs), but none are implemented.

Sequential revisions are inherently serial — the framework ignores latency for wall-clock-time-sensitive applications

The assumption or constraint. The paper measures compute in "generations" (number of complete solutions sampled), which is a reasonable proxy for total FLOPs but ignores wall-clock latency. Sequential revisions are inherently serial — each revision depends on the previous one — while parallel best-of-N can be executed simultaneously with sufficient hardware. The paper's compute-optimal policies, especially on easy problems, favor high sequential-to-parallel ratios (Figure 7, right): easy problems perform best with purely sequential revision chains, and at low budgets (8–32 generations), fully sequential is optimal (Figure 7, left). A budget of 64 sequential generations takes ~64× longer in wall-clock time than 64 parallel generations, even though both count as "64 generations" in the paper's accounting.

The consequence. For latency-sensitive applications — interactive assistants, real-time decision-making, any user-facing system where response delay matters — the sequential-heavy strategies favored by the compute-optimal policy may be impractical regardless of their FLOPs efficiency. A system that answers in 500ms with 92% accuracy may be preferable to one that answers in 30 seconds with 94% accuracy, but the paper's framework provides no way to express this tradeoff. The 4× efficiency gain is in FLOPs, not in wall-clock time — and for sequential-heavy allocations, the wall-clock time could be worse than the parallel baseline at the same generation count.

What evidence exists in the paper. None. The paper does not report wall-clock time, latency measurements, or even generation-versus-parallelism tradeoffs. Figure 7 shows what generation-count efficiency looks like for different sequential-to-parallel ratios, but there is no corresponding plot showing wall-clock time (which would be strictly increasing with the sequential ratio at fixed total generations). The FLOPs-matched comparison (Section 7) uses total generation counts, not time, reinforcing the FLOPs-centric framing.

Mitigation status. The paper does not address this tradeoff. A latency-aware cost model would incorporate the parallelism available in the deployment hardware — e.g., if K parallel workers are available, the effective cost of N sequential × M parallel generations is roughly N/K × M in wall-clock time units. Incorporating such a model into the compute-optimal framework would shift the optimal policy toward more parallel allocations, especially for large N/K ratios. This is acknowledged implicitly by the paper's focus on FLOPs rather than time, but never discussed as a limitation.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper establishes that model-free posterior sampling is not merely possible but achievable through a simple distributional equivalence — randomized learning rates in Q-learning induce the same Dirichlet-weighted averaging over historical targets that PSRL achieves through explicit model sampling. This is not an approximation or a heuristic; Lemma 3 (Appendix D.1) proves the equivalence is exact. The significance is in removing the conceptual barrier that previously separated model-based Bayesian exploration from model-free algorithms: posterior sampling was always about the distribution over weights applied to observations, not about the model per se. The model was just one way to parameterize that distribution. By recognizing this, the paper reframes the entire model-free/model-based divide for exploration as a matter of implementation rather than principle — the same statistical operation (Dirichlet-weighted averaging with anti-concentration-driven optimism) can be realized either by maintaining transition posteriors (PSRL) or by randomizing step sizes (RandQL).

This is a reframing with practical consequences, not a paradigm shift. The core exploration mechanism — posterior sampling — was already well-understood, and the regret bounds RandQL achieves (Ỡ(√(H⁵SAT))) match rather than improve upon existing model-free methods (OptQL). The contribution is not "better exploration" but "the same exploration quality through a different, computationally simpler mechanism." The practical consequence is that Bayesian-style exploration can now be retrofitted into any Q-learning pipeline by changing the learning rate schedule from deterministic to Beta-distributed — no architectural changes, no bonus terms, no posterior maintenance. This matters for the deep RL community, where randomized exploration (BootDQN, Noisy Nets, HyperDQN) has shown strong empirical results but lacked theoretical grounding. RandQL provides that grounding: it shows exactly what distribution the randomization should follow (Beta, parameterized by visit counts and prior strength) to replicate the statistical properties of posterior sampling, rather than the ad-hoc Gaussian or uniform noise used in prior heuristic methods.

The paper also reconciles a tension in the PSRL literature. The model-based PSRL algorithm is both theoretically sound (near-optimal regret) and empirically strong, but it was unclear whether its success came from the Bayesian posterior itself or from some side effect of model-based planning. RandQL's competitive empirical performance against PSRL (Figure 1, Section 5) — achieving similar regret curves despite being model-free — isolates the contribution of the posterior sampling distribution from the contribution of model-based planning. The residual gap between RandQL and PSRL (roughly 2–3× higher regret in tabular settings, Figures 1 and 3) can be attributed to the model-free disadvantage in value propagation (model-based methods propagate information backward in one episode; Q-learning takes H episodes). This decomposition — posterior sampling provides ~50–70% of PSRL's benefit, model-based planning provides the remaining ~30–50% — was previously unavailable.

The work also redirects research attention from bonus design to learning rate design for model-free exploration. Prior to RandQL, the model-free exploration literature focused overwhelmingly on constructing tighter confidence bounds (Hoeffding → Bernstein → empirical Bernstein → variance reduction). RandQL shows that a completely different axis — the distribution of the learning rate — can substitute for the bonus entirely. This doesn't make bonus-based methods obsolete (they still achieve tighter regret bounds, e.g., Zhang et al. 2020's Ỡ(√(H³SAT)) vs. RandQL's Ỡ(√(H⁵SAT))), but it opens a parallel research track: instead of asking "how can we construct a tighter bonus?", ask "what learning rate distribution produces the right exploration properties?" This reorientation is valuable because learning rate design may prove more robust to function approximation — in deep RL, where explicit bonuses are notoriously hard to calibrate, randomized learning rates (even heuristic ones like Noisy Nets) have already shown empirical success. RandQL provides the theoretical scaffolding to make this heuristic rigorous.

Research directions that become more attractive:

Learning rate distribution design for deep RL. RandQL's Beta(1/κ, (n+n₀)/κ) prescription is derived for tabular and metric settings; adapting it to function approximation (where there is no clear "visit count" for a continuous state) is a natural extension. The connection to BootDQN's ensemble re-sampling and Noisy Nets' parametric noise suggests these heuristics may already approximate aspects of the RandQL distribution.
Combining randomized learning rates with variance reduction. The paper explicitly notes (Section 6) that RandQL could likely achieve the optimal Ỡ(√(H³SAT)) rate by incorporating the reference-advantage decomposition of Zhang et al. (2020). The interaction between randomized weights and variance-reduced targets is unexplored.
Model-free algorithms with full Bayesian posteriors over Q-values. RandQL's ensemble of J copies represents J independent samples from the induced posterior. With larger J, one could maintain a richer representation of the posterior (quantiles, credible intervals) rather than just the maximum, enabling risk-sensitive exploration.

Research directions that become less attractive:

Purely bonus-based model-free exploration without randomization. RandQL's empirical advantage over OptQL (Figures 1, 3, 4) suggests that randomization provides exploration benefits beyond what deterministic bonuses achieve, at least with the simplified bonus heuristics commonly used in practice. The burden of proof now shifts to bonus-based methods to show they can match randomized methods' empirical performance.
Intractable model-free posterior sampling approximations. Dann et al. (2021)'s intractable approach is now superseded by RandQL's tractable construction. Research effort should shift from "is model-free posterior sampling possible?" to "how can we make it scale to deep RL?"

Follow-Up Research This Work Enables

1. Empirical verification of the Dirichlet weight distribution in RandQL. The paper's central theoretical claim is that Beta-distributed learning rates induce Dirichlet-distributed aggregate weights (Lemma 3), which in turn replicate PSRL's posterior sampling. The experiments demonstrate similar regret curves to PSRL, but do not directly test the distributional equivalence. A strong follow-up would instrument the Q-value estimates during training and perform distributional comparisons: for a fixed state-action pair at a fixed visit count, collect the empirical distribution of Q-estimates across seeds and ensemble members, and test whether this distribution matches the Dirichlet-weighted sum of targets that would arise from PSRL. Specifically, in a tabular MDP with known optimal values, one could compare the quantiles, variance, and KL divergence between the RandQL-estimated Q-distribution and the PSRL-estimated Q-distribution. If the distributions match (beyond just producing similar regret), it validates the core mechanism. If they diverge (e.g., RandQL's distribution is more concentrated or has different tail behavior), it would identify where the "lazy approximation" (using stale value functions rather than recomputing targets) causes a genuine distributional shift, not just a bias in the mean.

2. Ablation over the Beta distribution parameters to isolate the contribution of the distribution shape. The paper uses Beta(1/κ, (n+n₀)/κ) learning rates and shows this produces Dirichlet-distributed weights. A clean ablation would compare this against: (a) Beta(1/κ, constant) — fixed shape, no visit-count dependence, which would remove the "learning rate decays with visits" property; (b) Gaussian learning rates with matched mean and variance to the Beta — which would preserve the first two moments but destroy the Dirichlet structure; (c) deterministic learning rates equal to E[Beta(1/κ, (n+n₀)/κ)] = 1/(1 + n + n₀) — which removes all randomness while preserving the expected update magnitude. If (a) and (b) perform substantially worse than RandQL, it confirms that the specific Beta-with-visit-count-dependent-parameters distribution matters, not just "adding noise" or "decaying learning rates." If (c) performs nearly as well as RandQL, it would undermine the randomization claim — suggesting the benefit comes from the aggressive learning rate schedule (Beta(H, n) rather than Beta(1, n)) rather than from the randomness per se. This experiment would be most informative in the tabular grid-world (Figure 1) where RandQL's advantage over OptQL is clearest.

3. Extending RandQL to deep RL with a neural episodic memory for visit counts. The Beta distribution parameters in RandQL depend on n_t^h(s,a) — the exact visit count of each state-action pair. In deep RL with continuous states, exact visit counts are unavailable. A natural extension would maintain an episodic memory (e.g., a k-NN index over state-action embeddings) that provides pseudo-counts for each query. At each update, the algorithm retrieves the approximate visit count ^n for the current state-action pair, samples w ~ Beta(1/κ, (^n + n₀)/κ), and applies the RandQL update rule. This would test whether the theoretical benefits of Beta-distributed learning rates survive the approximation error in neural function approximation. The experiment should compare this "Neural RandQL" against BootDQN (which uses ensemble resampling but not Beta-distributed learning rates) and Noisy Nets (which uses parametric Gaussian noise but not visit-count-dependent noise magnitude) on standard deep RL benchmarks (Atari, MuJoCo). The key metric is whether the explicit Beta distribution and visit-count dependence provides benefits over the heuristic noise schemes currently used. The theory predicts that the advantage should be largest in sparse-reward environments where the visit-count-dependent noise (large for rarely-visited states, small for familiar ones) provides a principled exploration signal.

4. Testing the sensitivity of RandQL to the posterior inflation coefficient κ across orders of magnitude. The experiments use κ = 1.0 (tabular) and κ = 10 (metric), while the theory prescribes κ ≈ 60 for the grid-world (κ = 2β⋆(δ, T) with β⋆ ≈ 20–30). This 60× gap between theory and practice raises an important question: is the theoretical κ unnecessarily conservative, or does the algorithm become fragile at intermediate κ values? A systematic sweep would test κ ∈ {0.1, 0.5, 1.0, 2.0, 5.0, 10, 20, 50, 100} on the grid-world and chain environments, measuring both final regret and the rate of early exploration. The theory predicts that too-small κ (over-concentrated Dirichlet, under-exploration) should cause the agent to plateau at a suboptimal policy, while too-large κ (over-dispersed Dirichlet, over-exploration) should cause excessive regret from trying bad actions too often. The sweet spot — where performance is robust — may be much wider than the theory suggests, which would be valuable guidance for practitioners. If instead performance is highly sensitive to κ, it would indicate that the theoretical κ is genuinely necessary and the current experimental settings were lucky, motivating research into adaptive κ-selection schemes.

5. Combining RandQL's randomized learning rates with variance-reduced Q-learning to close the H² gap to the lower bound. RandQL achieves Ỡ(√(H⁵SAT)) regret, while the lower bound is Ω(√(H³SAT)) [Jin et al., 2018] and Zhang et al. (2020) achieves Ỡ(√(H⁴SAT)) (nearly matching) using reference-advantage decomposition and variance reduction. The paper explicitly conjectures that RandQL could achieve the optimal rate with variance reduction (Section 6: "We conjecture that RandQL could get optimal regret in the tabular setting if coupled with variance reductions techniques"), but notes that "obtaining such improvements is not straightforward due to the intricate statistical dependencies involved in the analysis of RandQL." A concrete follow-up would implement and analyze Variance-Reduced RandQL, combining the Beta learning rate sampling with the reference-advantage decomposition: maintain a reference value function that is updated slowly (or in stages), and use the randomized learning rates to update the advantage over the reference rather than the raw Q-value. The key challenge is that the randomized weights create dependencies between the advantage estimate and the reference value that don't exist with deterministic learning rates. Resolving these dependencies — either through a staged analysis (exploiting that within-stage targets are i.i.d.) or through a martingale concentration argument for the randomized weights — would close the remaining gap between model-free posterior sampling and the information-theoretic lower bound, establishing that randomized exploration can match the sample efficiency of the best bonus-based methods.

6. RandQL for partially observable or non-Markovian settings as a stress test of the posterior sampling mechanism. The MDP assumption is central to RandQL's analysis: the Dirichlet weight equivalence relies on the targets being (conditionally) i.i.d. samples from the transition kernel. In a partially observable MDP (POMDP) or a non-stationary environment, the next-state distribution given (s,a) depends on the agent's history, not just the current state. This breaks the i.i.d. assumption underlying the Dirichlet weight distribution. A stress-test experiment would apply RandQL without modification to a simple POMDP (e.g., a grid-world where the agent observes only its x-coordinate, not its y-coordinate, requiring memory) and compare against PSRL (which, as a model-based method, can incorporate belief states) and standard bonus-based Q-learning. If RandQL's exploration degrades catastrophically (e.g., the agent never discovers the optimal policy), it would confirm that the Dirichlet weight mechanism is fragile to violations of the i.i.d. assumption — the randomized learning rates may amplify correlations in the observation sequence rather than providing principled exploration. If RandQL remains competitive, it would suggest the Beta randomization provides robust exploration even when the theoretical equivalence breaks down, making it safer for practical deployment where strict MDP assumptions rarely hold. The experiment would provide either a clear boundary condition for RandQL's applicability or evidence for its robustness beyond the theory.

Practical Applications and Downstream Use Cases

1. On-device reinforcement learning for embedded systems. RandQL's Ỡ(H) per-episode time complexity (Table 2) and Ỡ(HSA) space complexity — matching standard Q-learning and roughly S× smaller than model-based methods (Ỡ(HS²A) for UCBVI, PSRL) — makes it the most practical choice for memory-constrained embedded devices (microcontrollers, IoT sensors, edge accelerators) where storing full transition probability tables is infeasible. In a robotic navigation task with S = 1000 discrete states (a coarse grid of a room) and A = 4 actions, PSRL requires storing 1000 × 4 × (1000 + 1) ≈ 4 million transition probability parameters; RandQL stores 1000 × 4 ≈ 4000 Q-values, plus a J = 10 ensemble factor (40,000 total — still 100× smaller). The empirical performance gap (RandQL achieves 2–3× higher regret than UCBVI in Figure 1) is the price paid for this memory reduction. For applications where the memory constraint is binding and some performance degradation is acceptable (e.g., a vacuum-cleaning robot that learns room layouts online with 512KB of RAM), RandQL's model-free posterior sampling offers the best exploration quality achievable within the storage budget. The staged variant (Staged-RandQL) is particularly suitable here: stage boundaries provide natural checkpoints for persisting Q-values to flash storage, and the per-stage independent estimates mean a power-loss event only loses the current stage's worth of learning (roughly H visits per state-action pair), not the entire learning history.

2. Continuous control with adaptive discretization in low-dimensional state spaces. The adaptive metric extension (Adaptive-Staged-RandQL, Algorithm 6, Appendix F) achieves regret scaling with the zooming dimension d_z rather than the covering dimension d_c. In many practical control problems, the optimal policy depends on a low-dimensional manifold of the state — e.g., a robotic arm's optimal joint torques may depend primarily on joint angles and velocities (a 2d_S-dimensional manifold in a d_S-dimensional configuration space) rather than on the full state including higher-order derivatives. In such cases, d_z ≪ d_c, and Adaptive-Staged-RandQL automatically concentrates its discretization budget on the near-optimal manifold. The paper's continuous experiments (Figure 4) demonstrate this in a 2D ball environment (d_c = 2) with a radial reward centered at (0.5, 0.5), where the optimal policy is to move toward the center — effectively a 1D manifold (distance to center). The adaptive algorithm's competitive performance against Kernel-UCBVI (which requires O(N³) kernel matrix operations for N representative states) with O(H log N_ε) per-episode time suggests that for control problems where the state space dimension is moderate (d ≤ 6-8) and a Lipschitz reparameterization exists (Assumption 3), adaptive discretization with randomized Q-learning provides a computationally efficient alternative to kernel-based or neural-network-based model-free RL. The experimental results show that at harder exploration levels (Levels 2–3, Figure 4), Adaptive-RandQL outperforms both DQN and BootDQN, making it a viable choice for sample-efficient learning in robotic reaching, pushing, or pick-and-place tasks with known smooth dynamics.

3. Ensemble-based exploration for deep Q-networks with principled noise. The deep RL community has converged on two families of randomized exploration: action-space noise (ε-greedy, entropy regularization) and parameter-space noise (Noisy Nets, where network weights have learned noise variances; BootDQN, where an ensemble of Q-networks with different initializations provides diversity). RandQL suggests a third family: learning-rate-space noise — randomize the optimizer's step size according to a Beta distribution parameterized by (approximate) visit counts. In the DQN setting, this could be implemented by maintaining a count-based exploration bonus (e.g., through hash-based counting or a learned density model) that provides pseudo-counts ^n for each state-action pair, then using a learning rate α ∼ Beta(1/κ, (ˆn + n₀)/κ) in the TD update for that transition. This is algorithmically trivial to add to any DQN implementation (two extra lines: one to query the pseudo-count model, one to sample the Beta random variable) and requires no architectural changes, unlike Noisy Nets (which replace all linear layers with noisy variants) or BootDQN (which maintains J separate networks). The paper's experiments show that even a constant J = 10 ensemble with Beta learning rates outperforms both DQN and BootDQN on the ball environment at hard exploration levels (Figure 4, Levels 2–3). If this benefit transfers to Atari or MuJoCo benchmarks, it would provide a lightweight, theoretically-grounded exploration method that can be retrofitted into existing DQN/SAC/PPO codebases with minimal modification.

4. Self-improving RL systems where model-free simplicity enables online deployment. Model-based algorithms like UCBVI and PSRL achieve lower regret (Figures 1, 3) but require storing and updating a full transition model — an O(S²A) memory and computational burden that prevents online deployment on systems with limited computation per timestep. RandQL's per-step update (sample J Beta variables, compute J weighted averages, max over J) is constant-time with respect to S and A — only the visited state-action pair is updated. This makes RandQL suitable for lifelong learning scenarios where an agent (robot, recommendation system, dialogue agent) continuously interacts with its environment and must update its policy online without any batch re-training phase. The staged variant is particularly well-suited: stage boundaries provide natural moments to update the policy (e.g., between user sessions or during maintenance windows), while within-stage updates are cheap constant-time operations. The theoretical guarantee — Ỡ(√(H⁵SAT)) regret with high probability — provides a statistical safety net: even without batch retraining or expensive model-based planning, the agent's cumulative sub-optimality grows sublinearly, meaning its performance converges to near-optimal over time. The computational complexity numbers from Tables 2 and 3 quantify this advantage: RandQL's per-episode wall-clock time is within 27% of Adaptive-QL (a bonus-based method) and 2.6× faster than Kernel-UCBVI, while achieving 2× better cumulative reward than Adaptive-QL at hard exploration levels (Figure 4, Level 2). This combination — provably sublinear regret, competitive empirical performance, and constant-time updates — makes RandQL the most deployable provably-efficient RL algorithm for online, resource-constrained settings.

When to Prefer This Method

The paper positions RandQL against two main alternatives: bonus-based model-free methods (OptQL, Adaptive-QL) for the model-free setting, and model-based posterior sampling (PSRL, RLSVI) for the Bayesian exploration setting. The tradeoffs are explicit in the paper's analysis and experiments:

Prefer RandQL over OptQL/Adaptive-QL when:

You want model-free exploration without manual bonus tuning. RandQL's exploration emerges from the Beta distribution parameters (κ, n₀), which depend only on problem-independent quantities (horizon H, confidence δ, Lipschitz constants L_r, L_F, L_V) rather than requiring per-environment bonus calibration. The experiments (Figures 1, 3, 4) show RandQL outperforms OptQL/Adaptive-QL at fixed hyperparameter settings, while the bonus-based baselines use simplified heuristic bonuses (equation 26 in Appendix I) that the authors note "do not necessarily result in a true upper-confidence bound."
You value empirical exploration quality over theoretical optimality. RandQL achieves Ỡ(√(H⁵SAT)) regret vs. Ỡ(√(H⁴SAT)) for the best variance-reduced OptQL variant (Zhang et al., 2020), but the empirical gap in Figures 1 and 3 favors RandQL by 1.5–2× over the simplified-bonus OptQL baseline. The theoretical optimality of the best bonus-based method has not been realized in the same experimental setting, making the practical comparison ambiguous.
Your deployment has tight memory constraints. RandQL's Ỡ(HSA) space complexity matches OptQL — both are S× smaller than model-based methods (Ỡ(HS²A)) — but RandQL adds only a J = Ỡ(1) factor for the ensemble, while the bonus terms in OptQL add negligible overhead. The space advantage over model-based methods is shared by both model-free approaches.

Prefer RandQL over PSRL/RLSVI when:

You cannot afford to learn or store a transition model. RandQL stores Q-values only (4 × J × S × A × H floating-point numbers for J ensemble members, S states, A actions, H steps); PSRL stores Dirichlet posterior parameters for each (s,a) pair — an A × S × H matrix of size S× larger (since the posterior over next-state distribution requires S concentration parameters per state-action pair). In the grid-world (S = 100, A = 4, H = 50), RandQL with J = 10 stores ~200,000 values; PSRL stores ~2,000,000. For S = 10,000, RandQL stores ~20 million values; PSRL stores ~200 million.
You need constant-time per-step updates. RandQL's update (sample J Beta variables, J weighted averages, max) is O(J AH) = Ỡ(H) per step; PSRL requires solving an MDP (e.g., value iteration or policy iteration) at each episode, which is at minimum O(S²A H) for one sweep of value iteration. Table 2 confirms this: RandQL's per-episode time is Ỡ(H), while UCBVI and PSRL are Ỡ(HS²A). For online deployment where computation per timestep must complete within the environment's step interval (milliseconds for real-time control), RandQL's constant-time update is essential.
You accept 2–3× higher regret in exchange for model-free simplicity. Figures 1 and 3 show this gap consistently: at episode 30,000 on the grid-world, UCBVI achieves ~100,000–150,000 cumulative regret vs. ~300,000–400,000 for RandQL; on the chain, PSRL achieves ~2,500 vs. ~5,000–7,500 for RandQL. This gap is the cost of avoiding model learning and backward induction. For applications where this regret premium is acceptable (e.g., the environment steps are cheap and interactions are abundant), model-free deployment may be preferred.

Prefer model-based PSRL/UCBVI over RandQL when:

Sample efficiency is paramount. The 2–3× regret gap in Figures 1 and 3 represents 2–3× more suboptimal episodes before convergence. In applications where each interaction is expensive (e.g., clinical trials, expensive physical experiments), model-based methods' faster convergence justifies their higher per-step cost.
The state space is small enough that O(S²A) memory is feasible (S ≤ 100–1000). In this regime, the memory overhead of model-based methods is negligible, and their sample efficiency advantage is pure gain.
You need the best possible asymptotic performance. Model-based methods' ability to propagate value information backward through the MDP in one episode (via value iteration) means they converge to near-zero per-episode regret faster than model-free methods, which require at least H episodes to propagate information from the terminal step to the initial state.