Ahmed Haroon

Reward Does Not Reveal What We Have Not Tried

A reinforcement-learning agent maximizes

J(\pi) =\mathbb E_{\tau\sim\pi} \left[ \sum_{t=0}^{\infty}\gamma^t r_t \right],

but it learns an action's consequences only by taking that action. Exploitation chooses the behavior currently believed to be best. Exploration chooses behavior that may improve what the agent knows.

Sparse reward makes the distinction temporal. Suppose reward requires one particular action at each of $L$ steps. Uniform random behavior succeeds with probability

\boxed{ P(\text{successful sequence}) =\left(\frac1{|\mathcal A|}\right)^L }.

If an $\epsilon$ -greedy policy must explore correctly at every step, the probability is approximately

P(\text{successful exploratory sequence}) \approx \left(\frac{\epsilon}{|\mathcal A|}\right)^L.

Independent action noise therefore becomes exponentially ineffective with the depth of the required behavior.

Shallow exploration asks which single action pays more. Deep exploration asks which coherent strategy eventually reveals reward. The second problem motivates episode-level hypotheses, intrinsic motivation, goals, and reusable skills.

Bandits Isolate the Exploration Tradeoff

A stochastic multi-armed bandit has actions $a\in\mathcal A$ with unknown reward distributions

r_t\sim R_{a_t},

and mean values

Q(a)=\mathbb E[r\mid a].

The optimal arm satisfies

a^*\in\arg\max_aQ(a), \qquad V^*=Q(a^*).

Bandits remove state transitions and delayed credit assignment while retaining uncertainty about which action is best.

After $N_t(a)$ pulls, the empirical mean is

\widehat Q_t(a) =\frac1{N_t(a)} \sum_{\tau=1}^{t} r_\tau\mathbf 1\{a_\tau=a\}.

Pure greed chooses the largest empirical mean. An unlucky early reward can make a suboptimal arm look best, after which greed gathers no evidence capable of correcting itself.

Regret prices exploration

Define the arm gap

\Delta_a=V^*-Q(a)\ge0.

Cumulative expected regret is

L_T =\mathbb E \left[ \sum_{t=1}^{T} (V^*-Q(a_t)) \right].

It decomposes into the cost of each suboptimal arm times how often it is selected:

\boxed{ L_T =\sum_{a\in\mathcal A} \Delta_a\,\mathbb E[N_T(a)] }.

See derivation

Replace instantaneous regret by the selected arm's gap:

L_T =\mathbb E\left[ \sum_{t=1}^{T}\Delta_{a_t} \right].

Group time steps by action:

\sum_{t=1}^{T}\Delta_{a_t} =\sum_{a\in\mathcal A} \Delta_a \sum_{t=1}^{T}\mathbf 1\{a_t=a\}.

The inner sum is exactly

Taking expectations gives the result.

Sublinear regret,

L_T=o(T),

implies vanishing average regret $L_T/T\to0$ . Fixed-rate exploration and permanent greed can both suffer linear regret: one wastes actions forever, while the other may never correct an early mistake.

A contextual bandit observes $s_t$ before acting and learns

Q(s,a)=\mathbb E[r\mid s,a],

but actions still do not affect future contexts. It introduces generalization without sequential credit assignment.

Simple Rules Inject Local Randomness

Under the common convention that uniform exploration may also select the greedy action,

\pi_\epsilon(a\mid s) = \begin{cases} 1-\epsilon+\dfrac{\epsilon}{|\mathcal A|}, &a\in\arg\max_{a'}Q(s,a'),\\[6pt] \dfrac{\epsilon}{|\mathcal A|},&\text{otherwise}. \end{cases}

GLIE schedules become greedy in the limit while preserving infinite exploration:

N_t(s,a)\to\infty, \qquad \pi_t(a\mid s) \to \mathbf 1\{a\in\arg\max_{a'}Q_t(s,a')\}.

This requires $\epsilon_t\to0$ slowly enough that exploration does not disappear after finitely many trials.

Boltzmann exploration distinguishes among alternatives by value:

\pi_\tau(a\mid s) =\frac{e^{Q(s,a)/\tau}} {\sum_{a'}e^{Q(s,a')/\tau}}.

As $\tau\to0$ , it becomes greedy; as $\tau\to\infty$ , it approaches uniform. Value magnitude is not calibrated uncertainty, however. A confidently poor estimate and an uncertain estimate can receive the same probability.

