PaperlayerView exact revision on arXiv

Source-linked AI summary

Minimax Regret for Sobolev Kernel-Based Reinforcement Learning

Haichen Hu, David Simchi-Levi

arXiv:2610.34045v1cs.LGmath.STstat.MLstat.TH

TL;DR

Kernel-based reinforcement learning still lacks a settled optimal regret rate, in part because action choice and learning across states pose distinct challenges. This paper analyzes Sobolev-kernel RL and introduces SOVI. It proves matching regret-rate bounds under stated conditions, partially addressing the open problem for this kernel setting.

  • Problem

    The paper asks for the optimal regret growth in kernel-based reinforcement learning, where the learner must learn unknown rewards and transitions and action selection differs from learning across states.

    Source: §1 · p. 2, §3 · p. 7

  • Method

    The authors introduce SOVI, which attains the rate using observed rewards and transitions and separates initial action selection from continuation-value estimation.

    Source: §1 · p. 3, §8 · p. 28

  • Results

    SOVI has a high-probability regret upper bound of order eO(T^max{eA,eB}), and every algorithm has worst-case expected regret Ω(T^max{eA,eB}) when Br > 0 and u > ∥1Z∥Hk.

    Source: §3 · p. 7

  • Takeaways & Limitations

    The matching bounds determine the optimal dependence on T for Sobolev kernel-based RL, partially addressing Vakili (2024); the upper-bound prefactor is polynomial in d, H, u, Br, and Λ up to logarithmic factors.

    Source: §8 · p. 28

    The analysis is for Sobolev RKHSs, and constructing and using SOVI's partitions and ε-nets can incur substantial computational costs.

    Source: §8 · p. 28

Abstract

from arXiv · show

We study the minimax regret rate for episodic kernel-based reinforcement learning, where the expected reward and transition density belong to a Sobolev reproducing kernel Hilbert space, with continuous state and action spaces, and adversarial initial states. For Sobolev smoothness parameter $\nu>0$, state dimension $d_S$, and action dimension $d_A$, we prove that the minimax expected regret over $T$ episodes is $\widetilde\Theta(T^{\max\{e_A,e_B\}})$, where $e_A=\frac{\nu+d_A}{2\nu+d_A}$, $e_B=\frac{\nu+d_A+3d_S/2}{2\nu+d_A+2d_S}$ with the other model parameters fixed. The two exponents reflect the distinct difficulties of action selection and learning across states. We introduce Sobolev Optimal Value Iteration (SOVI), which attains this rate from observed rewards and transitions. For fixed smoothness and reference-kernel lengthscale, its regret bound has a prefactor polynomial in the state-action dimension $d=d_S+d_A$, horizon $H$, transition and reward RKHS norm bounds $u,B_r$, and kernel norm-comparison factor $\Lambda$, up to logarithmic factors. The algorithm separates initial action selection from continuation-value estimation and combines local polynomial approximation with the shared RKHS structure of the approximation errors. Our matching upper and lower bounds determine the optimal dependence on the number of episodes for Sobolev kernel-based reinforcement learning. Thus, we partially address the open problem in Vakili(2024) under the condition of the Sobolev kernel setup.

1 Introduction

The introduction asks for the optimal regret growth in kernel-based reinforcement learning, where action choice and learning across states create distinct challenges. It presents a minimax characterization for Sobolev-kernel RL and introduces SOVI to attain the rate.

1 Introduction

  • The setting has unknown transition densities and expected rewards in Sobolev RKHSs over continuous state and action spaces.The reward and transition functions have RKHS norm bounds, and the state and action dimensions are denoted dS and dA.Source: §1 · p. 2
  • The open question is whether kernel-based transitions permit no-regret learning and what the optimal episode and horizon dependence is, with action selection distinct from learning across states.The introduction narrows the question to Sobolev kernels, which include the Matérn setting.Source: §1 · p. 2
  • The paper proves a minimax expected-regret characterization for Sobolev-kernel RL and states that it disproves the conjectured kernel-RL order.The cited result considers nonanticipating algorithms that know the model-class parameters and admissible initial-state adversaries.Source: §1 · pp. 2–3
  • SOVI attains the rate with unknown rewards, continuous actions, and adaptively chosen initial states by jointly estimating reward and continuation contributions through Bellman regression.Its dependence on the horizon H is polynomial.Source: §1 · p. 3

