Imitation learning trains an agent to copy recorded demonstrations. It rests on an assumption that is almost never true: that the demonstrator always chose the best action. When that assumption fails, the copied policy can be no better than its teacher. The usual escape is to let the agent keep learning online from reward. That raises a question nobody has answered formally: how much should the agent trust the demonstrations while it explores? If it trusts them too much, a bad teacher traps it. If it trusts them too little, a good teacher is wasted. Bandit theory has sharp results on how a prior belief speeds up or slows down learning. The most relevant one, On the Prior Sensitivity of Thompson Sampling, shows that a confidently wrong prior can inflate regret multiplicatively, as $\Theta(\sqrt{T/p})$ when the prior puts mass $p$ on the truth.
This note proposes a concrete fix and a theory for it. Turn each demonstration into a small number of randomized fake reward observations on the demonstrated action, which amount to a noisy vote that "this action was good." Mix these with the agent's real data, and act greedily on the resulting perturbed estimate. This is perturbed-history exploration (PHE), a method that explores by adding random fake rewards to the data and then acting greedily (Perturbed-History Exploration in Stochastic Linear Bandits), with demonstrations entering as extra perturbed pseudo-observations. The central claim is that this construction turns the multiplicative penalty of a wrong expert into an additive burn-in cost. It keeps most of the speed-up from a good expert, and one trust knob moves the algorithm along a provable trade-off between the two.
Core Claim
The expert optimality assumption is a prior: it says the demonstrated action is optimal. Behavior cloning holds this prior with infinite confidence, which is why it hits a ceiling. Thompson sampling with a sharp demonstration-derived prior holds it with finite but unbounded confidence, which is why a bad expert costs $\sqrt{T/p}$. Our proposal holds it with a bounded number of randomized votes.
In the linear bandit version, let $\mathcal{H}_t$ be the agent's real observations $(x_s, r_s)$. Let $\mathcal{E}$ be the demonstration set of feature vectors $x_{a_E}$ of expert-chosen actions, with no rewards. The estimator at round $t$ is
$$\hat\theta_t = \arg\min_\theta \sum_{\mathcal{H}_t}\big(x_s^\top\theta - r_s\big)^2 + \sum_{\mathcal{E}} \sum_{j=1}^{w}\big(x_{a_E}^\top\theta - z_{j}\big)^2 + \sum_{\text{PHE}}\big(x^\top\theta - u\big)^2 + \lambda\lVert\theta\rVert^2,$$
and the agent pulls the arm maximizing $x^\top\hat\theta_t$. The terms are defined as follows. The $w$ demonstration votes $z_j \sim \text{Bernoulli}(q)$ are redrawn every round, with $q$ the trust level. The PHE pseudo-rewards $u \sim \text{Bernoulli}(1/2)$ are the usual ones LinPHE attaches to real observations. $\lambda$ is ridge regularization. The target result has the form
$$R(T) \le \tilde O\big(d\sqrt{T}\big) + O\big(w\,|\mathcal{E}|\,\Delta_E\big) \quad \text{(bad expert)}, \qquad R(T) \le \tilde O\big(d\sqrt{T}\big) - G(w, q, |\mathcal{E}|) \quad \text{(good expert)}.$$
Here $\Delta_E$ is the expert's per-step suboptimality gap and $G$ is the exploration saved when the expert is right. The additive shape follows from counting: $w|\mathcal{E}|$ fake votes can mislead the agent for at most on the order of that many pulls before real data outweighs them. The randomization of $z$ is what keeps the vote from locking the agent onto the expert's arm, because it preserves the constant probability of optimism on unexplored arms that Worst-Case Regret Bounds for Exploration via Randomized Value Functions shows is sufficient.
The good-expert gain mirrors the additive prior-diffusiveness burn-in of Prior Diffusiveness and Regret in the Linear-Gaussian Bandit. That paper proves prior uncertainty adds $dr\sqrt{\mathrm{Tr}(\Sigma_0)}$ to regret rather than multiplying it, but only when the prior is correct. We ask for an additive term whether or not it is.
Relation to Prior Work
Two results motivate the proposal. Liu et al. show that misspecified sharp priors cost $\sqrt{T/p}$, in a two-action, two-model setting. Zhu, Duchi and Van Roy show that correct priors cost only an additive burn-in. Neither covers a prior that comes from a possibly suboptimal demonstrator, and that setting is exactly the one imitation learning lives in.
Three lines of work supply the method. LinPHE shows that fake Bernoulli rewards plus greedy regression match LinUCB and LinTS at $\tilde O(d\sqrt{n})$, and in their 5-dimensional experiment LinPHE runs in 113 seconds versus 273 for LinTS. It is a pure cold-start method. Randomized Exploration in Reinforcement Learning with General Value Function Approximation (LSVI-PHE) extends reward perturbation to Markov decision processes (MDPs, the standard model of sequential decisions with states). It fits $M$ perturbed value functions and acts on their maximum, again with no prior data. We reuse both constructions and add the demonstration votes.
Three demonstration methods set the empirical bar, and each differs from ours in a specific way. Monte Carlo Augmented Actor-Critic (MCAC) makes demonstrations optimistic deterministically, through $\max(Q_{TD}, Q_{MC})$. That works under sparse reward but overestimates under dense reward. Our optimism is randomized, and its weight is bounded by $w$. Flow Matching with Injected Noise (FINO) perturbs the action distribution of a cloned policy and then explores with a temperature heuristic. We perturb the value evidence the demonstrations provide, which gives a quantity we can analyze. APC-RL arbitrates between prior actors and a free actor using Q-values. It works well but carries no guarantee, and its compute grows with the number of prior actors.
Offline expertise estimators constrain the design rather than compete with it. ILEED and MARWIL reweight demonstrations by estimated quality but cannot discover actions the data never contains. We use ILEED's per-demonstrator expertise score as an optional data-driven setting of $q$. This replaces a hand-tuned trust level, but it is not needed for the core result.
Research Program
The first stage is theory, done in increasing generality. We begin with the two-action, two-model instance of Liu et al. and prove that the demonstration-vote estimator's regret against a wrong expert is additive in $w|\mathcal{E}|$. This directly contrasts with their $\sqrt{T/p}$ rate. Next we extend to linear bandits. The expert there has coverage bias: it picks only a few arm directions, so the votes concentrate the estimate along a low-rank subspace. We expect the bound to depend on how much of the gap $\Delta_E$ lies in the covered directions.
We also prove a lower bound. Any algorithm whose regret improves by an amount $G$ when the expert is optimal must pay at least a matching additive amount when the expert is wrong. This makes the trust knob a genuine Pareto frontier rather than an arbitrary hyperparameter. Finally, we derive the setting of $(w, q)$ that minimizes worst-case regret over a stated range of expert gaps. This gives practitioners a rule in place of a grid search.
The second stage transfers the construction to deep reinforcement learning. Demonstration transitions sit in the replay buffer. Each of $M$ critics receives its own independent draw of Bernoulli($q$) reward votes on demonstrated actions, weighted by $w$ and multiplied into the demonstration's reward-to-go target. Agent transitions receive the Gaussian reward perturbation used by LSVI-PHE. The policy acts greedily on the maximum across critics.
For datasets that carry rewards, the vote becomes a randomized optimistic offset on the demonstration return, which is the stochastic analogue of MCAC's max operator. We keep $M$ small ($M = 8$ or $16$), since LSVI-PHE reports that small ensembles already succeed empirically, and we test whether the $M=1$ case suffices, as random reward perturbation (RRP, Exploration by Random Reward Perturbation) suggests.
Baselines
The naive reference points are behavior cloning, which marks the ceiling, and cold-start LinPHE or LSVI-PHE, which ignore demonstrations. Together they define the two ends of the trust frontier. Any useful method must sit strictly inside the region they bound: better than cold start when the expert is good, and better than cloning when the expert is bad.
The strongest principled competitor in bandits is Thompson sampling with a demonstration-derived Gaussian prior whose variance is tuned. It is the Bayesian way to encode "trust the expert this much," and Liu et al. characterize its failure mode. We give it the same demonstrations, the same trust budget (prior precision matched to $w|\mathcal{E}|$), and a grid over prior variance equal in size to our grid over $(w, q)$.
In deep RL the strongest competitors are APC-RL and MCAC. APC-RL reports reaching a CarRacing score of about 900 in 30k steps from roughly 250-score human demonstrations, and 100% success on goal-misaligned PointMaze within 0.5M steps, where cloning-based baselines reach 0–7%. MCAC reports solving Pointmass and Block Lifting, where SAC and TD3 make zero progress, but no reported final numeric result was found on Lacuna for MCAC on these tasks. On D4RL and OGBench, FINO reports 104 on Adroit door-cloned and 97 on humanoidmaze-medium-navigate, versus 61 for the Flow Q-Learning backbone.
All deep methods share the same base actor-critic, demonstration data, environment step budget, and number of hyperparameter trials, with five or more seeds. Beating a baseline means one of two things. The method either matches the competitor's final return in fewer steps, or it avoids the competitor's documented failure. That failure is collapse to the teacher for cloning. For MCAC it is degradation under dense reward, and for Bayesian Thompson sampling it is the $\sqrt{T/p}$ growth.
The key ablation removes the randomization: votes are fixed at $z = q$. Its purpose is to isolate whether randomness, rather than extra weight on demonstrations, produces the additive penalty.
Why not just…?
Why not just widen the prior in Thompson sampling instead of perturbing? In the linear-Gaussian case this is a real threat, because randomized pseudo-observations and a tempered Gaussian prior may be nearly equivalent. If they are, the theoretical contribution stands as a result about tempered demonstration priors, and perturbation becomes the scalable way to implement it in deep networks, where exact posteriors are intractable (the LSVI-PHE setting). The bandit experiments will report whether the two frontiers coincide. If they do, we will say so plainly.
Why not just preload demonstrations into the replay buffer and run LSVI-PHE or RRP unchanged? This is the most plausible simpler competitor, since the demonstrations then act as ordinary data. The difficulty is that reward-free demonstrations carry no reward to perturb. With rewarded demonstrations, the agent inherits the expert's narrow coverage without any optimism on the expert's choices, which is the sparse-reward stagnation MCAC was built to fix. We run exactly this configuration as a baseline. If it matches our method on MCAC's sparse suite and APC-RL's CarRacing, the demonstration-vote mechanism is unnecessary.
Why not just filter demonstrations with ILEED or MARWIL and then fine-tune? Filtering discards bad actions but cannot add missing ones. MARWIL's improvement stays inside the data's support, and ILEED assumes suboptimality is random noise rather than systematic bias. Filtering also composes with our method, since it can supply $q$. We therefore test ILEED-then-fine-tune against votes with ILEED-set $q$ on ILEED's Robomimic Square tiers ("Worse," "Okay," "Better"), where the demonstrations are systematically mediocre.
Why not just use MCAC's deterministic max? MCAC is documented to overestimate under dense reward. We include D4RL Gym-MuJoCo medium datasets, which have dense reward, specifically to test whether bounded randomized optimism avoids that failure while matching MCAC under sparse reward.
Proposed Experiments
The bandit experiments use the LinPHE synthetic setup: 100 arms, $d \in \{5, 10, 20\}$, and 10,000 rounds. We add synthetic experts whose gap $\Delta_E$ ranges from zero to large and whose coverage ranges from a single arm to the full span. Separately, we reproduce the two-model Bernoulli instance of Liu et al. The decisive check is how regret against a wrong expert scales. We fit it as a function of $T$ and of demonstration count. Our claim requires it to be flat in $T$ beyond the $d\sqrt{T}$ term and linear in $w|\mathcal{E}|$, while the tuned-prior Thompson baseline grows as $\sqrt{T/p}$. We also trace the empirical good-versus-bad frontier by sweeping $(w, q)$ and compare it with the proven lower bound.
The deep RL experiments use four groups of tasks. The first is MCAC's sparse suite (Pointmass, Block Lifting, Robosuite Door). The second is APC-RL's misaligned PointMaze and suboptimal-human CarRacing. The third is D4RL Adroit door-cloned and OGBench humanoidmaze-medium-navigate, for comparison with FINO. The fourth is D4RL Gym-MuJoCo medium, which tests dense reward. Metrics are normalized return, success rate, and the number of environment steps needed to exceed the teacher's return.
Three outcomes would falsify the proposal. The first is the fixed-vote ablation performing as well as the randomized one. The second is plain buffer-preloaded LSVI-PHE matching it. The third is the theory-derived $(w, q)$ performing no better than a tuned grid.
References
- On the Prior Sensitivity of Thompson Sampling
- Perturbed-History Exploration in Stochastic Linear Bandits
- Worst-Case Regret Bounds for Exploration via Randomized Value Functions
- Prior Diffusiveness and Regret in the Linear-Gaussian Bandit
- Randomized Exploration in Reinforcement Learning with General Value Function Approximation
- Monte Carlo Augmented Actor-Critic for Sparse Reward Deep Reinforcement Learning from Suboptimal Demonstrations
- Flow Matching with Injected Noise for Offline-to-Online Reinforcement Learning
- APC-RL: Exceeding data-driven behavior priors with adaptive policy composition
- Imitation Learning by Estimating Expertise of Demonstrators
- Exponentially Weighted Imitation Learning for Batched Historical Data
- Exploration by Random Reward Perturbation