PaperlayerView exact revision on arXiv

Source-linked AI summary

Vector Symbolic Policy Gradient

Ryozo Masukawa, Sanggeon Yun, SungHeon Jeong, Hyunwoo Oh, Raheeb Hassan, Pietro Mercati, Nathaniel D. Bastian, Mahdi Imani, Mohsen Imani

arXiv:2608.18404v1cs.LGcs.AIcs.SC

TL;DR

Existing VSA-based RL methods leave open whether action hypervectors can directly parameterize a categorical actor with an exact policy-gradient update. VSPG answers this using similarity-scored unit-norm action hypervectors, proving advantage-weighted bundling, compressed kernel-memory formation, and robustness to random bit flips.

  • Problem

    Existing VSA-based RL methods leave open whether action hypervectors can directly parameterize a categorical actor and express its policy-gradient update.

  • Method

    VSPG represents actions with unit-norm hypervectors, scores them against encoded states, and applies closed-form advantage-weighted bundling followed by row normalization.

  • Results

    Across classic control, MiniGrid, and multi-agent building control, VSPG achieves competitive final performance, stronger sample efficiency, and graceful degradation under bit-flip corruption.

  • Takeaways & Limitations

    VSPG connects vector-symbolic action memories, log-linear policy gradients, and kernel policy search while providing a quantitative robustness guarantee for bipolar memories.

  • Takeaways & Limitations

    The random-bit-flip robustness bound applies to bipolar memories; multi-bit quantized memories are evaluated empirically rather than covered by the same guarantee.

Abstract

from arXiv · show

We answer this question with Vector-Symbolic Policy Gradient (VSPG), a discrete-action actor that represents each action by a unit-norm hypervector and scores it by similarity to the encoded state. Under the standard softmax policy-gradient surrogate, we prove that its update is exactly advantage-weighted hypervector bundling followed by normalization, and therefore supports standard advantage estimators. We further show that each trained action hypervector is a fixed-size compressed kernel memory, storing an advantage-weighted kernel expansion over visited states and transferring evidence according to the encoder-induced similarity. This provides a concrete mechanism that can support sample-efficient learning without increasing inference-time memory. Finally, for bipolar action memories, we prove that greedy action selection is stable under random bit flips, with failure probability decaying exponentially in the hypervector dimension. VSPG thus connects VSA action memories, log-linear policy gradients, and kernel policy search while providing a quantitative robustness guarantee.

1 Introduction

VSPG is a discrete-action actor that uses unit-norm action hypervectors and an exact advantage-weighted bundling update. It also yields compressed kernel memories, bit-flip robustness, and competitive, sample-efficient performance across several reinforcement-learning benchmarks.

  • Motivation: VSA represents data with high-dimensional distributed hypervectors and computes through similarity search, bundling, binding, and normalization.Nearly orthogonal hypervectors support superposition with limited interference, while encoder-induced inner products preserve meaningful input similarity.
  • Method: VSPG represents each discrete action with a unit-norm hypervector and scores actions by similarity to the encoded observation.A fixed encoder maps observations to hypervectors, and action hypervectors score them through inner products.
  • Method: VSPG’s standard softmax policy-gradient update is exactly advantage-weighted hypervector bundling followed by normalization.This exact vector-symbolic interpretation supports standard advantage estimators.
  • Mechanism: Trained action hypervectors are fixed-size compressed kernel memories that store advantage-weighted expansions over visited states and transfer evidence through encoder-induced similarity.This mechanism can support sample-efficient learning without increasing inference-time memory.
  • Evaluation: VSPG achieves competitive final performance and stronger sample efficiency than matched actor baselines across classic control, MiniGrid, and multi-agent building control.The evaluations compare against DNN, linear actor, and QHD baselines; distributed action memories also retain performance better under post-training bit-flip corruption.

2 Related Work