2 Related Works

Prior kernel and smooth-MDP analyses use differing assumptions and yield regret guarantees that do not settle the Sobolev RKHS minimax rate. The paper gives matching bounds for that setting and explains why the kernel-bandit benchmark does not transfer unchanged.

Kernel-Based RL

  • Earlier kernel-based approaches address data-dependent value-function targets with covering arguments or tighter confidence intervals, but the cited guarantees have limitations including non-sublinear rates or an optimistic closure assumption.The earlier order-optimality claim of Vakili and Olkhovskaya (2023) is described as relying on an invalid local covering step.Source: §2 · p. 3
  • Other kernel-RL guarantees rely on mean-dynamics or product-RKHS transition assumptions, while related work also studies average reward, GP-generated environments, preferences, or sample complexity rather than cumulative online regret.This paper addresses the Sobolev case of the open problem posed by Vakili (2024).Source: §2 · p. 3

Smooth MDPs

  • Maran et al. (2024a) give a sublinear regret bound for all Matérn kernels, but it does not match the bandit lower-bound benchmark; the Sobolev RKHS bounds match.The paper attributes the sharper result to norm constraints and bounded state-occupancy densities.Source: §2 · p. 3

Kernel Bandits and the Minimax Benchmark

  • For dS ≥ 1 and H ≥ 2, the matching upper and lower bounds have exponent max(eA, eB), smaller than the full-domain kernel-bandit benchmark exponent.The learner chooses actions while subsequent states have bounded densities, so the bandit lower bound cannot be transferred unchanged.Source: §2 · p. 4

3 Sobolev Kernel-Based Reinforcement Learning

The section defines episodic Sobolev-kernel MDPs with unknown rewards and transitions, then establishes matching minimax regret bounds. The rate reflects separate action-selection and state-learning difficulties.

Model and assumptions

  • The model uses continuous state and action spaces, unknown expected rewards and transition densities, and a known RKHS model class with bounded reward and transition norms.The learner observes rewards and next states through episodic interaction, while an adversary may choose initial states adaptively.Source: §3 · pp. 4, 5, 7
  • The Sobolev smoothness condition applies jointly to state-action variables, and the model includes Matérn kernel-based reinforcement learning as a special case.The transition-density RKHS constraint also bounds later-step state occupancy densities by u.Source: §3 · pp. 6, 7, 9

Main result

  • For fixed model parameters, minimax expected regret is Θ̃(T^max{e_A,e_B}), with e_A=(ν+d_A)/(2ν+d_A) and e_B=(ν+d_A+3d_S/2)/(2ν+d_A+2d_S).SOVI attains the upper bound, and every algorithm meets the matching lower bound when B_r>0 and u>∥1_Z∥_Hk.Source: §3 · p. 7
  • When d_A>2ν, e_A dominates and the exponent is independent of d_S; when d_A<2ν, e_B dominates and depends on both dimensions.At d_A=2ν, the exponents coincide at 3/4.Source: §3 · p. 7
  • Action selection and continuation-value learning have different state effects: small action regions may contain an optimum, while state-region errors are weighted by visitation probability.After the first step, the probability of visiting a state region E is at most uµ(E).Source: §3 · p. 7

4 SOVI: Sobolev Optimal Value Iteration Overview

SOVI learns from observed rewards and transitions by retaining candidate action-value functions and choosing actions using a continuation candidate. Its local polynomial features approximate Bellman backups while retaining the remaining kernel-feature component.

