Bandit Algorithms

This module implements a small set of classic discrete-action bandit algorithms:

• greedy / epsilon-greedy action selection,
• UCB1-style confidence bonuses,
• incremental sample-average value estimation,
• gradient bandits with a softmax policy over preferences.

Primary references:

• Sutton and Barto, Reinforcement Learning: An Introduction (2nd ed., bandit chapter): http://incompleteideas.net/book/the-book-2nd.html
• Auer, Cesa-Bianchi, and Fischer, "Finite-time Analysis of the Multiarmed Bandit Problem" (2002): https://doi.org/10.1023/A:1013689704352
• Williams, "Simple Statistical Gradient-Following Algorithms for Connectionist Reinforcement Learning" (1992): https://doi.org/10.1023/A:1022672621406

structure Runtime.RL.Bandits.ValueState (α : Type) [TorchLean.Storage α] (nActions : ℕ) : Type

Value-estimation state for finite-armed bandits.

• counts : TorchLean.Tensor α [nActions]

  Per-action pull counts.

• values : TorchLean.Tensor α [nActions]

  Per-action estimated values.

structure Runtime.RL.Bandits.PreferenceState (α : Type) [TorchLean.Storage α] (nActions : ℕ) : Type

Preference / policy-gradient state for gradient bandits.

• steps : α

  Number of observed rewards so far (tracked as the ambient scalar type).

• preferences : TorchLean.Tensor α [nActions]

  Preference logits over actions.

• averageReward : α

  Running average reward baseline.

def Runtime.RL.Bandits.ValueState.init {α : Type} [TorchLean.Storage α] [Context α] {nActions : ℕ} : ValueState α nActions

Zero-initialized action-value state.

def Runtime.RL.Bandits.PreferenceState.init {α : Type} [TorchLean.Storage α] [Context α] {nActions : ℕ} : PreferenceState α nActions

Zero-initialized preference state.

def Runtime.RL.Bandits.ValueState.greedy? {α : Type} [TorchLean.Storage α] [Context α] {nActions : ℕ} (state : ValueState α nActions) : Option (Fin nActions)

Greedy action under the current estimates, if the action space is nonempty.

def Runtime.RL.Bandits.ValueState.epsilonGreedy? {α : Type} [TorchLean.Storage α] [Context α] {nActions : ℕ} (state : ValueState α nActions) (epsilon draw : α) (exploreAction : Fin nActions) : Option (Fin nActions)

Epsilon-greedy action selection with explicit exploration draw and fallback action.

The caller supplies:

• epsilon: exploration probability,
• draw: a pre-sampled uniform value in [0,1),
• exploreAction: the action to use when the exploration branch is taken.

def Runtime.RL.Bandits.ValueState.update {α : Type} [TorchLean.Storage α] [Context α] {nActions : ℕ} (state : ValueState α nActions) (action : Fin nActions) (reward : α) : ValueState α nActions

Incremental sample-average update for one bandit arm.

def Runtime.RL.Bandits.ValueState.pulls {α : Type} [TorchLean.Storage α] [Context α] {nActions : ℕ} (state : ValueState α nActions) : α

Total number of pulls recorded in a ValueState.

def Runtime.RL.Bandits.ucbBonus {α : Type} [Context α] (exploration totalPulls actionPulls : α) : α

UCB1-style exploration bonus.

The denominator is clamped at Context.defaultEpsilon, without a special infinity rule for unseen arms. exploration controls the multiplier. Counts and the scalar epsilon are used as supplied.

def Runtime.RL.Bandits.ValueState.ucbScores {α : Type} [TorchLean.Storage α] [Context α] {nActions : ℕ} (state : ValueState α nActions) (exploration : α := 2) : TorchLean.Tensor α [nActions]

Per-action UCB1 scores.

def Runtime.RL.Bandits.ValueState.ucb? {α : Type} [TorchLean.Storage α] [Context α] {nActions : ℕ} (state : ValueState α nActions) (exploration : α := 2) : Option (Fin nActions)

Best action under UCB1 scores, if the action space is nonempty.

def Runtime.RL.Bandits.PreferenceState.policy {α : Type} [TorchLean.Storage α] [Context α] {nActions : ℕ} (state : PreferenceState α nActions) : TorchLean.Tensor α [nActions]

Softmax policy used by the gradient-bandit algorithm.

def Runtime.RL.Bandits.PreferenceState.update {α : Type} [TorchLean.Storage α] [Context α] {nActions : ℕ} (state : PreferenceState α nActions) (action : Fin nActions) (reward stepSize : α) (baseline : Bool := true) : PreferenceState α nActions

Gradient-bandit preference update with an optional average-reward baseline.