Prior VSA-RL work primarily uses hypervectors as lightweight approximators within existing actor-critic or value-based formulations, while policy corruption is addressed mainly through fault-aware training, error injection, or hardware adaptation. VSPG contributes an exponential failure bound for bipolar memories under bit corruption at a fixed similarity margin.

  • VSA-RL methods: Prior VSA-RL methods use hypervectors as lightweight function approximators, including Gaussian actors and critics for continuous control and Q-value hypervectors for discrete actions.HDPG applies VSA to continuous-control Gaussian actors and critics, whereas QHD methods learn action-specific Q-value hypervectors through Bellman-error-weighted bundling.
  • VSA-RL methods: The value-based QHD line has been applied to cybersecurity, robotics, navigation, and sensing.These applications extend the discrete-action value-based approach across several resource-constrained or embodied domains.
  • Robustness to corruption: Prior work on stored-policy corruption mainly uses fault-aware training, bit-error injection, or hardware-level adaptation to mitigate unreliable autonomous decisions.Low-voltage operation and approximate memory can introduce bit-level errors in model parameters and reduce decision reliability.
  • Robustness to corruption: An exponential failure bound in the hypervector dimension holds for bipolar memories at a fixed similarity margin under model-state bit corruption.The analysis provides this robustness guarantee alongside evaluation of degradation under quantization and model-state bit corruption.

3 Preliminaries

The paper formulates decentralized reinforcement learning as a Dec-POMDP and uses the standard policy-gradient objective with advantage estimates. It introduces VSA representations in which fixed state hypervectors and action hypervectors support similarity-based discrete-action policies.

  • Policy gradients: The joint policy maximizes expected discounted return, and each factorized agent policy uses a policy-gradient expression based on trajectories induced by the joint policy and environment.Advantage estimates may come from returns or actor–critic methods such as Generalized Advantage Estimation (GAE).
  • Vector-symbolic representations: VSA represents inputs as high-dimensional hypervectors and computes with element-wise addition for bundling, element-wise multiplication for binding, and similarity search.A fixed encoder produces h = φ(x) ∈RD, normalized when used for similarity search.
  • Vector-symbolic representations: Quasi-orthogonality limits interference among bundled random hypervectors, enabling associative prototypes that classify by similarity; VSPG applies this representation to discrete-action policies.Action hypervectors serve as policy weights, while encoded states serve as fixed features for policy-gradient learning.

4 Vector-Symbolic Policy Gradient

VSPG uses unit-norm action hypervectors as a stochastic policy over fixed encoded inputs, with similarity-based logits and a closed-form normalized update. The method is exactly advantage-weighted hypervector bundling, stores a compressed kernel expansion over experience, and provides exponential greedy-readout stability for bipolar memories under random bit flips.

  • Policy construction: VSPG converts VSA action prototypes into a stochastic policy whose logits are similarity scores between unit-norm action hypervectors and fixed encoded inputs.The policy uses inner products followed by a softmax, with temperature τ controlling logit scale and policy concentration.
  • Policy-gradient update: VSPG requires no encoder backpropagation or optimizer state, and it supports any advantage estimator by changing the surrogate weights in Λ.Row normalization restores unit norms after each closed-form update.
  • Policy-gradient update: The closed-form update is exactly the sampled softmax policy gradient, implemented as advantage-weighted bundling followed by row-wise projection onto the unit sphere.The update adds the encoded state to the selected action and subtracts it from other actions in proportion to their probabilities, weighted by the advantage.
  • Kernel-memory interpretation: Each trained action hypervector is a fixed-size compressed kernel expansion over visited inputs, with advantage-weighted evidence transferred according to encoder-induced similarity.Advantageous transitions add positive mass to an action at similar inputs, while competing evidence contributes negative mass; the expansion remains superposed in D coordinates and is not enumerated at inference.
  • Robustness guarantee: For bipolar action memories, independent random sign flips preserve greedy selection except when the perturbation exceeds the clean action margin, with failure probability decaying exponentially in D.The proof applies Hoeffding’s inequality to each action’s residual perturbation and uses a union bound over actions.

5 Experiments