4 SOVI: Sobolev Optimal Value Iteration Overview

  • SOVI retains candidate action-value functions consistent with past observations, selects an initial action and continuation candidate, then follows that candidate’s greedy policy.It separates initial-action selection loss from value-function estimation loss.Source: §4 · p. 9

4.1 Candidate Action-Value Functions and the Decision Objective

  • The decision objective evaluates the first-step reward and transition under the true model, using a candidate function to evaluate continuation; the Bellman response is estimated from observations.Candidate continuation values are induced by action-value candidates, with zero included in the class.Source: §4.1 · p. 10

4.2 Value Function Approximation via Local Legendre Polynomials

  • Local low-degree Legendre polynomials represent local Bellman-backup variation, while a kernel feature map retains the approximation remainder, keeping regression coefficients polynomial in d for fixed ν.Regressing the full observed response estimates both reward and continuation contributions.Source: §4.2 · p. 10

5 SOVI: Version Space Construction

The version-space construction uses a fixed partition and two tests on candidate Bellman residuals. The tests retain the optimal candidate with high probability while shrinking the candidate set over episodes.

5 SOVI: Version Space Construction

  • The first test keeps cumulative residual vectors within regression confidence bounds, controlling the difference between Bellman residuals and their feature-based terms.The second test examines the remaining term through observable residuals.Source: §5 · p. 14
  • A second test uses weighted observable residual innovations to detect systematic deviations too large to be explained by bounded regression error and mean-zero observation noise.Its weights are constructed from correlated Gaussian sequences using the regression features.Source: §5 · p. 15
  • With probability at least 1−δ/4, the optimal candidate remains in every episode’s version space, and these spaces are nested and nonincreasing.Candidates that fail constraints are rejected, and historical constraints prevent them from re-entering.Source: §5 · pp. 14, 17

6 SOVI: First Action and Value Function Selection

This section describes how SOVI selects a first action and continuation candidate using first-step Bellman backups estimated from observed rewards and transitions. It also covers how local polynomial regression, kernel-remainder models, and exploration support those choices, and how first-step feedback updates model weights and carries the selected continuation through the episode.

6.1 State and Action Partition

  • Restricting the first action to the finite grid incurs at most T^-1 approximation loss over T episodes, while later greedy policies still optimize over the continuous action space.Counting partitions track initial-state visits for level selection, while regression partitions pool nearby states for local fits.Source: §6.1 · pp. 19–20

6.2 G-optimal Design Policy

  • G-optimal designs on action blocks collect comparison data while controlling polynomial prediction variance within each block.The exploration policy chooses a block uniformly and then samples an action from that block’s G-optimal design.Source: §6.2 · pp. 20–21

6.3 Level Selection and Epoch Initialization

  • Each episode selects a state-dependent level using the current counting cell’s visit threshold; visits at each level are grouped into doubling-capacity epochs that reset regression and model weights.Epoch initialization fixes a finite net of kernel-remainder models; a shared coefficient represents the remainder across state-action inputs and continuation values.Source: §6.3 · pp. 21–22

6.4 Scoring and Selecting Action-Candidate Pairs

  • One fixed remainder model provides an optimistic approximation throughout each level-epoch, while candidate scores combine model predictions with local polynomial estimates.The estimates use past rewards and transitions, with the same regression design matrix shared across candidate value functions.Source: §6.4 · pp. 23–24
  • With probability 1−γ, SOVI executes the recommended first action; otherwise it samples from the G-optimal exploration policy, then follows π_f from step two.The marginal first-action distribution depends on current model weights and the exploration policy.Source: §6.4 · p. 24