Optimistic initialization instead starts with

Q_0(s,a)\approx\frac{R_{\max}}{1-\gamma}.

Greedy action selection tries unvisited actions because their estimates remain high. The optimism is transient, can generalize incorrectly under function approximation, and still does not sustain a coherent multi-step hypothesis.

All three methods perturb individual actions. They are useful baselines, but deep exploration needs uncertainty that persists across time.

Optimism Turns Uncertainty into Value

Upper confidence bounds assign each arm an optimistic score

U_t(a)=\widehat Q_t(a)+b_t(a),

then select

a_t\in\arg\max_a U_t(a).

If an optimistic arm is good, it produces reward. If it is poor, sampling shrinks its uncertainty until its score falls.

Assume rewards are $\sigma$ -sub-Gaussian. For $n$ independent samples with mean $\mu$ ,

P(\mu-\widehat\mu_n\ge\varepsilon) \le \exp\left(-\frac{n\varepsilon^2}{2\sigma^2}\right).

Solving for a failure probability $\delta$ gives the one-sided confidence radius

\boxed{ b(n,\delta) =\sqrt{ \frac{2\sigma^2\log(1/\delta)}{n} } }.

See derivation

Set the tail bound equal to $\delta$ :

\exp\left(-\frac{n\varepsilon^2}{2\sigma^2}\right) =\delta.

Taking logarithms and rearranging,

\varepsilon^2 =\frac{2\sigma^2\log(1/\delta)}{n}.

Since a radius is nonnegative,

\varepsilon =\sqrt{ \frac{2\sigma^2\log(1/\delta)}{n} }.

For unit-sub-Gaussian rewards, a horizon-aware UCB rule is

\boxed{ a_t\in\arg\max_a \left[ \widehat Q_t(a) +\sqrt{\frac{2\log T}{N_t(a)}} \right] }.

The bonus decays as $N_t(a)^{-1/2}$ . A suboptimal arm remains plausible until

\sqrt{\frac{\log T}{N_T(a)}} \lesssim\Delta_a,

N_T(a) \gtrsim\frac{\log T}{\Delta_a^2}.

Each pull costs $\Delta_a$ , suggesting regret

L_T =O\left( \sum_{a:\Delta_a>0} \frac{\log T}{\Delta_a} \right).

Uncertainty is not an inconvenience added to value—it becomes a temporary source of value that disappears when evidence resolves it.

Thompson Sampling Commits to a Plausible World

Bayesian exploration places a posterior over unknown reward or dynamics parameters:

p(\theta\mid\mathcal D) \propto p(\mathcal D\mid\theta)p(\theta).

Thompson sampling draws one plausible model and acts optimally in it:

\widetilde\theta_t\sim p(\theta\mid h_t), \qquad a_t\in\arg\max_aQ_{\widetilde\theta_t}(a).

Beta–Bernoulli updates

For binary rewards,

r\mid\theta\sim\operatorname{Bernoulli}(\theta), \qquad \theta\sim\operatorname{Beta}(\alpha,\beta).

After $S$ successes and $F$ failures,

\boxed{ \theta\mid\mathcal D \sim \operatorname{Beta}(\alpha+S,\beta+F) }.

See derivation

Ignoring normalization constants,

\begin{aligned} p(\theta\mid\mathcal D) &\propto \theta^S(1-\theta)^F \theta^{\alpha-1}(1-\theta)^{\beta-1}\\ &= \theta^{\alpha+S-1} (1-\theta)^{\beta+F-1}. \end{aligned}

This is the kernel of a $\operatorname{Beta}(\alpha+S,\beta+F)$ density.

For each arm, sample

\widetilde\theta_a \sim\operatorname{Beta}(\alpha_a,\beta_a),

select $\arg\max_a\widetilde\theta_a$ , and update only the chosen arm. Exploration decays automatically as poor arms become unlikely under the posterior.

Thompson sampling implements probability matching:

\boxed{ \pi_{\mathrm{TS}}(a\mid h_t) =P\left( a=\arg\max_{a'}Q_\theta(a') \;\middle|\;h_t \right) }.

See derivation

The selected action is a deterministic function of a posterior sample:

\pi_{\mathrm{TS}}(a\mid h_t) =\mathbb E_{\theta\sim p(\theta\mid h_t)} \left[ \mathbf 1\left{ a=\arg\max_{a'}Q_\theta(a') \right} \right].

The expectation of an indicator is the probability of its event, giving the posterior probability that $a$ is optimal.

In an MDP, posterior sampling can draw an entire environment

(\widetilde P,\widetilde R) \sim p(P,R\mid h_k),

plan in it, and follow its optimal policy for a full episode. Posterior Sampling for Reinforcement Learning therefore maintains one coherent hypothesis across many steps:

a_t\in\arg\max_aQ^*_{\widetilde P,\widetilde R}(s_t,a).

If the sampled world suggests that a distant corridor is valuable, the policy commits long enough to test that hypothesis. This is deep exploration rather than independently resampled action noise.

\textbf{Posterior Sampling for Reinforcement Learning}

\begin{aligned} &\text{Maintain }p(P,R\mid h_k).\\[0.25em] &\text{At the beginning of episode }k:\\[0.25em] &\qquad (\widetilde P_k,\widetilde R_k) \sim p(P,R\mid h_k),\\[0.25em] &\qquad \pi_k\leftarrow \operatorname{PLAN}(\widetilde P_k,\widetilde R_k),\\[0.25em] &\qquad \text{follow }\pi_k\text{ for the whole episode},\\[0.25em] &\qquad \text{update the posterior with the new trajectory}. \end{aligned}

Exact posterior inference and repeated planning are usually expensive. Bootstrapped Q-heads, Bayesian last layers, and sampled ensembles approximate the same persistent-hypothesis idea in deep RL.

Exploration Bonuses in Large State Spaces

Bandit optimism becomes an augmented reward in an MDP:

\boxed{ r^+(s,a) =r(s,a)+r_{\mathrm{int}}(s,a) }.

A tabular bonus may use

r_{\mathrm{int}}(s,a) \propto\frac1{\sqrt{N(s,a)}}

or a faster-decaying $1/N(s,a)$ . The optimistic Q update is