Experiments evaluate VSPG on discrete-action benchmarks and noisy multi-agent building control, testing sample efficiency, final performance, encoder effects, dimensionality, and robustness. VSPG learns faster than neural and linear actors in several tasks, while results show that encoder-induced similarity and hypervector dimension govern performance and memory interference.

  • Experimental scope: Experiments span MiniGrid, classic control, and SustainGym building control to assess sample efficiency, final performance, noisy delayed control, and multi-agent control.Results are reproducible on CPUs alone, with comparable tuning budgets that otherwise favor baselines.
  • Single-agent benchmarks: VSPG learns substantially faster than DNN and Raw-Linear actors on classic control, especially CartPole-v1 and Acrobot-v1, while remaining competitive across MiniGrid.On LunarLander-v2, VSPG improves faster early, but final performance is broadly comparable across methods; QHD deteriorates with greater complexity and partial observability.
  • Encoder comparison: Across both SustainGym climates, FHRR- and RFF-VSPG achieve the strongest returns, whereas Basis-VSPG performs poorly with high variance.The RFF configuration also fails on DoorKey-8x8, indicating that VSPG inherits the inductive bias of encoder-induced similarity.
  • Robustness: Under post-training bit corruption, VSPG action memories generally degrade more gracefully than DNN and Raw-Linear actors.SustainGym evaluates VSPG, DNN, and Raw-Linear actors after quantization and independent stored-bit flips.
  • Dimensionality: On CartPole-v1, performance improves with hypervector dimension D and largely saturates beyond D = 1,000; DoorKey-8x8 is more sensitive but generally benefits from higher dimensions.Increasing D improves approximation of κ(x, x′) and reduces interference in the compressed policy memory.
  • Representation analysis: Basis and FHRR produce coherent DoorKey-8x8 neighborhoods with high kernel similarity, whereas the unsuccessful RFF configuration yields weaker and less consistent matches.These neighborhoods are retrieved under the fixed encoder-induced similarity, illustrating how the encoder determines where stored advantage evidence is shared.

6 Conclusion

VSPG formulates discrete-action policy gradients with vector-symbolic representations: softmax updates become advantage hypervector bundling, action memories are fixed-size kernel expansions, and bipolar memories resist random bit flips. Experiments indicate favorable sample efficiency, competitive returns, and graceful degradation under quantization and memory corruption.

  • 6 Conclusion: VSPG’s softmax policy-gradient update becomes advantage hypervector bundling, while action memories encode fixed-size kernel expansions over experience.This connects vector-symbolic action representations with policy-gradient learning and kernel-like memory compression.
  • 6 Conclusion: Bipolar action memories provide provably robust greedy selection under random bit flips.The conclusion also reports graceful degradation under memory corruption and quantization.
  • 6 Conclusion: Experiments show favorable sample efficiency, competitive returns, and graceful degradation under quantization and memory corruption.These findings summarize the empirical behavior reported for VSPG.

A Baseline Actor Architectures

This section defines three baseline actor architectures—DNN, Raw-Linear, and QHD—and explains how their representations, learning procedures, and applicability differ from VSPG.

  • DNN: DNN uses a two-hidden-layer ReLU MLP to map observations to |A| action logits before softmax selection.For classic control and MiniGrid, it uses VSPG’s REINFORCE advantages and Adam optimizer; SustainGym Multi-Agent uses decentralized actors and a shared centralized critic.
  • Raw-Linear: Raw-Linear maps raw observations directly to |A| action logits with one linear layer, isolating hyperdimensional encoding from linear policy effects.All remaining training settings, including SustainGym Multi-Agent and Single variants, match DNN.
  • QHD: QHD learns a linear hyperdimensional Q-function, Q(s, a) = M[a]⊤s, using semi-gradient Q-learning as the closest prior HDC baseline.It is a single-agent, discrete-action value-based method rather than an actor architecture.
  • QHD: QHD selects actions ϵ-greedily with linearly decayed exploration and is compared using matched episode budgets because it is off-policy while VSPG is on-policy.QHD is omitted from SustainGym because it does not fit the actor-focused multi-agent comparison.

B Encoder Implementation Details Across Environments

Across environments, VSPG uses a fixed base map for each encoder family and builds environment-specific encoders through preprocessing, binding, and bundling. Resulting real-valued hypervectors are normalized to unit Euclidean norm before entering the actor.

  • Encoder construction: Each encoder family e ∈ {Basis, FHRR, RFF} has a fixed base map φ_e, applied directly to preprocessed observations or composed across components.Composition uses binding and bundling of multiple φ_e-encoded components.
  • VSA operations: Binding ⊙ and bundling ⊕ denote VSA operations whose implementations differ across Basis and FHRR encoders.Basis uses element-wise multiplication and addition; FHRR uses complex multiplication or phase addition and complex addition.
  • Normalization: Every resulting real-valued hypervector is normalized to unit Euclidean norm before being passed to the actor.This normalization is applied after environment-specific encoding and composition.

B.1 MiniGrid: Compositional Encoding over Grid Cells · B.2 Classic Control: Direct Encoding · B.3 SustainGym: Range-Normalized Direct Encoding