6.5 Feedback and Model-Weight Updates

  • Because feedback is observed only at the executed action, local action polynomials estimate Bellman backups for models’ recommended pairs using coefficients prepared before sampling.The convex optimization reproduces action polynomials on each block, controls approximation error and single-observation contribution, and minimizes a second-moment bound; the optimization is feasible.Source: §6.5 · pp. 24–25
  • The multiplicative weight update favors models with smaller estimated losses and uses a second-moment correction to cushion down-weighting when loss estimates have larger second-moment bounds.The estimated normalized loss and its conditional second-moment bound determine the update.Source: §6.5 · p. 25
  • After selecting and executing the first action, SOVI follows the selected continuation policy for stages 2 through H and stores the completed trajectory for future version-space tests.The same candidate continuation is kept throughout the episode.Source: §6.5 · p. 25

7 Theoretical Guarantee

The section establishes a high-probability regret bound for SOVI and a matching minimax exponent in the number of episodes. The lower bound has separate action- and state-related terms, and the resulting rate is minimax optimal up to logarithmic factors.

Upper-bound dependence

  • For fixed smoothness and reference-kernel inverse lengthscale κ, the upper-bound prefactor is polynomial in d, H, u, Br, and Λ, up to logarithmic factors.For a normalized Matérn kernel, Λ = 1; for a general Sobolev kernel, the bound retains its dependence on Λ.Source: §7 · p. 27

Upper bound

  • The theorem states a high-probability regret upper bound for SOVI under the specified model and admissible initial-state adversary.Its confidence level is at least 1 − δ.Source: §7 · p. 27

Minimax lower bound

  • The minimax lower bound is at least max{cA T^eA, ⌊H/2⌋cB T^eB}, and therefore at least min{cA, ⌊H/2⌋cB} T^max{eA,eB}.The constants are independent of H and T; the bound also holds with deterministic rewards.Source: §7 · p. 27

Matching rate

  • SOVI is minimax optimal in T up to logarithmic factors.The section combines the upper- and lower-bound results to establish the matching episode-growth exponent.Source: §7 · pp. 27–28

8 Discussion

The discussion presents matching upper and lower bounds for the minimax regret rate in episodes and describes SOVI’s design. It identifies computational costs and several open directions for improving the analysis and algorithm.

Discussion

  • Matching upper and lower bounds determine the minimax regret rate in episodes for Sobolev kernel-based reinforcement learning.The result partially addresses the open problem in Vakili (2024).Source: §8 · p. 28
  • SOVI separates initial action selection from continuation-value estimation and combines local polynomial approximation with shared RKHS structure of approximation errors.For fixed smoothness and reference-kernel lengthscale, its upper-bound prefactor is polynomial in d, H, u, Br, and Λ, up to logarithmic factors.Source: §8 · p. 28
  • Open directions include reducing polynomial dependence, extending analysis beyond Sobolev RKHSs, sharpening joint lower bounds, and improving computational efficiency.Constructing and using SOVI’s partitions and ε-nets can incur substantial computational costs; the paper calls for an efficient algorithm retaining the optimal regret rate in T and performing well empirically.Source: §8 · p. 28

A Mathematical Tools

The appendix collects analytic, measurability, concentration, and information-theoretic tools used in the proofs. It also establishes Sobolev-kernel norm comparisons and compactness properties needed for approximation and optimization.

Sobolev and RKHS properties

  • For τ > n/2, the stated spectral comparison identifies the kernel RKHS with Hτ(Rn), and restriction preserves the norm comparison.Restriction to a subset cannot increase the RKHS norm.Source: A Mathematical Tools · pp. 28–29

Compactness and regularity

  • On compact domains, Sobolev-kernel RKHS balls have uniformly bounded, Hölder-continuous representatives and are compact in the uniform norm.These properties support compact candidate classes for the lower bound.Source: A Mathematical Tools · pp. 29–30

Measurable optimization

  • Borel selection results ensure measurable maximizers for continuous objectives over compact feasible sets.The passage applies these results to greedy actions and history-dependent candidate sets.Source: A Mathematical Tools · p. 30

