Reservoir Sampling

The algorithm processes each data point exactly once, in the order it arrives, without requiring prior knowledge of the total stream length N. This makes it memory-efficient for infinite or very large streams where storing all data is impossible.

• Mechanism: It maintains a reservoir of size k. For each new element at index i, it is included with probability k/i. If selected, it randomly replaces an existing element in the reservoir.
• Implication: Essential for online learning and real-time data streams, as it operates with constant memory O(k) beyond the reservoir itself.

When the stream ends, every possible subset of size k from the N total elements has an equal probability of being the final reservoir. This ensures a simple random sample without replacement.

• Proof: The probability any specific element is in the final reservoir is k/N. For a proof, consider the inductive logic: the probability an element at position i is in the reservoir at that time is k/i. It then must survive all subsequent replacement attempts (i+1...N), each with probability 1 - k/j * 1/k = (j-1)/j. The product telescopes to k/N.
• Critical For: Statistical validity in experience replay, ensuring the buffer does not introduce temporal bias.

The algorithm runs in O(1) amortized time per stream element, independent of the stream length or reservoir size. The core operation involves a random number generation and a potential array replacement.

• Operation: For element i, generate a random integer j from [0, i). If j < k, replace reservoir[j] with the new element.
• Efficiency: This predictable, low-cost per-item processing is why it's favored for high-throughput data pipelines and integrating into tight reinforcement learning training loops.

The inclusion probability k/i automatically adjusts as the stream progresses. Early elements have a high chance of entering the reservoir but a high chance of later being replaced.

• Early Stream: When i <= k, all elements are included with probability 1 (the reservoir is filling).
• Late Stream: As i grows large, the probability a new element enters the sample becomes very small (≈ k/i).
• Application: In non-stationary environments, this property can be modified (e.g., with a decaying probability) to bias the sample toward more recent experiences, creating a sliding window effect within the reservoir.

Algorithm R is the standard, in-place implementation. It is the reference for understanding all reservoir sampling variants.

Pseudocode:

pythonCopy
# Initialize: fill reservoir with first k elements
reservoir = stream[:k]

for i in range(k, N):
    j = random.randint(0, i)  # inclusive range [0, i]
    if j < k:
        reservoir[j] = stream[i]

• Key Detail: The random integer must be drawn from an inclusive range [0, i]. This ensures the correct probabilities.
• Foundation: This algorithm is the basis for weighted reservoir sampling and distributed reservoir sampling extensions.

In reinforcement learning, a replay buffer is often implemented as a circular buffer (FIFO). Reservoir sampling provides a statistically rigorous alternative or complement.

• Uniform vs. FIFO: A simple FIFO buffer is a deterministic sample of the most recent k experiences. Reservoir sampling provides a uniform random sample of all N experiences seen, preserving information from earlier in training.
• Hybrid Approaches: Prioritized Experience Replay (PER) modifies the sampling distribution away from uniform. Reservoir sampling can be viewed as the uniform baseline (p=1) before priorities are applied.
• Use Case: In continual learning, a reservoir sampling-based buffer helps mitigate catastrophic forgetting by ensuring a model revisits a representative sample of past tasks.

An experience replay buffer is a core data structure in reinforcement learning that stores past interactions (state, action, reward, next state). Its primary functions are:

• Breaking temporal correlations by randomly sampling past experiences for training.
• Improving sample efficiency by reusing experiences multiple times.
• Stabilizing training for deep neural networks, as famously demonstrated in the Deep Q-Network (DQN) algorithm. A common implementation is a circular buffer (FIFO), but reservoir sampling provides a statistically sound method for maintaining a fixed-size, uniform random sample from an unbounded stream.

Prioritized Experience Replay is an advanced sampling strategy that selects experiences from a replay buffer with probability proportional to their temporal-difference (TD) error. This focuses learning on transitions the agent found more surprising or informative.

• Core Mechanism: Uses a priority queue (often a binary heap) instead of uniform random access.
• Bias Correction: Requires importance sampling weights to correct for the shifted sampling distribution, ensuring convergence.
• Impact: Can dramatically accelerate learning in complex environments by prioritizing high-learning-value experiences.

Online learning is a machine learning paradigm where a model updates its parameters incrementally, one data point (or mini-batch) at a time, as the data arrives in a stream. This contrasts with batch learning on a static dataset.

• Key Challenge: Adapting to non-stationary data distributions (concept drift).
• Connection to Reservoir Sampling: Reservoir sampling is a canonical algorithm for maintaining a representative sample from an online data stream, which can be used for monitoring, evaluation, or as a replay buffer for continual learning systems.
• Architectures: Includes algorithms like Follow-The-Regularized-Leader (FTRL) and stochastic gradient descent applied to streaming data.

Catastrophic forgetting (or catastrophic interference) is the tendency of a neural network to abruptly and drastically lose performance on previously learned tasks when trained on new data. It is the central challenge in continual learning.

• Role of Replay: Experience replay mechanisms, including those using reservoir sampling, directly combat forgetting by interleaving old and new data during training.
• Related Techniques: Generative replay uses a generative model to produce synthetic old data. Elastic Weight Consolidation (EWC) regularizes important weights for old tasks.
• Buffer-based solutions: Methods like Gradient Episodic Memory (GEM) explicitly store exemplars in a buffer to constrain new learning.

Importance sampling is a fundamental statistical technique for estimating expected values under one distribution using samples drawn from a different distribution. It is critical for off-policy reinforcement learning.

• Core Formula: Corrects estimates using a ratio of probability densities (or policy probabilities), known as the importance sampling ratio.
• Application in PER: Used to correct the bias introduced by non-uniform sampling in Prioritized Experience Replay.
• Advanced Methods: Algorithms like Retrace and V-trace use sophisticated importance sampling for stable off-policy correction with function approximation.

Streaming algorithms are designed to process data sequentially, in a single pass, using memory sublinear in the size of the data stream. They are essential for big data and real-time analytics.

• Reservoir Sampling's Place: It is a quintessential streaming algorithm for the random sampling problem.
• Other Key Streaming Problems:
  • Frequency Estimation (e.g., Count-Min Sketch).
  • Distinct Element Counting (e.g., HyperLogLog).
  • Heavy Hitters Identification (e.g., Misra-Gries).
• ML Relevance: These algorithms enable efficient feature statistics collection, data distribution monitoring, and memory-efficient preprocessing for online learning systems.