Many control problems ask an agent to choose a joint action across many dimensions at once, such as six joint torques, each discretized into 16 levels. The number of joint actions then grows exponentially, so the agent cannot score every candidate and take the best. The usual workaround predicts each dimension, or each bit of the action index, with its own output head. That has no redundancy: one wrong head yields a wrong action, and nothing catches the mistake. This note proposes treating action selection as decoding an error-correcting code. The agent predicts the bits of the greedy action together with a small number of extra "check" outputs. These outputs are wired as a sparse bipartite constraint graph of the kind used in graph-based codes, and the action is recovered by iterative decoding on that graph. Consistent predictions reinforce each other, and isolated head errors get corrected.
The design question has a sharp answer. The ordinary choice of check is a parity check (an XOR of a few bits), and parity checks turn out to be the worst choice for this job. Flipping any single bit of the best action flips its parity. The check head must therefore separate the best action from its one-bit neighbors, which are usually nearly as good, so its decision margin is the smallest gap in the problem. Checks that are not linear can be built so that a single bit flip leaves them unchanged, for example majority or threshold functions of a few bits. Their margins then correspond to larger value gaps, so their heads make fewer mistakes under the same approximation error. The proposal turns this observation into a design rule, a decoder, and a test on discretized offline control.
Core Claim
Fix a state $s$. Let $Q^*(s,a)$ be the optimal value of joint action $a$, written as a binary string, and let $a^*$ be the best action. For any binary check function $f$ of the action bits, the head that predicts $f(a^*)$ has margin
$$m_f(s) = Q^*(s,a^*) - \max_{a:\, f(a)\neq f(a^*)} Q^*(s,a) \;\ge\; \Delta_{(k_f)}(s).$$
Here $k_f$ is the fewest bits of $a^*$ that must be flipped to change the value of $f$. The quantity $\Delta_{(k)}(s)$ is the smallest value gap among actions that differ from $a^*$ in at least $k$ bits. If the head's approximation error is below $m_f(s)/2$, it labels the greedy action correctly. A parity check always has $k_f = 1$. A majority check over three bits, evaluated where those bits agree, has $k_f = 2$.
In environments where value degrades smoothly with Hamming distance from $a^*$, non-linear checks therefore have strictly larger margins than linear ones. The claim we will test is that a sparse, high-girth graph of low-sensitivity non-linear checks gives fewer decision errors, and lower regret per error, than three alternatives with the same parameter budget. These are heads without redundancy, ensembles (which are repetition codes), and the same graph with parity checks. "High girth" means the graph has no short cycles. There is a trade-off: low-sensitivity checks carry less corrective information per check. Characterizing that trade-off as a function of how gaps are distributed is the main analytical contribution.
This gives a concrete, controllable form to the condition highlighted by Warm-Start Actor-Critic. That paper shows that policy improvement depends on critic error staying below the sub-optimality gap, but it treats critic error as an external scalar. In our setting the code determines which gap each head must resolve, so the effective margin becomes a design choice.
Relation to Prior Work
Gap-dependent theory motivates the idea and also limits what we can claim. PEDEL obtains instance-dependent speedups in linear MDPs, but it relies on exponentially large sets of candidate policies. BREA gives exponentially decaying failure probability for fixed-budget identification, but only in tabular settings. Logarithmic-regret and geometric-convergence results (Zhou et al., Khodadadian et al.) are likewise linear. We do not attempt sample-complexity guarantees for neural networks. Our claim is narrower: a per-decision statement linking head error, check margins, and decoding.
The graph-coding work supplies the method. Cooperative local repair shows that high girth keeps the subgraph induced by failures acyclic, which guarantees that leaf-peeling recovery succeeds. Generalized LDPC codes replace single parity checks with small local block codes inside a Tanner graph. We go one step further and allow those local constraints to be non-linear Boolean functions, chosen for their margin properties.
The non-linear-coding work motivates the idea from a different setting. Cadambe and Mazumdar and Agarwal and Mazumdar bound what linear locally repairable codes can achieve over small alphabets. KO codes and DeepPolar show that neural non-linear encoders beat linear ones on noisy channels. All of these concern static transmission or storage with a uniform cost per error. In our setting, errors have unequal costs set by value gaps, and that is precisely why linear structure hurts here. Expander-decoded associative memory is the closest relative in spirit, since it cleans corrupted patterns with sparse checks. It assumes, however, that the patterns lie in a linear subspace and involves no decision values.
Research Program
The agent has three parts. The first is a critic $Q_\theta(s,a)$ that takes the joint action as input, trained with standard offline machinery. The second is a set of $n$ bit heads and $m$ check heads sharing a state encoder. The third is a decoder.
Each head is trained as a binary classifier toward the label of the critic's greedy action. Its target is the sign of the difference between the best critic value among sampled candidates on each side of that head's partition. The candidates come from dataset actions, the current decoded action, and its Hamming neighbors. This training uses only the critic's sign comparisons. It does not require maximizing over all $2^n$ actions.
At decision time, the soft outputs of the heads feed belief propagation on the Tanner graph. We then run a short local search under the critic among the decoded action's Hamming neighbors.
The analysis has two parts. First, we bound the probability of a wrong decode in terms of the per-head margins $m_f(s)$ and the girth, extending the peeling argument from erasures to soft errors whose size is bounded by margin. Second, we bound the expected regret of a wrong decode. The goal is to show that low-sensitivity checks push likely error patterns toward actions with small gaps.
The design study varies three things: the number of bits each check reads, the sensitivity $k_f$ of each check, and whether checks are fixed Boolean functions or small learned non-linear local codes. The graph construction is held at controlled girth.
Baselines
The naive reference point is independent heads. One head per bit, or one per action dimension, has no redundancy. Each head is argmaxed separately with the same critic and the same encoder. This is the "do nothing" version of factored action selection, and the full system must reduce decision error relative to it.
The second baseline is autoregressive per-dimension decoding. Each dimension's head is conditioned on the dimensions already chosen. This is a chain-shaped graph with coordination but no redundancy. It is the strongest simple way to handle coupling between dimensions.
The third is an ensemble of bit heads with majority voting, which is a repetition code. It receives the same total number of head outputs as our $n+m$, so the comparison isolates code structure from added capacity.
The ablation that isolates the key ingredient uses the identical Tanner graph, girth, and head count, but makes every check a parity check. If parity checks perform as well as non-linear ones, the margin argument fails. A second ablation keeps the non-linear checks but uses a random low-girth graph, which isolates the role of girth.
All discrete methods share the discretization, the critic architecture, and the stabilizers that Improving and Benchmarking Offline RL found decisive: LayerNorm and Double-Q, which account for a 33.8% gain between CRR and CRR+. Each method gets the same hyperparameter-search budget and the same seeds.
The strongest existing continuous-action methods serve as external references. OFQL reports a D4RL MuJoCo average normalized score of 92.5 and an AntMaze average of 84.6. CQL+ reports a cumulative D4RL locomotion score of 731.9, against 692.4 for IQL (Improving and Benchmarking Offline RL). "Beating" has two levels. The primary win is lower decision error and higher return than every discrete baseline, especially the parity ablation. The external target is to come within a few points of OFQL's 92.5 while using a discrete decoder. Exceeding it is not the claim. No reported result was found on Lacuna for discretized combinatorial-action variants of D4RL.
Why not just…?
Why not just use a larger ensemble of critics or heads? An ensemble is a repetition code. It corrects errors only by spending a full copy of every head, and its copies tend to fail together on out-of-distribution actions, where all of them extrapolate the same way. A sparse code reaches a given level of correction with fewer redundant outputs, but only if its checks have usable margins. The equal-budget repetition baseline settles this. If majority-voted ensembles match coded heads at equal output count, the coding argument adds nothing here, and we will report that.
Why not just use a continuous actor such as OFQL? On standard D4RL this is a real threat. With only 3 to 8 smooth action dimensions, a continuous policy may simply be better than any discretization. Our contribution targets combinatorial action spaces, where the action is genuinely discrete or a joint choice must coordinate across dimensions. We therefore report OFQL's published numbers alongside ours without claiming to beat them. The synthetic benchmark, which has discrete actions and controllable coupling, is where the decisive comparison happens.
Why not just use autoregressive or independent heads with better normalization? Normalization lowers per-head error but adds no redundancy. A chain has no cycles, so one error early in the chain carries through to every later choice. If careful tuning alone shrinks head error below every margin, coding is unnecessary. The synthetic sweep over the ratio of head error to gap shows where that regime ends.
Why not just use standard parity (LDPC) checks? The margin argument says parity checks must resolve one-bit neighbors of the best action, so they are the least reliable checks. This is the central ablation, and it can falsify the proposal directly.
Proposed Experiments
The first experiment is a synthetic factored-action MDP. It follows the controlled-gap synthetic constructions used in gap-dependent theory, with joint actions of 16 to 32 bits. Two knobs are set independently: how value decays with Hamming distance from the best action, which sets $\Delta_{(k)}$, and the strength of coupling between dimensions. We measure decision-error rate, regret per error, and return as functions of the ratio between head error and margin. The decisive checks are three. Non-linear checks should beat parity checks exactly when gaps grow with Hamming distance. The advantage should disappear when gaps are flat across distances, as the margin bound predicts. Low-girth graphs should lose the advantage of BP decoding.
The second experiment uses D4RL locomotion and AntMaze, discretizing each action dimension into 16 levels (4 bits each). This yields 12 to 32 bits per joint action. We report normalized scores against all discrete baselines and against the published continuous references above. We also report decoding latency against brute-force argmax wherever brute force remains feasible. A final check repeats the comparison on RL Unplugged's broader replay data. This tests whether the margin advantage holds when the critic's errors are less concentrated on out-of-distribution actions.
References
- Warm-Start Actor-Critic: From Approximation Error to Sub-optimality Gap
- Instance-Dependent Near-Optimal Policy Identification in Linear MDPs via Online Experiment Design
- Instance-Dependent Fixed-Budget Pure Exploration in Reinforcement Learning
- Logarithmic Regret for Reinforcement Learning with Linear Function Approximation
- On the Linear Convergence of Natural Policy Gradient Algorithm
- Cooperative local repair in distributed storage
- On Generalized LDPC Codes for 5G Ultra Reliable Communication
- An Upper Bound On the Size of Locally Recoverable Codes
- Bounds on the rate of linear locally repairable codes over small alphabets
- KO codes: inventing nonlinear encoding and decoding for reliable wireless communication via deep-learning
- DeepPolar: Inventing Nonlinear Large-Kernel Polar Codes via Deep Learning
- Associative Memory Using Dictionary Learning and Expander Decoding
- Improving and Benchmarking Offline Reinforcement Learning Algorithms
- One-Step Flow Q-Learning: Addressing the Diffusion Policy Bottleneck in Offline Reinforcement Learning