advanced33 min studyLesson 697 in Engineering

Exploration spends a defined reward budget to learn about eligible alternatives

Specify action probabilities, contextual reward assumptions, cold-start priors, and the comparator behind regret instead of promising universal benefit from random recommendations.

On this page

What you’ll understand

  • Compute epsilon-greedy action probabilities for a fixed eligible set.
  • Calculate immediate expected reward and pseudo-regret under known stationary means.
  • Distinguish learning coverage from validated user utility and long-horizon policy performance.

A new item or sparse-history user may have little feedback because the existing policy rarely exposes suitable alternatives. Purely exploiting the current estimate can preserve that gap indefinitely. Exploration deliberately gives some eligible actions a chance to collect information, but the randomization has costs and a precise scope. It does not make every new item good, identify outcomes for excluded actions, or automatically improve long-term satisfaction. The policy, reward, eligible action set, and comparison horizon must be stated together.

Write down the actual action distribution

In a simple epsilon-greedy policy, choose a specified greedy action most of the time and choose uniformly from the eligible set during exploration. The greedy action also receives its share of the uniform branch. Ties need a documented rule. If availability filters change, the probability denominator changes for that context; logging one global epsilon value is therefore insufficient to reconstruct every action's propensity. A slate policy has additional combinatorial and interaction choices, so an item-level epsilon rule should not be presented as a complete slate randomization contract.

Cold start can use item content, context, population priors, or carefully designed initial exposure while uncertainty remains high. Absence of clicks on an unshown item is not a known negative. Priors can improve early estimates but can also transfer misleading population averages to a new cohort. Preserve eligibility and the declared outcome requirements during exploration, then evaluate how quickly useful information arrives and how costly the exploration was. Exploration over an allowed set gives no support for an action that the system always filters out.

πϵ(a∣x)=(1−ϵ)1{a=a∗(x)}+ϵ∣A(x)∣(a∈A(x))\pi_\epsilon(a\mid x)=(1-\epsilon)\mathbf1\{a=a^*(x)\}+\frac{\epsilon}{|\mathcal A(x)|}\quad(a\in\mathcal A(x))
The eligible finite set A(x) is nonempty, a* is one specified greedy action with a tie rule, and epsilon lies in [0,1]. Probabilities are dimensionless. This is a one-action policy; dynamic availability, slate selection, or nonuniform exploration requires its actual conditional probabilities.↔ Scroll wide equations horizontally.

Regret depends on the reward and comparator

A common bandit quantity compares expected reward with an oracle that knows the best eligible action's mean for the same context. Summing those mean gaps gives expected pseudo-regret under a stated environment. This is not the same as comparing realized clicks with a lucky sequence of random rewards. A stationary finite-action example can illustrate the arithmetic, while real contexts and preferences can drift. Claims about sublinear regret need the particular algorithm and assumptions that prove them, not the mere presence of random exploration.

Choosing clicks as reward defines a click-maximization problem. It does not establish that higher click reward improves satisfaction, learning, or long-term user benefit. Delayed rewards, repeated recommendations, inventory effects, and interactions between users or items can violate a simple contextual-bandit abstraction. Evaluate the actual policy horizon and relevant outcomes instead of treating a short-term regret calculation as a universal product guarantee. Off-policy comparison also inherits support and logging assumptions; exploration can help collect supported evidence without eliminating every causal or measurement problem.

RT=∑t=1TE[μ∗(xt)−μ(at,xt)],μ∗(x)=max⁡a∈A(x)μ(a,x)R_T=\sum_{t=1}^{T}\mathbb E\left[\mu^*(x_t)-\mu(a_t,x_t)\right],\qquad \mu^*(x)=\max_{a\in\mathcal A(x)}\mu(a,x)
mu is the declared expected one-step reward under a specified environment, and the comparator shares the same eligible context. R_T has reward units and expectation includes policy randomness and any modeled contexts. This defines expected pseudo-regret, not a bound, observed causal effect, or guarantee for nonstationary long-term recommendation utility.↔ Scroll wide equations horizontally.

Monitor learning and immediate outcomes separately

Track exposure probability, unique explored items, reward delay, uncertainty, and quality by cold-start cohort. Log the actual chosen probability and policy version so future evaluation can reconstruct the action mechanism. Revisit priors and exploration allocation as feedback arrives, but record changes rather than pooling them as one fixed policy. Compare short-run cost with later learning benefit under a designed experiment. A popular-item average can hide poor experience for new users or creators, while a high diversity count alone says nothing about whether explored recommendations were useful.

