Action subsampling supports policy compression in large action spaces

Textbook decision experiments hand you two or three options and ask you to choose. Real life does not. Standing in a hardware store, planning a sentence, picking a move — the hard part is often that the set of things you could do is enormous and nobody has written it down. A mind with finite resources cannot score every possible action against every possible context. So it does two things at once: it considers only a handful of actions, and it maps situations to those actions only as sharply as it can afford. This paper is about how those two economies interact. With a stopwatch and a bandit task, it shows that people run both knobs at once, and close to optimally.

1. Blurring the map and shrinking the menu

Fix a task: states $s$ arriving with frequency $P(s)$, actions $a$, and a reward $Q(s,a)$ for taking $a$ in $s$. An unbounded agent maps each state to its best action and collects the most reward possible. A bounded agent cannot, and there are two different ways it can cut costs.

The first is to blur the map. Instead of a precise, state-specific policy, use one that partly ignores the state. In the limit, one habit for everything. The cost of a policy in this sense is exactly how much it tells you about the state, the mutual information between states and the actions they produce:

called the policy complexity. A deterministic map is expensive; a state-blind habit is free. This is the rate–distortion picture of action selection developed in this lab’s earlier work (the subject of lecture 02, policy compression as an information bottleneck): under a capacity limit $I^\pi(S;A) \le C$, the reward-maximizing policy takes a fixed form,

where $P^*(a)=\sum_s P(s)\,\pi^*(a\mid s)$ is the marginal action frequency and $\beta$ rises with the capacity $C$. That second term is what a plain softmax lacks: it biases the optimal compressed policy toward actions that are generally frequent, a built-in perseveration that dominates when $\beta$ is small. Sweeping $\beta$ and solving for $\pi^*$ (the Blahut–Arimoto algorithm) traces a reward–complexity frontier: the most reward attainable at each level of policy complexity.

The second way to cut costs is the one this paper adds. Before you even build a policy, shrink the menu: consider only a subset of the actions — an action consideration set of size $N_a$ — and solve the rate–distortion problem over just those. Prior work treated this as a separate story (people are known to generate only a few options before choosing), but here it slots directly into the same machinery: drop the excluded actions’ columns from $Q$, re-run Blahut–Arimoto, and read off a lower frontier. The gap between that frontier and the full-action one is the price of a narrow menu.

2. A task where both knobs matter

To watch this happen you need a task with a real menu of actions, a reason to shrink it, and a known reward structure so the frontier can actually be computed. The authors use a contextual bandit. Six images (states); seven keys (actions). Each image has exactly one correct key worth $+1$; press a wrong number and you lose $-0.18$. One key is a safety key that pays a flat $+0.2$ no matter the image. Miss the response deadline and you get $-1$.

The safety key’s value averaged over states — its general value $V(a)=\sum_s P(s)\,Q(s,a)$ — is $0.2$, while any single number key averages just $(1 - 5\times0.18)/6 \approx 0.017$. So a maximally compressed, zero-complexity policy — one action for everything — should be “always press safety,” banking $0.2$. To earn more you must let the state back into your policy: remember which number goes with which image, and accept a more complex, slower policy to execute it.

Play a block. Learn the mapping with feedback, then take the timed test and watch which keys you actually reach for when the clock is short.

The manipulation is the response deadline: 0.5 s, 1 s, or 2 s. Nothing about the reward structure changes between blocks, only the time you have to deploy your policy. If policy complexity carries a time cost (it does, in earlier work), then squeezing the deadline should squeeze the policy: fewer distinct keys, more reliance on safety, lower complexity, lower reward. The task turns an abstract capacity limit into a wall-clock one you can feel.

3. What people did

Seventy-five participants, three timed blocks of 96 trials each. The behavior tracks the framework closely. Under longer deadlines people ran more complex policies (mixed-effects slope $0.762 \pm 0.078$, $t(223)=9.78$, $p<10^{-18}$), earned more reward ($0.249 \pm 0.027$, $p<10^{-17}$), leaned on the safety key less ($-0.309 \pm 0.033$, $p<10^{-17}$), and considered more distinct actions ($N_a$ slope $1.30 \pm 0.16$, $p<10^{-13}$). And complexity paid for itself in time: higher-complexity policies came with reliably longer response times ($0.273 \pm 0.010$, $t(223)=26.3$, $p<10^{-69}$).

The load-bearing result is the interaction between the two knobs. More actions considered did more than add reward on their own: they amplified the reward return on policy complexity (interaction $0.0205 \pm 0.003$, $p<10^{-10}$) and blunted the suboptimality that complexity otherwise incurs (interaction on reward-loss $0.0571 \pm 0.003$, $p<10^{-40}$). And the two rose together across people: policy complexity and $N_a$ correlated at $R=0.671$ ($p<10^{-30}$). Participants were not told to do any of this. Under time pressure they spontaneously simplified the task, considering fewer actions and mapping them more crudely, and relaxed that simplification when the clock allowed.