The encoders use compositional MiniGrid representations with spatially controlled similarity, direct encoding for flat classic-control observations, and range-normalized direct encoding for SustainGym. All resulting representations are normalized to unit Euclidean norm.

  • B.1 MiniGrid: Compositional Encoding over Grid Cells: MiniGrid binds each cell’s position and categorical identifiers, bundles visible cells with the agent direction, and normalizes the resulting representation.Basis uses Hadamard-product binding and vector-addition bundling; FHRR uses complex multiplication and addition before conversion and normalization.
  • B.1 MiniGrid: Compositional Encoding over Grid Cells: Basis assigns fixed bipolar hypervectors to MiniGrid categorical components and represents position by binding independently drawn row and column encodings.Object, color, state, and direction identifiers use independent fixed codebooks.
  • B.1 MiniGrid: Compositional Encoding over Grid Cells: FHRR represents MiniGrid components with unit complex hypervectors, whose binding adds component phases before real–imaginary interleaving and final normalization.Each complex coordinate is projected back to unit magnitude before interleaving.
  • B.1 MiniGrid: Compositional Encoding over Grid Cells: With w = 1.0, adjacent horizontal or vertical cells have expected similarity exp(−1/2) ≈0.61, while larger w broadens spatial generalization.Smaller w produces more nearly orthogonal positions; larger w produces broader spatial similarity neighborhoods.
  • B.2 Classic Control: Direct Encoding: Classic-control observations have dimensions d = 4, 6, and 8 for CartPole-v1, Acrobot-v1, and LunarLander-v2, respectively, and are encoded directly.Basis uses φBasis(x) = Wx; FHRR and RFF use fixed random maps, without additional range normalization, followed by unit-norm normalization.
  • B.3 SustainGym: Range-Normalized Direct Encoding: SustainGym’s d = 10 flat observations undergo component-wise range normalization before direct application of the corresponding base map.This prevents large-range quantities such as solar heat gain from dominating the random projection.
  • B.3 SustainGym: Range-Normalized Direct Encoding: SustainGym applies fixed FHRR and RFF maps or Basis with ρ = sign, then normalizes the output to unit Euclidean norm.Range normalization is applied before encoding because the observation components have substantially different physical scales.

C Hyperparameter Tuning Budget

The section describes comparable hyperparameter tuning across methods and environments, with VSPG jointly tuning τ and η because they affect logit scale and update magnitude. Selected configurations are evaluated across five seeds for reported results.

  • Tuning strategy: VSPG jointly tunes τ and η because τ affects both logit scale and effective update magnitude.This joint tuning accounts for τ’s two roles in the optimization.
  • Tuning budgets: DNN and Raw-Linear use similarly sized searches, while QHD is evaluated over a substantially larger hyperparameter grid.The baselines receive at least comparable tuning budgets to VSPG.
  • Evaluation protocol: Each selected hyperparameter configuration is evaluated over five seeds for the reported results.Table 3 reports search spaces, evaluated configurations, and selected hyperparameters for each method and environment.

D Closed-Form Equivalence and the Sphere Constraint

The section shows that closed-form VSPG is an algebraic realization of policy-gradient learning over fixed HDC features, while sphere projection and initialization shape optimization behavior. Standard initialization yields similar learning across implementations, but zero initialization can make immediate normalization amplify weak early evidence.

  • Closed-form equivalence: Proposition 1 shows that advantage-weighted bundling, Λ⊤S, exactly equals the sampled policy gradient of the softmax surrogate.This establishes the equivalence between the vector-symbolic actor and a log-linear softmax policy over fixed HDC features.
  • Initialization and projection: Under standard initialization, directly differentiated variants generally learn similarly to the closed-form implementation, with larger differences on harder DoorKey tasks.The differences reflect projection, parameter-norm dynamics, and independently tuned optimization scales rather than a different policy objective.
  • Initialization and projection: At C = 0, immediate row normalization maps the first policy-gradient update to unit norm regardless of magnitude, allowing weak or noisy early evidence to set the action direction.Zero initialization makes the initial policy uniform, so the first update contains only evidence from initial trajectories.
  • Initialization and projection: Without normalization, action-vector norms grow gradually with accumulated gradient signal, whereas row normalization enforces bounded cosine-policy parameters and fixed-scale action-memory geometry.Row normalization is not required for the policy-gradient identity, but combined with zero initialization it can amplify early updates.
Loading 2608.18404v1…