Concentration and information-theoretic tools

  • Gaussian entropy and metric comparison control widths used in remainder tests and finite-model approximation.The appendix also invokes regression concentration, maximal inequalities, G-optimal design, and change-of-measure bounds.Source: A Mathematical Tools · pp. 30–31

B Proofs in Section 3

These proofs establish measurability and boundedness of value functions, show that transition expectations and Bellman updates remain in the RKHS, and verify optimality against history-dependent policies. They also bound state occupancy using the transition-density assumption.

Value-function regularity

  • Optimal value and Q-functions are measurable and bounded, with Q^h taking values in [0, H−h+1].Continuity in the action and compactness of the action space yield measurable maximizing selectors.Source: B Proofs in Section 3 · p. 32

Optimality and regret

  • The deterministic Markov policy formed by measurable greedy selectors attains the optimal value, and regret is bounded between 0 and HT.The proof compares it with history-dependent policies.Source: B Proofs in Section 3 · p. 32

Measurability and feedback

  • The transition-density expectation is measurable, and the conditional-expectation argument allows dependence between the current reward and next state.The passage states that the argument also permits history-dependent policies.Source: B Proofs in Section 3 · pp. 32–33

RKHS bounds

  • For bounded V, the transition expectation P^hV belongs to the RKHS with norm at most u∥V∥∞, while the Bellman update has norm at most B_r + u∥V∥∞.At the final stage, the Bellman update is the reward function and has norm at most B_r.Source: B Proofs in Section 3 · p. 33

Occupancy bound

  • The state distribution after the first step has density at most u, so the probability of any measurable state set E is at most uµ(E).The occupancy bound applies to history-dependent policies.Source: B Proofs in Section 3 · p. 33

C Proofs in Sections 4-6

The proof setup defines the information available before observing rewards and next states, then bounds the conditional expected algorithmic target.

Algorithmic lemmas

  • Before observing reward and next state, sample assignments are measurable with respect to the information available after choosing the action.For each fixed V, the conditional expectation of Y^h is at most H−h+1; at h = H, V = 0.Source: C Proofs in Sections 4-6 · p. 34

C.1 Proofs for Section 4

These proofs establish approximation, complexity, noise, and regression bounds used in the analyses, including feasibility of the true candidate across episodes. They control second moments through feasible coefficients and polynomial reproduction, with epoch-wise regression inequalities holding uniformly over the stated queries and continuations.

C.1 Proofs for Section 4

  • The local polynomial construction approximates the kernel feature uniformly with error at most C_ν min{1, t^ν}, while the Legendre projection preserves this approximation up to a dimension-dependent factor.The argument transfers a polynomial approximation through the feature-space isometry and bounds the projection operator uniformly over cells.Source: §C.1 · pp. 34–35
  • The RKHS ball has a uniform covering-entropy bound, and the continuation-value classes inherit the bound used to establish (4.9).The covering bound is log N(ε, G_B, ||·||∞) ≤ C_{ν,κ}d^2(B/ε)^p log^2(C_{ν,κ}dB/ε), where p = 2d/(2ν + d).Source: §C.1 · p. 36

C.2 Proofs for Section 5

  • A quadratic exponential test controls weighted continuation noise uniformly, and Q* passes both tests with probability at least 1 − δ/4, leaving the feasible sets nested across episodes.The noise bound allows predictable weights and dependence between reward and next state.Source: §C.2 · pp. 37–39

C.3 Proofs for Section 6

  • For each level and epoch, the regression argument yields inequalities at every visit, uniformly over continuations and grid-action queries.It combines the local regression confidence bound with a fixed net approximation to an element representing the true model.Source: §C.3 · p. 40
  • The construction partitions each block into removed and remaining sets and assigns measures and matrices to the sets, including blocks with zero recommendation mass.Source: §C.3 · p. 41
  • Feasible coefficients have small average second moments under the recommendation distribution, and compactness plus minimization transfers their pointwise bound to the optimizer.The proof states that the feasible set is compact on the positive-mass support and the minimizer’s objective is no larger than the constructed coefficients’ objective.Source: §C.3 · p. 41
  • A polynomial approximation with residual at most epsilon on finite U, together with the observation law and reproduction constraint, yields the stated second-moment bound.Source: §C.3 · p. 42