The probability lab can display a fixed rare-action count. Reset, set both p=0.04 and n=25, predict mean one and variance 0.96, then Play or Step. Reset and set both p=0.04 and n=30 for mean 1.2 and variance 1.152. The bars are exact binomial masses under independent fixed-probability choices; playback highlights outcomes rather than generating samples. The trial slider stops at thirty. It has no contexts, adaptive estimates, rewards, regret, or slate constraints, so it cannot establish a learning guarantee for the exploration policy.

Calculate the immediate cost of a specified exploration rule

Five eligible actions have stationary mean rewards 0.5 for one known-best action and 0.3 for each other action. Use epsilon-greedy with ε=0.2 and uniform exploration over all five. For this calculation, keep the greedy action and reward means fixed rather than modeling learning.

  1. The greedy action probability is0.8+0.2/5=0.84. Each other action has probability 0.04; the five probabilities sum to0.84+4×0.04=1.

  2. Uniform-branch mean reward is(0.5+4×0.3)/5=0.34. Policy mean reward is0.8×0.5+0.2×0.34=0.468, equivalently 0.84×0.5+0.16×0.3.

  3. The one-step expected gap from the known-best comparator is0.5−0.468=0.032. Over 1000 identical decisions without learning or drift, cumulative expected pseudo-regret is32 reward units; this does not quantify any later learning benefit.

The result

The immediate exploration cost is explicit under the toy assumptions. A real adaptive policy needs evidence about how its information gain, changing choices, and meaningful outcomes evolve.

Explore the model

Interactive lab

Interactive lab · probability

A fixed rare-action count does not model adaptive exploration

Reset, set both p=0.04 and n=25, predict mean 1 and variance 0.96, then Play or Step. Reset and re-enter both p=0.04 and n=30 for mean 1.2 and variance 1.152. Exact binomial bars assume independent fixed-probability choices; playback highlights possible outcomes, not samples. n caps at30, and the model contains no contexts, reward updates, learned policy, or regret.

A fixed rare-action count does not model adaptive explorationThese are exact binomial probabilities for independent trials with one fixed success probability. Playback tours the distribution; it does not resample outcomes. Current readings: Mean · np: 5; Variance · np(1−p): 2.5; Total probability: 1. All parameters are adjustable with the labeled controls below.03581000.070.150.220.3Successes kP(X = k)k = 0 · P = 9.77e-4
Exact probabilityHighlighted outcomeMean np
Mean · np
5
Variance · np(1−p)
2.5
Total probability
1
t = 0 s

These are exact binomial probabilities for independent trials with one fixed success probability. Playback tours the distribution; it does not resample outcomes. Parameter changes pause playback and recompute the model at the current elapsed time. Reset restores both parameters and returns time to zero. Playback starts paused. Adjust either parameter, then choose Play or Step.

Look forA logged action probability describes the selection mechanism; learning quality requires a separate policy evaluation.

Check your understanding

Under epsilon-greedy with ε=0.2 and five eligible actions, what is the probability of the single greedy action?

Try it yourself

Four eligible actions use ε=0.1 with one specified greedy action. Their stationary reward means are 0.6 for the greedy action and 0.2 for each other action. Compute action probabilities, expected reward, and one-step expected pseudo-regret against the known best.

Take a moment to make a prediction or work it out on paper. Open a hint when you need one.

Give me a hint

The greedy probability includes its uniform share; compare the policy mean with 0.6.

Compare with the solution

The greedy action has probability 0.9+0.1/4=0.925; each other action has 0.025. Expected reward is0.925×0.6+3×0.025×0.2=0.57. The expected gap is0.6−0.57=0.03 reward units per decision under these fixed means and choices. This arithmetic is not a long-run guarantee for an adaptive or changing environment.

Take it with you

  • Exploration probabilities are conditional on eligibility, tie handling, and the actual action unit.
  • A regret statement needs a reward, environment, comparator, and horizon.
  • Evaluate immediate cost, learned information, and meaningful user outcomes separately.

Read further

Original sources and deeper explanations to follow at your own pace.

Optional progress, saved in this browser when available. Revisit any lesson at any time.

Lesson not marked complete.