Q(s,a)\leftarrow Q(s,a)+\alpha \left[ r+r_{\mathrm{int}}(s,a) +\gamma\max_{a'}Q(s',a') -Q(s,a) \right].

Exact counts fail for pixels and continuous states because almost every observation is unique. Novelty must generalize across similar observations.

Density-model pseudo-counts

Let a density model assign probability

\rho=p_\theta(s)

before learning from $s$ , and

\rho'=p_{\theta'}(s)

afterward. Define imaginary tabular quantities by

\rho=\frac{\widehat N(s)}{\widehat n}, \qquad \rho'=\frac{\widehat N(s)+1}{\widehat n+1}.

Solving gives

\boxed{ \widehat N(s) =\frac{\rho(1-\rho')}{\rho'-\rho} }.

See derivation

From $\rho=\widehat N/\widehat n$ ,

\widehat N=\widehat n\rho.

Substitute into the post-update probability:

\rho' =\frac{\widehat n\rho+1}{\widehat n+1}.

Rearranging,

\widehat n =\frac{1-\rho'}{\rho'-\rho}.

Multiplying by $\rho$ yields

\widehat N(s) =\frac{\rho(1-\rho')}{\rho'-\rho}.

A large probability increase means the observation taught the model a lot, producing a small pseudo-count and a large novelty bonus. If the model barely changes, the state behaves as familiar.

Prediction-error novelty

Random Network Distillation fixes a random target $f_\xi$ and trains a predictor $\widehat f_\phi$ :

\boxed{ r_{\mathrm{int}}(s) =\|\widehat f_\phi(s)-f_\xi(s)\|_2^2 }.

Visited observations become easy to predict, while unfamiliar observations retain error. A forward model can similarly reward

\|f_\phi(s,a)-s'\|_2^2.

Prediction error is only an uncertainty proxy:

\text{error} =\text{epistemic uncertainty} +\text{aleatoric noise} +\text{misspecification} +\text{optimization error}.

An agent rewarded for error may stare forever at an inherently unpredictable screen—the noisy-TV problem. Learning progress and posterior information gain better target reducible uncertainty.

Generalization Changes What a Count Means

With function approximation, one observation changes predictions at many state-action pairs. Uncertainty depends on coverage in representation space, not literal repetition.

Consider a linear contextual model

r_t=\theta^\top x_t+\eta_t, \qquad x_t=\phi(s_t,a_t).

Ridge regression gives

\widehat\theta_t=A_t^{-1}b_t,

where

A_t=\lambda I+\sum_{i=1}^{t-1}x_ix_i^\top, \qquad b_t=\sum_{i=1}^{t-1}x_ir_i.

If the parameter lies in the confidence ellipsoid

\|\theta-\widehat\theta_t\|_{A_t}\le\beta_t,

then an optimistic reward estimate is

\boxed{ U_t(s,a) =\widehat\theta_t^\top\phi(s,a) +\beta_t \sqrt{ \phi(s,a)^\top A_t^{-1}\phi(s,a) } }.

See derivation

Let $x=\phi(s,a)$ . Then

\theta^\top x =\widehat\theta_t^\top x +(\theta-\widehat\theta_t)^\top x.

By Cauchy–Schwarz in the $A_t$ geometry,

(\theta-\widehat\theta_t)^\top x \le \|\theta-\widehat\theta_t\|_{A_t} \|x\|_{A_t^{-1}}.

Apply the confidence bound:

\theta^\top x \le \widehat\theta_t^\top x +\beta_t\sqrt{x^\top A_t^{-1}x}.

The bonus is large in feature directions poorly covered by previous data. It is the geometric analogue of $1/\sqrt{N(a)}$ .

Deep representations make this geometry nonstationary and their uncertainty harder to calibrate. Ensembles and bootstrapped heads provide useful approximations, but they do not inherit tabular guarantees automatically.

Curiosity Values Information

State-marginal entropy measures breadth of visitation:

\mathcal H(d_\pi) =-\mathbb E_{s\sim d_\pi} [\log d_\pi(s)].

Maximizing it encourages coverage, although not every reachable state is equally relevant.

Intrinsic rewards differ in what they call interesting:

\begin{aligned} \text{rarity:}&\quad r_{\mathrm{int}}(s)\propto1/\sqrt{N(s)},\\ \text{surprise:}&\quad r_{\mathrm{int}}(s)=-\log p_\phi(s),\\ \text{prediction error:}&\quad r_{\mathrm{int}}=\|f_\phi(s,a)-s'\|^2,\\ \text{learning progress:}&\quad r_{\mathrm{int}}=\ell_{\mathrm{before}}-\ell_{\mathrm{after}}. \end{aligned}

Information gain directly measures how much an observation changes beliefs about an uncertain model parameter $\Theta$ :

\boxed{ \operatorname{IG}(x) =D_{\mathrm{KL}} \left( p(\theta\mid\mathcal D,x) \,\|\, p(\theta\mid\mathcal D) \right) }.

Before observing the outcome, the expected information gain of an action is

\mathbb E_{x\sim p(x\mid a,\mathcal D)} \left[ D_{\mathrm{KL}} \left( p(\theta\mid\mathcal D,x) \,\|\, p(\theta\mid\mathcal D) \right) \right].

This equals conditional mutual information:

\boxed{ \mathbb E_x[\operatorname{IG}(x)] =I(\Theta;X\mid\mathcal D) }.

Curiosity should reward observations that reduce epistemic uncertainty, not outcomes that remain surprising because of irreducible aleatoric noise.

Choosing an Exploration Strategy

The right mechanism depends on both uncertainty and temporal depth.

Use $\epsilon$ -greedy or Boltzmann sampling as cheap local baselines.
Use UCB when calibrated confidence sets or meaningful counts are available.
Use Thompson sampling when a posterior can represent coupled uncertainty and a sampled hypothesis can persist.
Use pseudo-counts or RND when state spaces are large and novelty must generalize.
Use information gain or learning progress when stochastic distractions make raw prediction error unreliable.

Exploration always depends on representation. A count, posterior, or density model declares two observations similar according to its features. Bad features turn principled formulas into misleading bonuses.

The progression is

\boxed{ \text{random actions} \longrightarrow \text{uncertainty-aware actions} \longrightarrow \text{coherent hypotheses} \longrightarrow \text{information-seeking behavior} }.

When useful behavior must persist beyond a single decision, exploration can be lifted into temporally extended goals and skills. That is the subject of skill learning.

Exploration is therefore not synonymous with randomness. Useful exploration selects behavior whose outcomes can change what the agent knows.