D Proof of Theorem 7.1

The proof separates SOVI’s first-action selection error from its continuation error, then combines their bounds to establish the theorem. Local action approximation, regression uncertainty, and remainder-model comparison supply the main components.

D Proof of Theorem 7.1

  • SOVI’s proof separately controls first-action and continuation-policy errors before combining the two propositions.The argument intersects the events for Propositions D.1 and D.2, then uses Bellman optimality and telescoping continuation values.Source: D Proof of Theorem 7.1 · pp. 42, 45
  • The action-approximation analysis uses local polynomials whose degree and rank depend on the action-dimension regime.For the mixed-scale partition, the degree is k′ − 1 and the local rank is at most [C ln(eT)]^dA.Source: D Proof of Theorem 7.1 · p. 43
  • A shared approximation-error envelope controls all action blocks without summing its squared norm across blocks.The conversion argument’s approximation cost depends on polynomial rank within a block rather than the total number of action blocks.Source: D Proof of Theorem 7.1 · pp. 43–44
  • The regression remainder is compared through a fixed net, with only the logarithm of its size entering model-comparison cost.The net is fixed independently of observations, and one fixed remainder model serves as the comparator within an epoch.Source: D Proof of Theorem 7.1 · p. 43
  • The first-step regret contribution combines confidence-width, remainder-model comparison, and action-approximation costs.Occupied regression cells control confidence widths, while the remainder cover controls model comparison and action approximation controls feedback bias.Source: D Proof of Theorem 7.1 · p. 44
  • Continuation-error conversion handles data-dependent candidates and errors using historical occupancies of the selected policies.The cumulative continuation bound is applied to SOVI’s selected candidates using the action-approximation ranks and errors.Source: D Proof of Theorem 7.1 · pp. 44–45

E Proofs of Lemmas in Appendix D

The appendix proves technical bounds used to analyze the algorithm and establish the regret bound. These include results on partition counts, approximation, covering and concentration, as well as uniform change-of-measure and matrix bounds for combining approximation regimes, with dimension dependence.

Proof of Lemma D.1

  • The partition proof bounds visits to each counting cell by its capacity and controls how many current regression cells can meet saturated preceding-level cells.It also bounds the number of levels and the action partition size.Source: E Proofs of Lemmas in Appendix D · p. 46

Proof of Lemma D.2

  • The approximation proof bounds high-frequency state error using fixed reward and transition coefficients, then controls the action-low-frequency error with Taylor approximation.The fixed-coefficient condition is needed for the cellwise squared-envelope bound; summing the approximation terms yields the stated dimension bound.Source: E Proofs of Lemmas in Appendix D · pp. 47–48

Proof of Lemma D.3

  • The remainder-feature proof bounds feature width and covering entropy, then uses Gaussian-width and internal-net arguments to obtain the covering bound.The expected absolute supremum is bounded in terms of the feature-width scale and dimension, and the projected centers form an internal net.Source: E Proofs of Lemmas in Appendix D · p. 49

Proof of Lemma D.4

  • The epoch-comparison proof establishes positive update multipliers and a prefix-wise bound without requiring an extra fallback case.Its concentration argument does not assume independence between models’ loss estimates, which use the same observation.Source: E Proofs of Lemmas in Appendix D · pp. 50–51

Proof of Lemma D.5

  • Lemma D.5’s change-of-measure bounds hold simultaneously for every posterior, including one chosen after observing the history, and its combined events fail with probability at most δ/2.The proof avoids treating the retrospectively chosen candidate as predictable.Source: E Proofs of Lemmas in Appendix D · pp. 53–54

