# Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity

arXiv: https://arxiv.org/abs/2210.09579 · HTML: https://mlsanity.com/paper/2210.09579/

## Key facts

- Cited by 62 papers in the map (data through 14 Oct 2026).
- Builds on 42 of its 61 references that are in the map.
- First posted on arXiv 18 Oct 2022.

## Builds on (most cited first, 30 of 42)

- [Meta-World: A Benchmark and Evaluation for Multi-Task and Meta Reinforcement Learning](https://mlsanity.com/paper/1910.10897/) (2019)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Exploration by Random Network Distillation](https://mlsanity.com/paper/1810.12894/) (2018)
- [Learning Dexterous In-Hand Manipulation](https://mlsanity.com/paper/1808.00177/) (2018)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Provably Efficient Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/1907.05388/) (2019)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Is Q-learning Provably Efficient?](https://mlsanity.com/paper/1807.03765/) (2018)
- [FeUdal Networks for Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1703.01161/) (2017)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [Model-Based Reinforcement Learning with Value-Targeted Regression](https://mlsanity.com/paper/2006.01107/) (2020)
- [Provably Efficient Exploration in Policy Optimization](https://mlsanity.com/paper/1912.05830/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Tighter Problem-Dependent Regret Bounds in Reinforcement Learning without Domain Knowledge using Value Function Bounds](https://mlsanity.com/paper/1901.00210/) (2019)
- [Incentivizing Exploration In Reinforcement Learning With Deep Predictive Models](https://mlsanity.com/paper/1507.00814/) (2015)
- [RIDE: Rewarding Impact-Driven Exploration for Procedurally-Generated Environments](https://mlsanity.com/paper/2002.12292/) (2020)
- [Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition](https://mlsanity.com/paper/2004.10019/) (2020)
- [Optimism in Reinforcement Learning with Generalized Linear Function Approximation](https://mlsanity.com/paper/1912.04136/) (2019)
- [Provably Efficient Reinforcement Learning for Discounted MDPs with Feature Mapping](https://mlsanity.com/paper/2006.13165/) (2020)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Corralling a Band of Bandit Algorithms](https://mlsanity.com/paper/1612.06246/) (2016)
- [PC-PG: Policy Cover Directed Exploration for Provable Policy Gradient Learning](https://mlsanity.com/paper/2007.08459/) (2020)
- [Provably Efficient Q-Learning with Low Switching Cost](https://mlsanity.com/paper/1905.12849/) (2019)
- [Towards Playing Full MOBA Games with Deep Reinforcement Learning](https://mlsanity.com/paper/2011.12692/) (2020)
- [Model Selection in Contextual Stochastic Bandit Problems](https://mlsanity.com/paper/2003.01704/) (2020)
- [PRM-RL: Long-range Robotic Navigation Tasks by Combining Reinforcement Learning and Sampling-based Planning](https://mlsanity.com/paper/1710.03937/) (2017)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Q-learning with Logarithmic Regret](https://mlsanity.com/paper/2006.09118/) (2020)
- [Hybrid Reward Architecture for Reinforcement Learning](https://mlsanity.com/paper/1706.04208/) (2017)

## Built on by (most cited first, 30 of 62)

- [Cal-QL: Calibrated Offline RL Pre-Training for Efficient Online Fine-Tuning](https://mlsanity.com/paper/2303.05479/) (2023)
- [RL-VLM-F: Reinforcement Learning from Vision Language Foundation Model Feedback](https://mlsanity.com/paper/2402.03681/) (2024)
- [General In-Hand Object Rotation with Vision and Touch](https://mlsanity.com/paper/2309.09979/) (2023)
- [Comprehensive Overview of Reward Engineering and Shaping in Advancing Reinforcement Learning Applications](https://mlsanity.com/paper/2408.10215/) (2024)
- [Towards Better Alignment: Training Diffusion Models with Reinforcement Learning Against Sparse Rewards](https://mlsanity.com/paper/2503.11240/) (2025)
- [RLIF: Interactive Imitation Learning as Reinforcement Learning](https://mlsanity.com/paper/2311.12996/) (2023)
- [A Large Language Model-Driven Reward Design Framework via Dynamic Feedback for Reinforcement Learning](https://mlsanity.com/paper/2410.14660/) (2024)
- [Highly Efficient Self-Adaptive Reward Shaping for Reinforcement Learning](https://mlsanity.com/paper/2408.03029/) (2024)
- [Real-World Offline Reinforcement Learning from Vision Language Model Feedback](https://mlsanity.com/paper/2411.05273/) (2024)
- [Accelerating Exploration with Unlabeled Prior Data](https://mlsanity.com/paper/2311.05067/) (2023)
- [Reward Shaping for Happier Autonomous Cyber Security Agents](https://mlsanity.com/paper/2310.13565/) (2023)
- [Understanding the Complexity Gains of Single-Task RL with a Curriculum](https://mlsanity.com/paper/2212.12809/) (2022)
- [Rapidly Adapting Policies to the Real World via Simulation-Guided Fine-Tuning](https://mlsanity.com/paper/2502.02705/) (2025)
- [TempSamp-R1: Effective Temporal Sampling with Reinforcement Fine-Tuning for Video LLMs](https://mlsanity.com/paper/2509.18056/) (2025)
- [Learning Representations that Enable Generalization in Assistive Tasks](https://mlsanity.com/paper/2212.03175/) (2022)
- [When is Agnostic Reinforcement Learning Statistically Tractable?](https://mlsanity.com/paper/2310.06113/) (2023)
- [ReDit: Reward Dithering for Improved LLM Policy Optimization](https://mlsanity.com/paper/2506.18631/) (2025)
- [Automatic Environment Shaping is the Next Frontier in RL](https://mlsanity.com/paper/2407.16186/) (2024)
- [Assessing the Zero-Shot Capabilities of LLMs for Action Evaluation in RL](https://mlsanity.com/paper/2409.12798/) (2024)
- [Benchmarking Smoothness and Reducing High-Frequency Oscillations in Continuous Control Policies](https://mlsanity.com/paper/2410.16632/) (2024)
- [Online Preference-based Reinforcement Learning with Self-augmented Feedback from Large Language Model](https://mlsanity.com/paper/2412.16878/) (2024)
- [Automatic Reward Shaping from Confounded Offline Data](https://mlsanity.com/paper/2505.11478/) (2025)
- [Guaranteeing Control Requirements via Reward Shaping in Reinforcement Learning](https://mlsanity.com/paper/2311.10026/) (2023)
- [Combining Automated Optimisation of Hyperparameters and Reward Shape](https://mlsanity.com/paper/2406.18293/) (2024)
- [ARM-FM: Automated Reward Machines via Foundation Models for Compositional Reinforcement Learning](https://mlsanity.com/paper/2510.14176/) (2025)
- [FoMo Rewards: Can we cast foundation models as reward functions?](https://mlsanity.com/paper/2312.03881/) (2023)
- [Advancing Investment Frontiers: Industry-grade Deep Reinforcement Learning for Portfolio Optimization](https://mlsanity.com/paper/2403.07916/) (2024)
- [Reward Training Wheels: Adaptive Auxiliary Rewards for Robotics Reinforcement Learning](https://mlsanity.com/paper/2503.15724/) (2025)
- [Reinforcement Learning with Physics-Informed Symbolic Program Priors for Zero-Shot Wireless Indoor Navigation](https://mlsanity.com/paper/2506.22365/) (2025)
- [Annotations as Rollouts: Efficient and Scalable Reinforcement Learning for Video MLLMs](https://mlsanity.com/paper/2608.20492/) (2026)

## Abstract (arXiv)

Reinforcement learning provides an automated framework for learning behaviors from high-level reward specifications, but in practice the choice of reward function can be crucial for good results -- while in principle the reward only needs to specify what the task is, in reality practitioners often need to design more detailed rewards that provide the agent with some hints about how the task should be completed. The idea of this type of ``reward-shaping'' has been often discussed in the literature, and is often a critical part of practical applications, but there is relatively little formal characterization of how the choice of reward shaping can yield benefits in sample complexity. In this work, we build on the framework of novelty-based exploration to provide a simple scheme for incorporating shaped rewards into RL along with an analysis tool to show that particular choices of reward shaping provably improve sample efficiency. We characterize the class of problems where these gains are expected to be significant and show how this can be connected to practical algorithms in the literature. We confirm that these results hold in practice in an experimental evaluation, providing an insight into the mechanisms through which reward shaping can significantly improve the complexity of reinforcement learning while retaining asymptotic performance.