Policies
Turning a table of action values into a policy — greedy, ε-greedy, Boltzmann and UCB — plus one-hot encoding, entropy and the softmax score.
Prelude.Policies chooses actions. It takes a table of action values q of shape S×A (one row per state, one column per action) and returns a policy: a row-stochastic matrix of the same shape whose row \(s\) is the probability of each action in state \(s\). A multi-armed bandit is simply a one-state problem, so every definition works on a 1×A table exactly as it does on S×A.
Exploration is arithmetic rather than a branch. ε-greedy is a weighted sum of the greedy and uniform policies, so the fact that the exploring branch may also pick the greedy action — making its true probability \(1 - \varepsilon + \varepsilon/A\) rather than \(1 - \varepsilon\) — falls out of the algebra. Greedy is a mask: when several actions tie for the maximum, they share the probability equally rather than one being picked arbitrarily.
Learners in this family receive state and action numbers; marked turns a batch of numbers into one-hot rows against the table’s own axes, which is how the definitions in Temporal read and write a table. The sample models QTable.hb, Bandit.hb and Thompson.hb (in the Hilbert sample project) use this module inside model … : Learner declarations.
Notation. \(Q \in \mathbb{R}^{S \times A}\) has entries \(Q_{sa}\); state and action numbers are positions counted from zero. \([\,\cdot\,]\) is the Iverson bracket (1 if true, 0 otherwise), and \(\operatorname{safe}(d) = d + [\,d = 0\,]\) is the guarded divisor from Linear algebra.
open Prelude.Policies
A table’s axes and one-hot encoding
stateIds
stateIds(q) · q table matrix S×A → state numbers vector S
Let \(Q \in \mathbb{R}^{S \times A}\) (the argument q) be a table. Then
The state indices, taken from the table’s own shape.
Intuition The numbers \(0..S-1\) read off the rows of the table itself, so the axis can never disagree with the table’s width. It is the ruler that marked compares a batch of state numbers against.
Use it when you turn state numbers into one-hot rows with marked(stateIds(q), s) before reading or writing a row of the table. Never type the axis as a literal: if the table grows, a literal silently mis-encodes. For the action axis use actionIds.
table-indexingone-hot-encoding
def stateIds(q) ≔ positions(einsum("sa->s", ones(q)))
actionIds
actionIds(q) · q table matrix S×A → action numbers vector A
Let \(Q \in \mathbb{R}^{S \times A}\) (the argument q) be a table. Then
The action indices.
Intuition The same ruler as stateIds, laid along the columns: the numbers \(0..A-1\) taken from the table’s width.
Use it when you encode the actions of a batch as one-hot rows, marked(actionIds(q), a), to pick out \(Q(s, a)\) for a TD update or to build the one-hot ha that scoreOf expects. It also gives A without counting by hand.
table-indexingone-hot-encoding
def actionIds(q) ≔ positions(einsum("sa->a", ones(q)))
marked
marked(ids, v) · ids the axis, from stateIds or actionIds vector K · v a batch of indices vector n → one-hot rows matrix n×K
Let \(\iota \in \mathbb{R}^K\) (the argument ids) be an axis, normally \(\iota_k = k\) for \(k = 0, \dots, K-1\), and let \(v \in \mathbb{R}^n\) be a batch of indices. Then, for \(i = 1, \dots, n\) and \(k = 0, \dots, K-1\),
so with the table’s own axis row \(i\) is the basis vector \(e_{v_i}\). Pass the axis from the table (marked(stateIds(q), s)) so the width always matches.
Intuition A lookup written as arithmetic: compare every index in the batch with every position on the axis and keep the matches. Row \(i\) then has a single 1 in column \(v_i\), so multiplying by the table selects a row (or cell), and an outer product with it scatters an update back.
Use it when a learner receives states or actions as numbers and must read or update a table without loops or branches — the tabular learners in Temporal do exactly this. An index outside the axis gives a row of zeros, not an error, so it silently does nothing.
one-hot-encodingtable-indexingbatched-updates
def marked(ids, v) ≔ einsum("i,k->ik", v, ones(ids)) = einsum("i,k->ik", ones(v), ids)
Policies as row-stochastic matrices
shared
shared(m) · m non-negative weights matrix n×A → policy matrix n×A
Let \(M \in [0, \infty)^{n \times A}\) (the argument m) be a matrix of weights, and let \(\sigma_i = \sum_{b} M_{ib}\) be its row sums. Then
Normalises each row to sum to one. A row of all zeros stays zero rather than dividing by zero.
Intuition Each row is a pile of non-negative “votes” for the actions, and dividing by the row total turns votes into probabilities. Every policy on this page is some weighting passed through this one step.
Use it when you have scores that are already non-negative — counts, masks, likelihoods, preference weights — and need a distribution per row. Watch the zero row: it stays all zeros, which is not a valid policy, so make sure every row has some weight. For real-valued scores that can be negative use boltzmann, which exponentiates first.
probability-normalisationaction-selection
def shared(m) ≔ m / lifted(m, safe(einsum("ij->i", m)))
greedyOf
greedyOf(q) · q action values matrix S×A → greedy policy matrix S×A
Let \(Q \in \mathbb{R}^{S \times A}\) (the argument q) be the action values. Then
The greedy policy: all probability on the action(s) with the highest value in each row, split equally among ties.
Intuition “Do what currently looks best.” The argmax is a mask of every best action rather than one index, so a tie is a fair coin between the winners instead of a hidden bias toward the lowest-numbered action.
Use it when you evaluate or deploy a learned table, extract the policy that Q-learning’s max already assumes, or act on UCB-adjusted values (greedyOf(confident(q, c, counts))). Do not train with it alone: it never tries an action that looks worse, so early estimate errors become permanent. Use exploring or boltzmann while learning.
action-selectioncontrolpolicy-evaluation
def greedyOf(q) ≔ shared(highest(q))
uniformOf
uniformOf(q) · q any table matrix S×A → uniform policy matrix S×A
Let \(Q \in \mathbb{R}^{S \times A}\) (the argument q) be any table. Then
The uniform random policy.
Intuition Total ignorance: every action equally likely, whatever the values say. Its entropy is the maximum, \(\ln A\).
Use it when you need a baseline to beat, a behaviour policy that gathers unbiased data for off-policy learning, a warm-up phase before values mean anything, or the exploring half of exploring. The table is only read for its shape, so any table of the right size works.
explorationbaseline-comparisonoff-policy-learning
def uniformOf(q) ≔ shared(ones(q))
exploring
exploring(q, eps) · q action values matrix S×A · eps exploration rate ε scalar → ε-greedy policy matrix S×A
Let \(Q \in \mathbb{R}^{S \times A}\) (the argument q) be the action values and \(\varepsilon \in [0, 1]\) (the argument eps) the exploration rate. Then
The ε-greedy policy, a mixture of the greedy and uniform policies.
Intuition Mostly exploit, occasionally roll a die: with probability \(\varepsilon\) ignore the values and pick at random. Writing it as a blend of two policies keeps every action’s probability at least \(\varepsilon/A\), so nothing is ruled out forever.
Use it when you train tabular Q-learning, SARSA or a bandit and want the simplest exploration with one knob. \(\varepsilon\) between 0.05 and 0.2 is typical, often decayed over time with decayed. It explores blindly — the second-best and the worst action are equally likely — so prefer boltzmann when values are informative, or confident when you want exploration to fade where counts are high.
explorationaction-selection
def exploring(q, eps) ≔ (1 − eps) · greedyOf(q) + eps · uniformOf(q)
boltzmann
boltzmann(q, tau) · q action values matrix S×A · tau temperature τ scalar → softmax policy matrix S×A
Let \(Q \in \mathbb{R}^{S \times A}\) (the argument q) be the action values and \(\tau > 0\) (the argument tau) the temperature. Then
computed stably by subtracting each row’s maximum before exponentiating. The Boltzmann (softmax) policy. Low temperatures approach greedy; high temperatures approach uniform.
Intuition Explore in proportion to how good an action looks: a near-best action is tried often, a clearly bad one rarely. The temperature is the value difference that counts as “clearly”: actions \(\tau\) apart differ in probability by a factor \(e\).
Use it when you want graded exploration, a differentiable policy for policy gradients (pair it with scoreOf), or a soft choice model. \(\tau\) is in the units of \(Q\), so scale it to the spread of your values; it is often annealed with decayed. Very small \(\tau\) behaves like greedyOf. For exploration that ignores the values’ spread use exploring.
explorationaction-selectionpolicy-gradient
def boltzmann(q, tau) ≔ softmaxRows(q / tau)
decayed
decayed(e0, rate, k) · e0 initial value scalar · rate decay factor per step scalar · k step number scalar → value scalar
Let \(\varepsilon_0 \in \mathbb{R}\) (the argument e0) be the initial value, \(\rho > 0\) (the argument rate) the decay factor per step and \(k \in \mathbb{N}\) the step number. Then
An exponential schedule, typically for the exploration rate or temperature.
Intuition Explore a lot while you know nothing and less as estimates improve. Multiplying by the same factor each step shrinks the value by the same fraction per step; it halves every \(\ln 2 / (-\ln \rho)\) steps.
Use it when you schedule \(\varepsilon\) for exploring, \(\tau\) for boltzmann, or a learning rate. A rate like 0.995 or 0.999 per episode is common. There is no floor, so the value tends to zero; take max(decayed(e0, rate, k), eMin) if some exploration must remain. A rate above 1 grows instead of decaying.
hyperparameter-choiceexploration
def decayed(e0, rate, k) ≔ e0 · rate^k
greedyChance
greedyChance(eps, n) · eps exploration rate ε scalar · n number of actions A scalar → probability scalar
Let \(\varepsilon \in [0, 1]\) (the argument eps) be the exploration rate and \(A \ge 1\) (the argument n) the number of actions. Then
The probability that ε-greedy picks the greedy action (with a single maximum).
Intuition The random branch can also land on the best action, so the real chance of exploiting is higher than \(1 - \varepsilon\) by \(\varepsilon/A\). With few actions the difference is large: at \(A = 2\), \(\varepsilon = 0.2\) exploits 90% of the time, not 80%.
Use it when you set \(\varepsilon\) from a target exploit rate, compute importance ratios for an ε-greedy behaviour policy, or check a policy row by hand. It assumes one greedy action; with ties the greedy mass is split, so read the probabilities from exploring instead.
hyperparameter-choiceimportance-weightingexploration
def greedyChance(eps, n) ≔ 1 − eps + eps / n
Optimism in the face of uncertainty
Upper-confidence-bound (UCB) selection adds an exploration bonus to each action value,
\[q(s,a) + c\,\sqrt{\frac{\ln N_s}{n_{s,a}}},\]where \(n_{s,a}\) is how often action \(a\) was taken in state \(s\) and \(N_s\) the total for that state. An action never taken is treated as taken once, so its bonus is the largest finite one on the row: it is preferred, without dividing by zero or winning by infinity. Pass the result to greedyOf to act.
confident
confident(q, c, counts) · q action values matrix S×A · c exploration weight scalar · counts visit counts matrix S×A → optimistic values matrix S×A
Let \(Q \in \mathbb{R}^{S \times A}\) (the argument q) be the action values, \(c \ge 0\) the exploration weight and \(n \in \mathbb{N}^{S \times A}\) (the argument counts) the visit counts, with row totals \(N_s = \sum_b n_{sb}\). Then
The UCB-adjusted action values. The \(\max(N_s, 1)\) keeps the logarithm non-negative in a state never visited.
Intuition Optimism in the face of uncertainty: judge each action by the best value it could plausibly have. The bonus is a confidence width — large for rarely tried actions, shrinking as \(1/\sqrt{n}\) — while \(\ln N\) grows slowly so a neglected action is eventually revisited. Exploration is aimed, not random.
Use it when you solve multi-armed bandits or small tabular problems where counts are available, and act with greedyOf(confident(q, c, counts)). \(c = \sqrt{2}\) is the classic UCB1 value for rewards in \([0, 1]\); scale \(c\) with the reward range. In a state never visited \(N = 0\) makes every bonus zero and the greedy row splits evenly. When no counts exist, fall back to exploring or boltzmann.
explorationmulti-armed-banditsuncertainty-quantification
def confident(q, c, counts) ≔ q + bonus(c, counts)
Building blocks
pulls(counts)— Let \(n \in \mathbb{N}^{S \times A}\). Then \(\operatorname{pulls}(n)_{sa} = N_s = \sum_{b} n_{sb}\). The total count of each row, broadcast across the row.bonus(c, counts)— Let \(c \ge 0\) and \(n \in \mathbb{N}^{S \times A}\), with \(N = \operatorname{pulls}(n)\). Then \(\operatorname{bonus}(c, n)_{sa} = c\,\sqrt{\ln \max(N_{sa}, 1) \,/\, \operatorname{safe}(n_{sa})}\). The UCB exploration bonus for every cell.
Entropy and the policy score
hedging
hedging(pol) · pol policy matrix S×A → entropy of each row vector S
Let \(\pi \in [0, 1]^{S \times A}\) (the argument pol) be a row-stochastic policy. Then
The entropy of each row, in nats: 0 for a deterministic row, \(\ln A\) for a uniform one.
Intuition How undecided the policy is in each state, measured as the average surprise of its own choice. \(e^{H}\) reads as “the number of actions it is effectively choosing between”.
Use it when you add an entropy bonus to a policy-gradient loss so the policy does not collapse too early (as in A2C or PPO), monitor whether exploration is dying during training, or detect states where the agent is still unsure. Zero probabilities contribute nothing thanks to the guarded log. Compare against \(\ln A\) to normalise it.
policy-regularisationexplorationuncertainty-quantification
def hedging(pol) ≔ −einsum("ij->i", pol · ln(safe(pol)))
scoreOf
scoreOf(pol, ha) · pol policy rows for a batch matrix n×A · ha one-hot actions taken matrix n×A → score matrix n×A
Let \(\pi \in [0, 1]^{n \times A}\) (the argument pol) be the policy rows of a batch and \(H \in \{0, 1\}^{n \times A}\) (the argument ha) the one-hot actions taken. Then
The score \(\nabla \log \pi\) of a softmax policy with respect to its logits: the one-hot of the action taken minus the policy’s own probabilities. Every policy-gradient method in Objectives multiplies it by something.
Intuition The direction that makes the action just taken more likely: raise its logit and lower the others in proportion to how much the policy already favoured them. If the policy was already certain of that action the score is near zero, so there is little left to learn from it.
Use it when you compute a policy gradient for a softmax policy: multiply it by a return (REINFORCE), a TD error or an advantage from gae, then average over the batch. It is the gradient with respect to the logits, not the probabilities, and only for a softmax (boltzmann) parametrisation; for \(\tau \ne 1\) it carries an extra factor \(1/\tau\).
policy-gradientcredit-assignment
def scoreOf(pol, ha) ≔ ha − pol
Examples
The examples below live in one file, Choosing.hb, so the class is Choosing. Tables are passed as Tensor.
Greedy and ε-greedy policies, with a tie
In the first state actions 1 and 2 tie for the best value and share the greedy probability. With \(\varepsilon = 0.3\) over three actions the lone greedy action in the second state gets \(0.7 + 0.1 = 0.8\), matching greedyChance.
open Prelude.Policies
fn greedyPolicy(q) ↦ greedyOf(q)
fn epsilonPolicy(q, eps) ↦ exploring(q, eps)
fn chanceOfGreedy(eps, n) ↦ greedyChance(eps, n)
using MLambda.Hilbert.Runtime;
using Examples;
var q = (Tensor)new double[,] { { 1, 3, 3 }, { 2, 0, 1 } };
var greedy = Choosing.GreedyPolicy(q);
var exploring = Choosing.EpsilonPolicy(q, 0.3);
var chance = Choosing.ChanceOfGreedy(0.3, 3.0);
Output (verified; matrices are shown flat in row order):
greedy = shape [2, 3] values [0, 0.5, 0.5, 1, 0, 0]
exploring = shape [2, 3] values [0.1, 0.45, 0.45, 0.8, 0.1, 0.1]
greedyChance = 0.8
Softmax and UCB for a two-armed bandit
A bandit is a 1×A table. With values 1 and 2 at \(\tau = 1\) the softmax gives \(e/(e + e^2) \approx 0.269\) to the first arm. With equal values and counts of 1 and 3, UCB favours the less-tried arm: \(\sqrt{\ln 4 / 1} \approx 1.177\) against \(\sqrt{\ln 4 / 3} \approx 0.680\).
open Prelude.Policies
fn softPolicy(q, tau) ↦ boltzmann(q, tau)
fn optimistic(q, c, counts) ↦ confident(q, c, counts)
using MLambda.Hilbert.Runtime;
using Examples;
var soft = Choosing.SoftPolicy((Tensor)new double[,] { { 1, 2 } }, 1.0);
var ucb = Choosing.Optimistic((Tensor)new double[,] { { 0, 0 } }, 1.0, (Tensor)new double[,] { { 1, 3 } });
Output (verified, rounded to six digits):
boltzmann = shape [1, 2] values [0.268941, 0.731059]
confident = shape [1, 2] values [1.17741, 0.679778]
One-hot states and policy entropy
States 2 and 0 of a three-state table become one-hot rows. A 50/50 row has entropy \(\ln 2\); a deterministic row has none.
open Prelude.Policies
fn oneHotStates(q, s) ↦ marked(stateIds(q), s)
fn policyEntropy(pol) ↦ hedging(pol)
using MLambda.Hilbert.Runtime;
using Examples;
var table = (Tensor)new double[,] { { 0, 0 }, { 0, 0 }, { 0, 0 } };
var hot = Choosing.OneHotStates(table, (Tensor)new[] { 2d, 0d });
var entropy = Choosing.PolicyEntropy((Tensor)new double[,] { { 0.5, 0.5 }, { 1, 0 } });
Output (verified, rounded to six digits):
marked = shape [2, 3] values [0, 0, 1, 1, 0, 0]
hedging = [0.693147, -0]