Sample Efficiency

The cumulative reward, or return, is the sum of all rewards an agent collects in an episode. It is the fundamental performance signal in reinforcement learning (RL). High sample efficiency is achieved when an algorithm maximizes this sum with minimal environmental interactions.

• Sparse vs. Dense Rewards: Dense rewards (frequent feedback) typically improve sample efficiency but require careful engineering.
• Discount Factor (γ): A hyperparameter between 0 and 1 that weights future rewards, influencing long-term planning efficiency.
• In sim-to-real, policies are trained to maximize cumulative reward in simulation before transfer.

Sample complexity is a theoretical measure from computational learning theory that bounds the number of training samples required for an algorithm to learn a concept with high probability within a specified error tolerance.

• PAC Framework: Often expressed in Probably Approximately Correct (PAC) learning terms.
• Empirical vs. Theoretical: While theoretical bounds exist for simple models, deep RL sample complexity is typically assessed empirically through learning curves.
• A core goal in sim-to-real research is to develop algorithms with lower sample complexity, reducing the simulation burden.

A learning curve is a plot of an agent's performance (e.g., cumulative reward, success rate) against the number of training samples or environment steps. It is the primary empirical tool for evaluating sample efficiency.

• Steepness: A steeper initial ascent indicates faster initial learning.
• Asymptotic Performance: The final plateau indicates the best performance achievable with the given data and algorithm.
• Comparison: Algorithms are compared by how quickly and how high their learning curves rise. Efficient algorithms reach high asymptotic performance with fewer samples.

Experience replay is a technique that stores an agent's past experiences (state, action, reward, next state) in a buffer and repeatedly samples from it during training. This re-use of data dramatically improves sample efficiency.

• Breaks Temporal Correlations: Random sampling decorrelates sequential experiences, stabilizing training.
• Prioritized Replay: Some implementations weight sampling toward experiences with high temporal-difference error, learning more from surprising outcomes.
• It is a foundational component of sample-efficient off-policy RL algorithms like DQN and DDPG, commonly used in simulation.

Model-based reinforcement learning (MBRL) algorithms learn an explicit model of the environment's dynamics (a world model) and use it for planning or to generate synthetic training data. This approach is often more sample-efficient than model-free RL.

• Dynamics Model: A function that predicts the next state and reward given the current state and action.
• Planning: Algorithms like Monte Carlo Tree Search (MCTS) use the model to simulate future trajectories.
• Data Augmentation: The learned model can generate unlimited imagined rollouts for policy training. This is highly aligned with sim-to-real, where the simulation itself is a privileged dynamics model.

This distinction defines how an algorithm uses collected experience, directly impacting sample efficiency.

• Off-Policy Learning (e.g., DQN, SAC): Can learn from experiences generated by an older policy or an entirely different behavior policy. This enables experience replay and is generally more sample-efficient.
• On-Policy Learning (e.g., A2C, PPO): Can only learn from experiences generated by the current policy. After an update, old experiences are discarded. This is often less sample-efficient but can be more stable.
• For sim-to-real, off-policy methods are favored when simulation samples are abundant but real-world samples are extremely limited, as the policy can learn from a fixed dataset of real-world rollouts.

Cumulative reward, or return, is the sum of all rewards an agent receives during an episode in reinforcement learning. It is the fundamental objective an agent aims to maximize.

• Direct Performance Measure: A high cumulative reward indicates successful task completion.
• Sample Efficiency Proxy: An algorithm that achieves a high cumulative reward with fewer environmental interactions is more sample-efficient.
• Normalization: For comparison across tasks, cumulative reward is often normalized against the performance of a random or expert policy.

A learning curve is a plot that visualizes an algorithm's performance (e.g., success rate or cumulative reward) as a function of the number of training samples or environmental interactions.

• Primary Diagnostic Tool: It is the most direct visualization of sample efficiency. A steeper curve that plateaus at a higher performance level indicates superior efficiency.
• Comparison Metric: Learning curves allow for head-to-head comparison of different algorithms or hyperparameter settings.
• Asymptotic Performance: The curve's plateau reveals the final performance level, while its shape shows the speed of convergence.

Sample complexity is a theoretical measure from computational learning theory that quantifies the number of training samples required for an algorithm to learn a concept with high probability within a specified error tolerance.

• Theoretical Guarantee: It provides a worst-case upper bound on the data needed for learning, often expressed using Big O notation (e.g., O(1/ε²)).
• Distinction from Efficiency: While related, sample complexity is a theoretical bound, whereas sample efficiency is an empirical observation of an algorithm's data requirements in practice.
• Algorithm Design Goal: Developing algorithms with lower sample complexity is a key research objective for efficient learning.

Data efficiency is a broader term often used synonymously with sample efficiency, particularly in supervised learning contexts. It emphasizes learning effectively from limited or expensive datasets.

• Supervised Learning Focus: In classification or regression, it measures how well a model generalizes from a small labeled training set.
• Core Techniques: Methods to improve data efficiency include data augmentation, semi-supervised learning, transfer learning, and active learning.
• Business Impact: High data efficiency reduces the cost and time required for manual data collection and labeling, accelerating model deployment.

The exploration-exploitation trade-off is a fundamental dilemma in reinforcement learning central to sample efficiency. An agent must balance exploring new states/actions to discover higher rewards against exploiting known actions to maximize immediate reward.

• Inefficient Exploration: Pure random exploration is highly sample-inefficient.
• Efficient Strategies: Algorithms like Upper Confidence Bound (UCB) or Thompson Sampling use uncertainty to guide exploration more intelligently.
• Direct Impact: An optimal balance allows an agent to discover a high-reward policy with minimal environmental interactions.

Experience replay is a technique used in deep reinforcement learning (e.g., DQN) to improve sample efficiency by storing and repeatedly sampling past transitions (state, action, reward, next state) from a replay buffer.

• Data Reuse: Allows the learning algorithm to learn from each real interaction multiple times, dramatically improving efficiency.
• Stabilizes Training: Breaking temporal correlations in sequential data by sampling experiences randomly from the buffer.
• Prioritized Replay: An advanced variant that samples more important, informative transitions more frequently, further boosting efficiency.