Circular Buffer

A circular buffer is allocated a fixed, contiguous block of memory upon creation. This provides several critical advantages:

• Deterministic Performance: Memory allocation and deallocation overhead is eliminated during runtime operations.
• Real-Time Safety: Prevents unpredictable garbage collection pauses, which is essential for embedded systems, audio processing, and robotics.
• Cache Efficiency: The contiguous layout maximizes CPU cache performance for rapid sequential access.

The buffer's size is a crucial hyperparameter, balancing the diversity of stored experiences against memory constraints.

The primary operations—adding (enqueue) and removing (dequeue) elements—execute in constant time, regardless of buffer size.

• Head/Tail Pointers: Two indices (or pointers) track the next insertion point (tail) and the next removal point (head).
• Modulo Arithmetic: When a pointer reaches the end of the allocated array, it wraps around to the beginning using a modulo operation (index % capacity). This wrap-around creates the "circular" behavior.
• No Data Shifting: Unlike a linear queue, elements are never shifted, eliminating O(n) operations. This makes it ideal for high-throughput data streams in experience replay, where new transitions are constantly added.

When the buffer is at capacity, the next enqueue operation automatically overwrites the oldest element. This is a defining characteristic.

• First-In-First-Out (FIFO) Eviction: The element at the head pointer is replaced, maintaining temporal order.
• Handles Non-Stationary Data: In online learning, this provides a rolling window over the most recent data, which is critical when the environment or data distribution changes (concept drift).
• Passive Management: No explicit logic is needed to manage old data; the structure self-manages. This contrasts with a reservoir sampling buffer, which uses a randomized overwrite policy.

For experience replay, a key operation is uniformly sampling a random mini-batch of past experiences. A circular buffer enables this efficiently.

• Direct Indexing: Because all elements reside in a contiguous array, any stored experience can be accessed in O(1) time via a computed index.
• Uniform Sampling: A random integer is generated within the range of currently stored elements ([head, tail) modulo capacity), and the corresponding memory location is accessed directly. This efficiency is why circular buffers are the default backend for standard replay buffers in libraries like RLlib and Stable-Baselines3.

The buffer's state is fully defined by three simple variables, making it lightweight and easy to serialize.

• Buffer Array: The underlying fixed-size array.
• Head Index: Points to the oldest element (next to dequeue).
• Tail Index: Points to the next empty slot for insertion.
• Count or Full Flag: A derived variable (or flag) tracks the current number of elements, calculated from head and tail. This minimal state allows for efficient checkpointing and restoration, which is vital for fault-tolerant training systems.

In production systems, a single buffer is often accessed by multiple concurrent threads (e.g., one adding experiences, another sampling batches). Thread-safe implementations are critical.

• Lock-Based: Using mutexes or semaphores to protect the head and tail pointers. This can create contention bottlenecks.
• Lock-Free (or Wait-Free): Advanced implementations use atomic operations and careful memory ordering to allow concurrent enqueue/dequeue without locks, maximizing throughput in multi-core systems.
• Double Buffering: A technique where one buffer is written to while another is read from, then swapped, eliminating contention entirely. This is common in audio and graphics pipelines.

Circular buffers are essential for online machine learning models that adapt to non-stationary data streams, such as fraud detection or trending topic analysis.

• Concept Drift Detection: A model monitors its performance on a sliding window of recent data held in a circular buffer. A significant drop in accuracy signals potential drift.
• Reservoir Sampling: For truly unbounded streams, a circular buffer can implement reservoir sampling to maintain a uniform random sample of fixed size from the entire history seen so far.

Beyond training, circular buffers manage high-velocity data in production inference pipelines.

• Temporal Fusion: For models requiring sequential context (e.g., video action recognition, real-time anomaly detection), a circular buffer holds the last N frames or sensor readings.
• Batching Optimization: Inference servers use circular buffers to aggregate incoming requests, enabling continuous batching for optimal GPU utilization and reduced latency.
• Pre-processing Queues: They act as a decoupling mechanism between data ingestion and model inference, smoothing out bursts in load.

An experience replay buffer is the general-purpose data structure for which a circular buffer is a common implementation. It stores past experiences—typically tuples of (state, action, reward, next state)—to be sampled later for training. Its primary functions are:

• Breaking temporal correlations by randomizing the order of experiences.
• Improving sample efficiency by reusing each experience in multiple updates.
• Enabling off-policy learning, where the policy being improved differs from the one that collected the data.

Prioritized Experience Replay is an advanced sampling strategy that modifies a standard replay buffer. Instead of uniform random sampling, experiences are sampled with a probability proportional to their temporal-difference (TD) error. This focuses learning on transitions the agent found more surprising or informative. Implementation requires:

• A priority queue or sum-tree data structure for efficient sampling.
• Importance sampling weights to correct the bias introduced by non-uniform sampling and ensure convergence.

A trajectory buffer stores and samples complete sequences of states and actions (trajectories), rather than individual, independent transitions. This is critical for algorithms that require temporal context, such as:

• On-policy algorithms like Proximal Policy Optimization (PPO), which use entire rollout sequences.
• Sequence models like the Decision Transformer, which are trained on chunks of past trajectories. Unlike a circular buffer of single transitions, managing trajectory storage involves handling variable-length sequences and often uses a first-in-first-out queue for entire episodes.

Reservoir sampling is a randomized algorithm for maintaining a fixed-size, uniform random sample from a data stream of unknown and potentially infinite length. It is an alternative sampling logic for a replay buffer in non-stationary environments. The algorithm guarantees that every item seen in the stream has an equal probability of being in the final reservoir. It is particularly useful when:

• The data distribution changes over time (concept drift).
• You need a statistically representative sample of the entire stream seen so far, not just the most recent N items.

Generative replay is a continual learning technique where a generative model (e.g., a Generative Adversarial Network or Variational Autoencoder) is trained to produce synthetic data samples from previous tasks. These generated samples are then interleaved with real data from the new task during training. This approach:

• Mitigates catastrophic forgetting by simulating rehearsal of old data.
• Decouples memory requirements from storing raw data, though it requires maintaining and training a generative model.
• Can be seen as a learned, compressed form of a replay buffer.

These are two critical hyperparameters governing replay buffer behavior:

• Buffer Capacity: The maximum number of experiences stored. A larger capacity increases diversity but may store outdated, less relevant data. A circular buffer's fixed size makes this a direct design choice.
• Replay Ratio: The average number of gradient updates performed using the replay buffer for each new experience added from the environment. A ratio greater than 1.0 increases data efficiency but may lead to overfitting to old data. A common default in Deep Q-Networks is 4.