Proof of Lemma D.6

  • The D.6 matrix argument controls changing candidates without multiplying their approximation error by L, charging cumulative error through action blocks, bins, and slack.It uses whitened local polynomial bases and unnormalized subdensities; summing the bin bounds and charged slack proves (D.7).Source: E Proofs of Lemmas in Appendix D · pp. 54–55

Proof of Proposition D.2

  • The final dimension accounting bounds local-construction factors by powers of 2 + d and retains at most quadratic logarithmic and model factors.The listed dimension-dependent quantities are bounded by Cν or Cν,κ times the stated powers of 2 + d.Source: E Proofs of Lemmas in Appendix D · pp. 55–56
  • The Proposition D.2 proof obtains the target T^e* time exponent across approximation regimes, balancing or interpolating the resulting bounds as needed.In one regime the coarse, balanced-tail, and approximation terms share an exponent; in another, interpolation gives eA = e*.Source: E Proofs of Lemmas in Appendix D · p. 56

F Proof of Theorem 7.2

The proof constructs lower bounds from localized transition perturbations and testing arguments. Action perturbations yield T^eA regret, while perturbations spread across state cubes yield T^eB regret and can be repeated across odd stages.

F Proof of Theorem 7.2

  • A single transition perturbation at a fixed initial state supports a testing lower bound for action selection.The one-action-cell bound applies when all initial states equal the fixed state s◦, subject to its width, height, and testing constraints.Source: F Proof of Theorem 7.2 · pp. 57–58
  • T^eA regret follows from action-localized testing, while state-cube perturbations give T^eB regret and uniform resets repeat that construction at ⌊H/2⌋ stages.The randomized initial states can be replaced by a deterministic sequence with at least the same average regret.Source: F Proof of Theorem 7.2 · pp. 57, 59
  • The transition perturbations define valid probability densities in [1/2, 3/2] when the perturbation has supremum norm at most 1/4.Under the stated RKHS norm constraint, each transition-density section also satisfies the transition norm bound.Source: F Proof of Theorem 7.2 · p. 57
  • State-cube perturbations require smaller height because the RKHS norm grows with the square root of the number of cubes.Uniform initial states and resets make the learner face the cubes and repeat the testing problem at every odd stage.Source: F Proof of Theorem 7.2 · p. 58

G Proofs of Lemmas in Appendix F

The appendix develops lower-bound comparisons and admissible bump constructions, while Corollary G.1 shows minimax regret is asymptotically smaller than the full-domain kernel-bandit benchmark.

Proof of Lemma F.2

  • At s°, actions outside U° lose at least ε/2 against the optimal perturbation value ε, yielding expected regret at least (cε/4)(T − E_U n°(U)).The bound uses the count of visits to the action region U°.Source: G Proofs of Lemmas in Appendix F · p. 59
  • Only the first transition differs in the compared models; identical rewards and decision rules leave the likelihood comparison valid for randomized, history-dependent decisions.The transition likelihood ratio is constant on S+ and S−, giving a Bernoulli divergence.Source: G Proofs of Lemmas in Appendix F · p. 59

Proofs of Lemmas F.1 and F.3

Proof of Lemma F.3

  • Each lower-bound comparison changes one stage, so its information bound uses T observations rather than HT, while regret adds across all R informative stages.This separates the information cost of a comparison from the accumulated regret contribution.Source: G Proofs of Lemmas in Appendix F · p. 61

Corollary G.1 (Comparison with the full-domain kernel-bandit exponent)

  • The minimax expected regret divided by T^((ν+d)/(2ν+d)) tends to zero under Theorem 7.2’s assumptions.The comparison follows from the matching upper and lower bounds and a positive exponent gap.Source: G Proofs of Lemmas in Appendix F · p. 61

Related papers

Loading 2610.34045v1…