4. The frontier, and where people sit on it

Because the task’s reward structure is fully known, the frontier here is computable, not a metaphor. The widget below is the actual output of the reproduction’s Blahut–Arimoto engine on this task. The black curve is the full-action frontier; drop to a consideration set of $N_a$ actions and the reachable frontier falls below it. Slide policy complexity to move along a curve; the red segment is the suboptimality gap you would pay at that point.

Two consequences follow, both visible in the human data. First, a bigger consideration set raises the ceiling: with $N_a$ actions you can reach at most $\log_2 N_a$ bits, so more actions are a precondition for a more rewarding policy. Second, a bigger consideration set flattens the gap: each extra bit of complexity is spent more efficiently when more actions are on the table. Together they explain why complexity and $N_a$ have to climb together: raising one without the other leaves reward on the table, which is exactly the positive correlation the participants show. The human means (the colored dots, one per deadline) sit below the full frontier, in the region the framework attributes to finite consideration sets, and march up-and-right as the deadline loosens.

5. Which actions are worth considering?

The frontier tells you the cost of a small menu but not which actions belong on it. Enumerating every subset is hopeless in a large space, so the agent needs a heuristic — a proposal distribution $P_0(a)$ to sample the consideration set from. The paper weighs three:

• Flat — $P_0(a)=\text{const}$, sample actions uniformly.
• General value — $P_0(a)\propto V(a)$, favor actions that are good on average across states. This is the empirically documented human tendency: people generate options that are generally good, then check them against the current context.
• Oracle — $P_0(a)=P^*(a)$, sample from the optimal marginal itself. It needs the answer, so it is a benchmark, not a strategy.

The question is normative: when is the general-value heuristic actually a good idea? The simulation below runs it on a large action space (16 states, 32 actions). Sample $N_a$ actions from each proposal, keep the best policy over them, and plot how far below the full frontier you land.

The heuristic earns its keep precisely in the regime humans occupy: low policy complexity and small consideration sets. There, sampling by general value lands much closer to the frontier than flat sampling, because at low complexity the optimal policy wants the single highest-general-value action anyway — so a proposal biased toward high general value is likely to contain it. Push either knob up — more complexity, more actions — and the edge fades, as state-specific value decouples from general value. That turns a descriptive quirk (“people over-sample generally-good options”) into a conditional-optimality claim with sharp boundaries.

The boundaries cut the other way too. Swap the downstream algorithm from Blahut–Arimoto to self-normalized importance sampling (SNIS), which corrects the proposal’s bias to approximate the full-space policy without distortion,

and the general-value advantage vanishes. By construction SNIS discounts frequently-sampled actions, cancelling the very bias that made general-value sampling helpful. SNIS has the better asymptotic guarantee (it is unbiased; Blahut–Arimoto is not), yet it is the worse model of adaptive behavior in the small-sample regime people live in. A guarantee about the infinite-data limit is not a reason to expect a mechanism in a finite mind.

6. Cracks and alternatives

7. Where this sits

The paper is the hinge of this lab’s policy-compression cluster. It sits directly on lecture 02 (policy compression: an information bottleneck in action selection), which established the rate–distortion frontier and the perseveration signature for small, fully-known action spaces; the contribution here is to make the framework survive contact with large action spaces by letting the agent solve the same problem over a sampled subset. It is the natural sibling of lecture 04 (action chunking as conditional policy compression): chunking and subsampling are two different moves for making a policy cheaper — compose actions into macros versus prune the menu down — and comparing where each bends the frontier is an obvious synthesis.

It also rhymes with lecture 01 (strategy reuse / SF&GPI), where the mind carried a small library of previously-good policies and re-scored them instead of recomputing from scratch. Here the reusable, amortized object is a proposal distribution — a general-value prior over actions, learned once and applied across tasks — rather than a policy library, but the bargain is the same one the whole study circles: keep a small, reusable structure and pay a little suboptimality, instead of solving each problem in full. The wider lineage the paper draws on is explicit in its own text: rate–distortion theory of cognition (Sims), resource-rational analysis (Lieder & Griffiths), the option-generation literature (Morris, Phillips, Cushman), and sampling-as-cognition (importance sampling for concept learning, reinforcement learning, and parsing).

On the accuracy–compute frontier that organizes this course, the paper stakes out a specific, measurable point: a mind that is doubly bounded — coarse in its state-to-action map and narrow in the actions it will even entertain — and that manages both bounds well enough to stay near optimal in a task it has quietly made smaller. The next question, which the reproduction’s extension spec takes up, is whether a learned proposal can keep that bargain as action spaces grow from tens to billions.