Information-Theoretic Regret Bounds

Regret scales with the number of true surprises your model class allows. Count those independent probes and you can predict learning cost without counting states.

Two probes x1 and x2 pin down a 2D class at tolerance 0.2 while x3 adds nothing, so eluder dimension is 2 and regret follows its root

Why Does This Exist?

Counting states stops working the moment you generalize. A gridworld bound that grows with state count says nothing about pixels, joints, or text, where states are effectively endless. Once one function approximator shares strength across states, as in value function approximation, the question changes. What number now sets exploration cost.

Parameter count misleads. A giant net that smooths cleanly can be easy to explore, while a tiny jagged class can hide surprises everywhere. The linear case is settled in linear methods. Feature dimension $d$ rules, because $d$ clean probes fix every direction. This page lifts that idea to general classes with eluder dimension for prediction and Bellman rank for multi step control.

Two basics first. Regret is tuition paid while learning. In multi-armed bandits with best mean $\mu^*$ and picks $a_t$ :

\mathrm{Regret}(T) = \sum_{t=1}^{T}(\mu^* - \mu_{a_t})

In RL the same sum tracks $V^* - V^{\pi_t}$ over episodes. Sublinear regret means average mistakes fade. That tradeoff against probing is the exploration versus exploitation dilemma. For the tabular view of the same sum, see regret bounds.

Think of It Like This

The mineral surveyor

A mining firm owns wide land and a geologist with a map of likely ore. Each drill costs money and reveals one spot.

Some sites need no drill. If every nearby hole in the same rock came up empty, she calls it empty by geology. Other sites split her map. Two underground pictures both fit all past holes yet disagree here. Those split sites are the only drills worth paying for. Eluder dimension is the worst case count of such split drills before the map holds everywhere. Bellman rank asks the same question one step ahead, checking whether today plus physics predicts tomorrow.

Where the analogy stops: real ore correlates by distance, while here dependence is algebraic at your tolerance. And the surveyor keeps the same ground while drilling, while an RL agent steers into new ground with every early move.

How It Actually Works

Optimistic methods act by the best world still consistent with data, so they pay big regret only when the world surprises them. Eluder dimension counts how many such surprises a class permits.

Fix class $\mathcal{F}$ from inputs $x$ to values and tolerance $\epsilon > 0$ . Point $x_t$ is $\epsilon$ independent of past $x_1, \dots, x_{t-1}$ when two members $f, f'$ match the past yet split now:

\sum_{i \lt t}(f(x_i) - f'(x_i))^2 \le \epsilon^2 \quad \text{but} \quad |f(x_t) - f'(x_t)| \gt \epsilon

Symbols: $f$ and $f'$ are candidate models, $\epsilon$ is the survey tolerance you ignore. Eluder dimension $\dim_E(\mathcal{F}, \epsilon)$ is the longest run where every point is independent of all before it. General regret then looks like $\sqrt{\dim_E \cdot T \cdot \log N}$ , with $N$ for class size. Replace $\dim_E$ with $d$ and you recover linear $d\sqrt{T}$ style bounds.

Bellman rank handles horizon $H$ and shifting data. Write $\mathcal{E}_h(f, \pi')$ for average Bellman error of $f$ at step $h$ under roll in $\pi'$ . Rank $M$ means those errors factor through $M$ directions:

\mathcal{E}_h(f, \pi') \approx \langle \phi_h(\pi'), \psi_h(f) \rangle

Methods in the OLIVE family probe those $M$ directions, with sample cost polynomial in $M$ and $H$ instead of state count.

Worked toy

Take $\mathcal{F} = \{x \mapsto \theta^T x\}$ with $\theta$ in $\mathbb{R}^2$ , so $d = 2$ . Tolerance $\epsilon = 0.2$ . Probes $x_1 = (1,0)$ , $x_2 = (0,1)$ , $x_3 = (0.6,0.8)$ .

First $x_1$ surprises against empty past. Zero versus $\theta = (1,0)$ differ by $1.00 \gt 0.2$ .

Next $x_2$ surprises given $\{x_1\}$ . Zero versus $\theta = (0,1)$ match at $x_1$ with gap $0 \le 0.04$ , yet split by $1.00 \gt 0.2$ at $x_2$ .

Now $x_3$ is pinned. For $d = \theta - \theta'$ , past match means $d_1^2 + d_2^2 \le 0.04$ . Gap at $x_3$ is $0.6 \cdot d_1 + 0.8 \cdot d_2$ , capped by Cauchy Schwarz:

|0.6 d_1 + 0.8 d_2| \le \sqrt{0.36 + 0.64} \cdot 0.2 = 0.20

never strictly above $\epsilon$ . Equality sits at $d = (0.12, 0.16)$ with past $0.0144 + 0.0256 = 0.0400$ and gap $0.072 + 0.128 = 0.200$ . Longest surprising run is 2, so $\dim_E = 2 = d$ . That equality is what the diagram draws.

Code

This snippet checks the pinning claim from the toy.

1"""Verify x3 is pinned at eps 0.2 for the 2D toy."""2
3import math4
5eps = 0.26x3 = (0.6, 0.8)7norm = math.sqrt(x3[0] ** 2 + x3[1] ** 2)8bound = norm * eps9d = (eps * x3[0] / norm, eps * x3[1] / norm)10past = d[0] ** 2 + d[1] ** 211gap = x3[0] * d[0] + x3[1] * d[1]12
13print(round(bound, 4))14# -> 0.215print((round(d[0], 2), round(d[1], 2)))16# -> (0.12, 0.16)17print(round(past, 4), round(gap, 4))18# -> 0.04 0.219print(gap > eps + 1e-9)20# -> False

Watch Out For

Reading parameter count as exploration cost

A ten million weight net on clean images can have small eluder dimension, while a three knob spiky class can hide endless surprises. The symptom is budgeting probes or bonus scale from weight count and then over exploring smooth models or under exploring jagged ones.

Count surprising directions at your tolerance instead. Ask how many queries could still split the survivors, not how many knobs the model has.

Treating low rank as cheap compute

Bellman rank bounds samples for an ideal explorer, not optimizer work. Realizing methods search version spaces that are intractable for rich classes. The symptom is quoting a polynomial sample bound as if wall clock training will be fast.

Budget planning and optimization apart from statistics. A task can be information light and compute brutal at once.

The Quick Version

Eluder dimension is the longest run of queries that can each surprise you given the past.
Optimistic regret concentrates on those steps, growing near $\sqrt{\dim_E T}$ .
The 2D toy at $\epsilon = 0.2$ gives dimension 2, with $x_3$ capped at gap $0.20$ .
Bellman rank ports the count to multi step errors, with cost polynomial in rank and horizon.
Neither number prices optimization, so small statistical cost can still mean hard training.