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

Abhishek GuptaAldo PacchianoYuexiang ZhaiSham M. KakadeSergey Levine

article2022NeurIPS100 citations

Establishes theoretical guarantees and algorithmic methods showing how reward shaping provably improves reinforcement learning sample complexity by reducing the effective state space and horizon dependence during exploration.

Listen

Reinforcement learning enables systems to learn effective decision-making policies from high-level objectives. However, standard exploration methods that explore unguided often require vast amounts of trial-and-error data, visiting every possible state in the worst case. In practical engineering, developers routinely bypass this inefficiency by shaping rewards—providing intermediate guidance to direct learning. While widely used in industry, reward shaping has historically lacked formal theoretical justification demonstrating how and when it improves sample efficiency without compromising final performance.

To address this gap, the article aims to mathematically formalize and empirically evaluate how domain knowledge provided through reward shaping reduces sample complexity in reinforcement learning. Specifically, the article demonstrates how shaped rewards can shrink the effective search space and reduce planning horizon dependencies while maintaining optimal asymptotic performance.

The authors approach the problem through a combination of theoretical regret analysis and empirical simulations. They introduce a modified model-based algorithm, named UCBVI-Shaped, which incorporates an approximate value function estimate through two key mechanisms: bonus scaling, which dampens exploration bonuses in unpromising regions, and value projection, which caps learned values to prevent over-optimism. The theoretical framework evaluates episodic decision processes under multiplicatively bounded reward shaping approximations, supported by online model selection methods to dynamically estimate approximation bounds. The theoretical claims are validated via numerical simulations across several tabular maze environments with varying degrees of corridor complexity and reward suboptimality.

The analysis reveals several key findings. First, integrating shaped rewards provably restricts the learning algorithm's search area to a much smaller effective state space, allowing it to quickly identify and permanently prune suboptimal branches. Second, bonus scaling accelerates convergence by replacing problem horizon factors with bounded value terms, reducing unnecessary exploration. Third, empirical benchmarks confirm that combining both projection and bonus scaling consistently yields the lowest cumulative regret, significantly outperforming unshaped baselines. Fourth, the magnitude of performance gains depends heavily on environment geometry: environments with irrelevant dead ends see dramatic sample efficiency improvements (effectively halving the search space in symmetric corridor tasks), whereas narrow single-path environments show more modest benefits. Finally, online model selection allows algorithms to adaptively estimate shaping accuracy bounds online without degrading performance.

These findings provide strong practical implications for engineering and research teams deploying reinforcement learning. System designers can formally rely on imperfect domain heuristics to drastically reduce trial-and-error costs, training times, and computational resource demands without risking convergence to suboptimal policies. This bridges the longstanding divide between theoretical exploration algorithms and heuristic reward design, confirming that engineered rewards are theoretically sound tools for sample-efficient learning.

Decision-makers and engineering teams should actively incorporate domain knowledge through shaped rewards, particularly in complex domains with large, branching state spaces containing many irrelevant pathways. When the exact accuracy of the shaping heuristic is uncertain, teams should deploy online model selection techniques rather than relying on brittle manual tuning. Further research is recommended to extend this theoretical framework from discrete, tabular settings to high-dimensional continuous control problems utilizing deep neural networks.

Confidence in these findings is high for tabular, discrete environments where value approximations satisfy multiplicative error bounds. However, readers should note that the current formal bounds assume tabular state representations and bounded reward errors. Caution is advised when directly extrapolating these theoretical sample complexity guarantees to large-scale deep reinforcement learning architectures where function approximation errors can introduce additional instability.

Harvard University Microsoft University of California Berkeley University of Washington engineering reward function reinforcement learning method reward shaping reward engineering sample complexity

arXiv: 2210.09579

Paper: Policy Invariance Under Reward Transformations: Theory and Application to Reward Shaping, Andrew Y. Ng et al. (1999). This foundational paper establishes potential-based reward shaping and proves policy invariance under reward transformations, providing the essential theoretical basis that the source analyzes in terms of sample complexity.
Paper: Unifying Count-Based Exploration and Intrinsic Motivation, Marc G. Bellemare et al. (2016). This work introduces pseudo-counts to connect count-based exploration with intrinsic rewards, establishing the novelty-based exploration framework upon which the source constructs its reward shaping analysis.
Paper: Exploration by Random Network Distillation, Yuri Burda et al. (2019). This paper presents Random Network Distillation as a practical novelty-based intrinsic reward mechanism for exploration in sparse-reward environments, which directly relates to the source's exploration framework.
Paper: R-MAX - A General Polynomial Time Algorithm for Near-Optimal Reinforcement Learning, R. Brafman et al. (2001). This paper establishes polynomial sample complexity bounds for reinforcement learning via optimistic exploration under uncertainty, setting the classical theoretical standards the source builds upon.
Paper: Approximately Optimal Approximate Reinforcement Learning, S. Kakade et al. (2002). This work provides core sample complexity analysis and conservative policy iteration principles that underpin theoretical guarantees in sample-efficient reinforcement learning.
Paper: Near-optimal Regret Bounds for Reinforcement Learning, Thomas Jaksch et al. (2008). This foundational study derives rigorous regret and sample complexity bounds in undiscounted MDPs using optimism in the face of uncertainty, framing the formal sample efficiency metrics unpacked in the source.

Paper: Demystifying Reinforcement Learning Post-Training of Language Models, Donovan Clay et al. (2026). This paper empirically and theoretically investigates how dense versus sparse reward signals interact with prior policy distributions during language model post-training, directly applying reward engineering principles to modern domains.
Paper: TRACE: Turn-level Reward Assignment via Credit Estimation for Long-Horizon Agents, Leitian Tao et al. (2026). This work develops turn-level intermediate credit assignment and potential-like reward signals for long-horizon agents, realizing practical reward engineering to mitigate sample complexity without external critics.
Paper: Automaton-Guided Curriculum Generation for Reinforcement Learning Agents, Yash Shukla et al. (2023). This research leverages automaton-guided task decomposition to automate curriculum and intermediate reward structures, providing an algorithmic extension to structured reward design for complex tasks.
Paper: Understanding Reasoning from Pretraining to Post-Training, Jingyan Shen et al. (2026). This study analyzes how reinforcement learning alters policies under verifiable reward signals across varying task difficulties, extending the study of learning efficiency and policy transformation.
Paper: Rewarding the Rare: Uniqueness-Aware RL for Creative Problem Solving in LLMs, Zhiyuan Hu et al. (2026). This work designs novelty- and uniqueness-aware reward engineering to prevent exploration collapse in LLM reasoning, continuing the exploration-driven reward modification themes explored in the source.

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

Abstract

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.

Topics

engineering reward function reinforcement learning method imitation learning actor critic average reward

Keywords

reward shaping reward engineering sample complexity reinforcement learning count-based exploration exploration bonuses regret analysis empirical Bernstein sample efficiency

1 Introduction
2 Related Work
3 Overview
4 The UCBVI-Shaped Algorithm
5 Analyzing UCBVI-Shaped
5.2 Proof Intuitions and Sketch for Theorem 5.2
6 Practical Considerations: Online Model Selection
7 Numerical Simulations
7.1 Does reward shaping help direct exploration over optimism under uncertainty?
7.2 How does the effectiveness of reward shaping vary across environments?
7.3 How does the suboptimality of reward shaping affect learning?
7.4 Is online UCBVI-Shaped able to infer b online without prior knowledge?
8 Discussion
References
Checklist

Knowls

Knowl 1 — Sample Complexity and Regret Bound of UCBVI-Shaped under Shaped Rewards
theoretical result
For an episodic finite-horizon Markov Decision Process $\mathcal{M} = (\mathcal{S}, \mathcal{A}, P^*, r, H)$ with state space $\mathcal{S}$ , action space $\mathcal{A}$ , horizon $H$ , reward function $r(s,a) \in [0, 1]$ , and a reward shaping function $\tilde{V}_h: \mathcal{S} \to \mathbb{R}$ satisfying $V_h^*(s) \le \beta \tilde{V}_h(s)$ for some known factor $\beta \ge 1$ , the cumulative regret of the UCBVI-Shaped algorithm over $T$ episodes is bounded with probability at least $1 - 6\delta$ by:

$\text{Regret}(T) = \sum_{t=1}^T \left( V^*(s_0) - V^{\pi_t}(s_0) \right) = \mathcal{O}\left( \min_{\Delta > 0} \left( H \beta \tilde{V}^{\max} \sqrt{|\mathcal{S} \setminus \text{PathPseudoSub}_\Delta| |\mathcal{A}| T \ln \frac{\tilde{V}^{\max}|\mathcal{S}||\mathcal{A}|T}{\delta}} + \beta^2 (\tilde{V}^{\max})^2 H^{1/2} |\text{BoundaryPseudoSub}_\Delta|^{1/2} \ln\frac{\tilde{V}^{\max}|\mathcal{S}||\mathcal{A}|T}{\delta} \cdot \min(A(\Delta), B(\Delta)) \right) \right)$

where $\tilde{V}^{\max} = \max_{s, h} \tilde{V}_h(s)$ , $A(\Delta) = \frac{|\mathcal{S}|^{1/2}|\mathcal{A}|^{1/2}}{\Delta}$ , and $B(\Delta) = \frac{\beta \tilde{V}^{\max} H^{1/2} |\text{BoundaryPseudoSub}_\Delta|^{1/2}}{\Delta^2}$ .

The set $\text{PathPseudoSub}_\Delta$ consists of all states reachable only via $\Delta$ -pseudosuboptimal state-action pairs, and $\text{BoundaryPseudoSub}_\Delta$ is the set of $\Delta$ -pseudosuboptimal state-action pairs whose states are outside $\text{PathPseudoSub}_\Delta$ . This result demonstrates that the leading term of the regret scales not with the ambient state space size $|\mathcal{S}|$ , but with the effective pruned state space $|\mathcal{S} \setminus \text{PathPseudoSub}_\Delta|$ , and replaces the worst-case $H^2$ factor with $H \beta \tilde{V}^{\max}$ .
Knowl 2 — UCBVI-Shaped Algorithm
algorithm
UCBVI-Shaped is an episodic model-based reinforcement learning algorithm that leverages a multiplicatively bounded shaped value function $\tilde{V}_h(s)$ and a bounding scalar $\beta \ge 1$ to prune suboptimal regions and scale exploration bonuses. At each episode $t = 1, \dots, T$ , it updates empirical transition probabilities $\hat{P}_t(s' \mid s, a) = \frac{N_h^t(s, a, s')}{N_h^t(s, a)}$ based on historical visitation counts $N_h^t(s, a)$ and transition counts $N_h^t(s, a, s')$ . It then performs backward value iteration with shaped bonuses and value function clipping before executing the greedy policy.
Input: Reward function $r$ , confidence parameter $\delta \in (0,1)$ , horizon $H$ , state space $\mathcal{S}$ , action space $\mathcal{A}$ , shaping function $\tilde{V}_h$ , scale factor $\beta \ge 1$
for episode $t = 1, \dots, T$ do
    for each step $h = 0, \dots, H-1$ and $(s, a) \in \mathcal{S} \times \mathcal{A}$ do
        Compute empirical transition model $\hat{P}_t(s' \mid s, a) = \frac{N_h^t(s,a,s')}{N_h^t(s,a)}$ for all $s' \in \mathcal{S}$
        Compute shaped bonus $b_h^t(s,a) = \min\left( 16\beta \sqrt{\frac{\hat{\mathbb{E}}_{s' \sim \hat{P}_t(\cdot|s,a)}[\tilde{V}_{h+1}^2(s')] \ln(2|\mathcal{S}||\mathcal{A}|/\delta)}{N_h^t(s,a)}} + \frac{12\beta \tilde{V}^{\max}}{N_h^t(s,a)} \ln\frac{2|\mathcal{S}||\mathcal{A}|t}{\delta}, 2\beta \tilde{V}^{\max} \right)$
    end for
    Initialize $\hat{V}_H^t(s) = 0$ for all $s \in \mathcal{S}$
    for step $h = H-1, \dots, 0$ backward do
        for each $(s, a) \in \mathcal{S} \times \mathcal{A}$ do
             $\hat{Q}_h^t(s, a) = \min\left( r(s, a) + b_h^t(s, a) + \sum_{s'} \hat{P}_t(s' \mid s, a) \hat{V}_{h+1}^t(s'), H \right)$
        end for
        for each $s \in \mathcal{S}$ do
             $\hat{V}_h^t(s) = \min\left( \max_{a \in \mathcal{A}} \hat{Q}_h^t(s, a), \beta \tilde{V}_h(s) \right)$
             $\pi_h^t(s) = \arg\max_{a \in \mathcal{A}} \hat{Q}_h^t(s, a)$
        end for
    end for
    Execute policy $\pi^t = (\pi_0^t, \dots, \pi_{H-1}^t)$ to collect trajectory $(s_0^t, a_0^t, \dots, s_{H-1}^t, a_{H-1}^t)$
    Update counts $N_h^{t+1}(s, a)$ and $N_h^{t+1}(s, a, s')$
end for
Knowl 3 — Pseudosuboptimal, Path-Pseudosuboptimal, and Boundary-Pseudosuboptimal State Spaces
definition
Let $\mathcal{M} = (\mathcal{S}, \mathcal{A}, P^*, r, H)$ be an episodic MDP, $V_h^*(s)$ be the optimal value function, and $\tilde{V}_h: \mathcal{S} \to \mathbb{R}$ be an approximate value function satisfying $V_h^*(s) \le \beta \tilde{V}_h(s)$ for $\beta \ge 1$ . The surrogate upper $Q$ -function induced by $\tilde{V}$ is defined as:

$\tilde{Q}_h^u(s,a) := \mathbb{E}_{s' \sim P^*(\cdot \mid s,a)} \left[ r(s,a) + \beta \tilde{V}_{h+1}(s') \right]$

For any gap parameter $\Delta > 0$ :
1. $\Delta$ -pseudosuboptimal state-action pairs: $\text{PseudoSub}_\Delta := \left\{ (s, a) \in \mathcal{S} \times \mathcal{A} \mid V_h^*(s) \ge \Delta + \tilde{Q}_h^u(s,a) \right\}$
2. $\Delta$ -path-pseudosuboptimal states: $\text{PathPseudoSub}_\Delta := \left\{ s \in \mathcal{S} \mid \text{all feasible paths from initial states to } s \text{ intersect } \text{PseudoSub}_\Delta \right\}$
3. $\Delta$ -boundary-pseudosuboptimal state-action pairs: $\text{BoundaryPseudoSub}_\Delta := \left\{ (s, a) \in \text{PseudoSub}_\Delta \mid s \notin \text{PathPseudoSub}_\Delta \right\}$
States in $\text{PathPseudoSub}_\Delta$ can only be reached by executing a $\Delta$ -pseudosuboptimal action. Consequently, once state-action pairs in $\text{BoundaryPseudoSub}_\Delta$ are identified as suboptimal, an optimistic learner projecting values with $\beta \tilde{V}$ ceases to visit any state in $\text{PathPseudoSub}_\Delta$ .
Knowl 4 — Multiplicatively Bounded Reward Shaping Assumption
assumption
In an episodic Markov Decision Process $\mathcal{M} = (\mathcal{S}, \mathcal{A}, P^*, r, H)$ , the quality of the shaping value function $\tilde{V}_h : \mathcal{S} \to \mathbb{R}$ is assumed to satisfy a multiplicative upper-sandwich condition with respect to the optimal value function $V_h^*(s)$ :

$V_h^*(s) \le \beta \tilde{V}_h(s), \quad \forall s \in \mathcal{S}, \; h \in [H]$

for a finite multiplicative factor $\beta \ge 1$ . The shaping function is allowed to underestimate the optimal value at certain states (i.e., $\tilde{V}_h(s) < V_h^*(s)$ ) provided the scalar $\beta$ restores the upper bound uniformly.
Knowl 5 — Shaped Empirical Bernstein Exploration Bonus
equation
In UCBVI-Shaped, the exploration bonus $b_h^t(s,a)$ for state-action pair $(s,a)$ at episode $t$ and step $h$ is constructed from the empirical second moment of the shaping term $\tilde{V}_{h+1}$ under the empirical transition distribution $\hat{P}_t(\cdot \mid s,a)$ :

$b_h^t(s,a) = \min\left( 16\beta \sqrt{\frac{\hat{\mathbb{E}}_{s' \sim \hat{P}_t(\cdot \mid s,a)}[\tilde{V}_{h+1}^2(s')] \ln\left(\frac{2|\mathcal{S}||\mathcal{A}|}{\delta}\right)}{N_h^t(s,a)}} + \frac{12\beta \tilde{V}^{\max}}{N_h^t(s,a)} \ln\left(\frac{2|\mathcal{S}||\mathcal{A}|t}{\delta}\right), \; 2\beta \tilde{V}^{\max}\right)$

where $\tilde{V}^{\max} = \max_{s, h} \tilde{V}_h(s)$ , $N_h^t(s,a)$ is the state-action visitation count up to episode $t-1$ , $\beta \ge 1$ is the shaping quality factor, and $\delta \in (0, 1)$ is the confidence parameter.
Knowl 6 — Optimism of Value and Action-Value Estimates in UCBVI-Shaped
theoretical result
Let $\mathcal{M} = (\mathcal{S}, \mathcal{A}, P^*, r, H)$ be an episodic MDP with $h$ -indexed state spaces, and let $\hat{V}_h^t$ and $\hat{Q}_h^t$ be the empirical value and action-value functions computed by Value Iteration with Projection using the shaped exploration bonus $b_h^t(s,a)$ and upper clipping at $\beta \tilde{V}_h(s)$ where $V_h^*(s) \le \beta \tilde{V}_h(s)$ . Then, with probability at least $1 - \delta$ , optimism is maintained across all rounds and time steps:

$\hat{V}_0^t(s_0) \ge V_0^*(s_0), \quad \forall s_0 \in \mathcal{S}$ $\hat{Q}_h^t(s,a) \ge Q_h^*(s,a), \quad \forall (s,a) \in \mathcal{S} \times \mathcal{A}, \; h \in [H], \; t \in \mathbb{N}$
Knowl 7 — Online Model Selection for Unknown Shaping Parameter $\beta$
model/method
When the multiplicative bounding factor $\beta \ge 1$ for a shaping function $\tilde{V}$ is unknown a priori, it can be learned online without sacrificing regret guarantees by formulating the problem as online model selection over a discrete candidate set $\{\beta_1, \beta_2, \dots, \beta_N\}$ . A meta-algorithm (such as Stochastic CORRAL or RegretBalancing) maintains and updates a probability distribution over $N$ concurrent instances of UCBVI-Shaped $(\beta_i)$ using the observed episodic returns as the feedback signal. This allows the learner to automatically select the tightest valid $\beta$ factor online.
Knowl 8 — Empirical Benefits of Value Projection and Bonus Scaling in Tabular Mazes
empirical result
In tabular maze navigation tasks (Open Gridworld, Single Corridor, and Double Corridor) with sparse goal rewards ( $r=1$ at the goal, $r=0$ elsewhere), empirical evaluations demonstrate the following:
1. The full UCBVI-Shaped algorithm (incorporating both value projection $\hat{V} \le \beta \tilde{V}$ and shaped bonus scaling) achieves the lowest cumulative regret across all environments compared to standard UCBVI.
2. In ablation tests, UCBVI-Shaped-P (only value projection) outperforms UCBVI-Shaped-BS (only bonus scaling), while both variants outperform unshaped UCBVI.
3. Combining value projection with bonus scaling provides a synergistic reduction in exploration of suboptimal regions, leading to faster policy convergence.
Knowl 9 — Empirical Sensitivity of UCBVI-Shaped to State Space Topology and Shaping Quality
empirical result
Simulations across maze environments show that the efficiency gains of UCBVI-Shaped depend strongly on environment topology and the bounding factor $\beta$ :
1. In environments with extensive suboptimal branches (e.g., Double Corridor where the goal is on one side and numerous irrelevant states are on the other), UCBVI-Shaped achieves dramatic sample complexity reductions by pruning entire subtrees of the state space.
2. In linear topologies (e.g., Single Corridor) where exploration is constrained to a single trajectory, gains over standard UCBVI are smaller because fewer states can be path-pruned.
3. Moderate shaping suboptimality (e.g., $\beta \in \{1.2, 1.5\}$ ) maintains near-optimal sample efficiency, whereas large values of $\beta$ (severe value overestimation or corruption) degrade performance toward standard uninformed UCBVI.

Coverage note — No substantial contributed theoretical or empirical material from the paper was omitted; low-order constants in the extended appendix regret theorem (Theorem B.11) were omitted in favor of the full main text theorem (Theorem 5.2).

References

1.A. Agarwal, H. Luo, B. Neyshabur, and R. E. Schapire. Corralling a band of bandit algorithms. In Conference on Learning Theory, pages 12–38. PMLR, 2017.
2.A. Agarwal, N. Jiang, S. M. Kakade, and W. Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, 2019.
3.A. Agarwal, M. Henaff, S. Kakade, and W. Sun. Pc-pg: Policy cover directed exploration for provable policy gradient learning. Advances in Neural Information Processing Systems, 33: 13399–13412, 2020.
4.S. Agrawal and R. Jia. Posterior sampling for reinforcement learning: worst-case regret bounds. arXiv preprint arXiv:1705.07041, 2017.
5.O. M. Andrychowicz, B. Baker, M. Chociej, R. Jozefowicz, B. McGrew, J. Pachocki, A. Petron, M. Plappert, G. Powell, A. Ray, et al. Learning dexterous in-hand manipulation. The International Journal of Robotics Research, 39(1):3–20, 2020.
6.P. Auer, T. Jaksch, and R. Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
7.A. Ayoub, Z. Jia, C. Szepesvari, M. Wang, and L. Yang. Model-based reinforcement learning with value-targeted regression. In International Conference on Machine Learning, pages 463–474. PMLR, 2020.
8.M. G. Azar, I. Osband, and R. Munos. Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning, pages 263–272. PMLR, 2017.
9.Y. Bai, T. Xie, N. Jiang, and Y.-X. Wang. Provably efficient q-learning with low switching cost. Advances in Neural Information Processing Systems, 32, 2019.
10.M. Bellemare, S. Srinivasan, G. Ostrovski, T. Schaul, D. Saxton, and R. Munos. Unifying count-based exploration and intrinsic motivation. In Advances in Neural Information Processing Systems, pages 1471–1479, 2016.
11.C. Berner, G. Brockman, B. Chan, V. Cheung, P. Dąbiak, C. Dennison, D. Farhi, Q. Fischer, S. Hashme, C. Hesse, et al. Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv:1912.06680, 2019.
12.Y. Burda, H. Edwards, A. Storkey, and O. Klimov. Exploration by random network distillation. arXiv preprint arXiv:1810.12894, 2018.
13.Q. Cai, Z. Yang, C. Jin, and Z. Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pages 1283–1294. PMLR, 2020.
14.C. Cheng, A. Kolobov, and A. Swaminathan. Heuristic-guided reinforcement learning. In M. Ranzato, A. Beygelzimer, Y. N. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 13550–13563, 2021. URL https://proceedings.neurips.cc/paper/2021/hash/70d31b87bd021441e5e6bf23eb84a306-Abstract.html.
15.A. Cutkosky, C. Dann, A. Das, C. Gentile, A. Pacchiano, and M. Purohit. Dynamic balancing for model selection in bandits and rl. In International Conference on Machine Learning, pages 2276–2285. PMLR, 2021.
16.C. Dann, T. V. Marinov, M. Mohri, and J. Zimmert. Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34:1–12, 2021.
17.Y. Efroni, N. Merlis, M. Ghavamzadeh, and S. Mannor. Tight regret bounds for model-based reinforcement learning with greedy policies. Advances in Neural Information Processing Systems, 32, 2019.
18.A. Faust, K. Oslund, O. Ramirez, A. G. Francis, L. Tapia, M. Fiser, and J. Davidson. PRM-RL: long-range robotic navigation tasks by combining reinforcement learning and sampling-based planning. In 2018 IEEE International Conference on Robotics and Automation, ICRA 2018, Brisbane, Australia, May 21-25, 2018, pages 5113–5120. IEEE, 2018. doi: 10.1109/ICRA.2018.8461096. URL https://doi.org/10.1109/ICRA.2018.8461096.
19.D. A. Freedman. On tail probabilities for martingales. the Annals of Probability, pages 100–118, 1975.
20.R. Fruit, M. Pirotta, A. Lazaric, and R. Ortner. Efficient bias-span-constrained exploration-exploitation in reinforcement learning. In International Conference on Machine Learning, pages 1578–1586. PMLR, 2018.
21.N. Golowich and A. Moitra. Can q-learning be improved with advice? In Conference on Learning Theory, pages 4548–4619. PMLR, 2022.
22.R. Houthooft, X. Chen, Y. Duan, J. Schulman, F. De Turck, and P. Abbeel. Vime: Variational information maximizing exploration. Advances in neural information processing systems, 29, 2016.
23.T. Jaksch, R. Ortner, and P. Auer. Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research, 11:1563–1600, 2010.
24.C. Jin, Z. Allen-Zhu, S. Bubeck, and M. I. Jordan. Is q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
25.C. Jin, Z. Yang, Z. Wang, and M. I. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137–2143. PMLR, 2020.
26.S. M. Kakade et al. On the sample complexity of reinforcement learning. PhD thesis, University College London, 2003.
27.G. Li, L. Shi, Y. Chen, Y. Gu, and Y. Chi. Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34, 2021.
28.K. Li, A. Gupta, A. Reddy, V. H. Pong, A. Zhou, J. Yu, and S. Levine. Mural: Meta-learning uncertainty-aware rewards for outcome-driven reinforcement learning. In International Conference on Machine Learning, pages 6346–6356. PMLR, 2021.
29.A. Maurer and M. Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.3740, 2009.
30.P. Ménard, O. D. Domingues, X. Shang, and M. Valko. Ucb momentum q-learning: Correcting the bias without forgetting. In International Conference on Machine Learning, pages 7609–7618. PMLR, 2021.
31.A. Y. Ng, D. Harada, and S. Russell. Policy invariance under reward transformations: Theory and application to reward shaping. In ICML, volume 99, pages 278–287, 1999.
32.A. Pacchiano, P. Ball, J. Parker-Holder, K. Choromanski, and S. Roberts. On optimism in model-based reinforcement learning. arXiv preprint arXiv:2006.11911, 2020.
33.A. Pacchiano, C. Dann, C. Gentile, and P. Bartlett. Regret bound balancing and elimination for model selection in bandits and rl. arXiv preprint arXiv:2012.13045, 2020.
34.A. Pacchiano, M. Phan, Y. Abbasi Yadkori, A. Rao, J. Zimmert, T. Lattimore, and C. Szepesvari. Model selection in contextual stochastic bandit problems. Advances in Neural Information Processing Systems, 33:10328–10337, 2020.
35.A. Pacchiano, P. Ball, J. Parker-Holder, K. Choromanski, and S. Roberts. Towards tractable optimism in model-based reinforcement learning. In Uncertainty in Artificial Intelligence, pages 1413–1423. PMLR, 2021.
36.D. Pathak, P. Agrawal, A. A. Efros, and T. Darrell. Curiosity-driven exploration by self-supervised prediction. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pages 16–17, 2017.
37.R. Raileanu and T. Rocktäschel. Ride: Rewarding impact-driven exploration for procedurally-generated environments. In International Conference on Learning Representations, 2020. URL https://openreview.net/forum?id=rkg-TJBFPB.
38.D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):484–489, 2016.
39.D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, et al. Mastering the game of go without human knowledge. nature, 550 (7676):354–359, 2017.
40.B. C. Stadie, S. Levine, and P. Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv preprint arXiv:1507.00814, 2015.
41.H. Tang, R. Houthooft, D. Foote, A. Stooke, O. X. Chen, Y. Duan, J. Schulman, F. DeTurck, and P. Abbeel. # exploration: A study of count-based exploration for deep reinforcement learning. In Advances in neural information processing systems, pages 2753–2762, 2017.
42.H. Van Seijen, M. Fatemi, J. Romoff, R. Laroche, T. Barnes, and J. Tsang. Hybrid reward architecture for reinforcement learning. In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL https://proceedings.neurips.cc/paper/2017/file/1264a061d82a2edae1574b07249800d6-Paper.pdf.
43.A. S. Vezhnevets, S. Osindero, T. Schaul, N. Heess, M. Jaderberg, D. Silver, and K. Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 3540–3549. JMLR. org, 2017.
44.O. Vinyals, I. Babuschkin, W. M. Czarnecki, M. Mathieu, A. Dudzik, J. Chung, D. H. Choi, R. Powell, T. Ewalds, P. Georgiev, et al. Grandmaster level in starcraft ii using multi-agent reinforcement learning. Nature, 575(7782):350–354, 2019.
45.Y. Wang, R. Wang, S. S. Du, and A. Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv:1912.04136, 2019.
46.K. Yang, L. Yang, and S. Du. Q-learning with logarithmic regret. In International Conference on Artificial Intelligence and Statistics, pages 1576–1584. PMLR, 2021.
47.L. Yang and M. Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pages 6995–7004. PMLR, 2019.
48.L. Yang and M. Wang. Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746–10756. PMLR, 2020.
49.Z. Yang, C. Jin, Z. Wang, M. Wang, and M. I. Jordan. On function approximation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprint arXiv:2011.04622, 2020.
50.D. Ye, G. Chen, W. Zhang, S. Chen, B. Yuan, B. Liu, J. Chen, Z. Liu, F. Qiu, H. Yu, Y. Yin, B. Shi, L. Wang, T. Shi, Q. Fu, W. Yang, L. Huang, and W. Liu. Towards playing full moba games with deep reinforcement learning. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 621–632. Curran Associates, Inc., 2020. URL https://proceedings.neurips.cc/paper/2020/file/06d5ae105ea1bea4d800bc96491876e9-Paper.pdf.
51.T. Yu, D. Quillen, Z. He, R. Julian, K. Hausman, C. Finn, and S. Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning. In L. P. Kaelbling, D. Kragic, and K. Sugiura, editors, 3rd Annual Conference on Robot Learning, CoRL 2019, Osaka, Japan, October 30 - November 1, 2019, Proceedings, volume 100 of Proceedings of Machine Learning Research, pages 1094–1100. PMLR, 2019. URL http://proceedings.mlr.press/v100/yu20a.html.
52.A. Zanette and E. Brunskill. Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference on Machine Learning, pages 7304–7312. PMLR, 2019.
53.A. Zanette, D. Brandfonbrener, E. Brunskill, M. Pirotta, and A. Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference on Artificial Intelligence and Statistics, pages 1954–1964. PMLR, 2020.
54.Y. Zhai, C. Baek, Z. Zhou, J. Jiao, and Y. Ma. Computational benefits of intermediate rewards for goal-reaching policy learning. Journal of Artificial Intelligence Research, 73:847–896, 2022.
55.Z. Zhang, Y. Zhou, and X. Ji. Almost optimal model-free reinforcement learningvia reference-advantage decomposition. Advances in Neural Information Processing Systems, 33:15198–15207, 2020.
56.D. Zhou, J. He, and Q. Gu. Provably efficient reinforcement learning for discounted mdps with feature mapping. In International Conference on Machine Learning, pages 12793–12802. PMLR, 2021.

Citation

MLA

Gupta, A., et al. “Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity”. Advances in Neural Information Processing Systems, vol. 35, 2022, pp. 15281–95, https://proceedings.neurips.cc/paper_files/paper/2022/file/6255f22349da5f2126dfc0b007075450-Paper-Conference.pdf.

APA

Gupta, A., Pacchiano, A., Zhai, Y., Kakade, S., & Levine, S. (2022). Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity. Advances in Neural Information Processing Systems, 35, 15281–15295. https://proceedings.neurips.cc/paper_files/paper/2022/file/6255f22349da5f2126dfc0b007075450-Paper-Conference.pdf

Chicago

Gupta, A., A. Pacchiano, Y. Zhai, S. Kakade, and S. Levine. 2022. “Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity”. Advances in Neural Information Processing Systems 35: 15281–95. https://proceedings.neurips.cc/paper_files/paper/2022/file/6255f22349da5f2126dfc0b007075450-Paper-Conference.pdf.

Harvard

Gupta, A. et al. (2022) “Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity”, Advances in Neural Information Processing Systems. Curran Associates, Inc., pp. 15281–15295. Available at: https://proceedings.neurips.cc/paper_files/paper/2022/file/6255f22349da5f2126dfc0b007075450-Paper-Conference.pdf.

Vancouver

1. Gupta A, Pacchiano A, Zhai Y, Kakade S, Levine S (2022) Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity. In: Advances in Neural Information Processing Systems. Curran Associates, Inc., pp 15281–15295

BibTeX

@inproceedings{gupta2022unpacking,
  title = {Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity},
  author = {Gupta, Abhishek and Pacchiano, Aldo and Zhai, Yuexiang and Kakade, Sham and Levine, Sergey},
  year = {2022},
  booktitle = {Advances in Neural Information Processing Systems},
  publisher = {Curran Associates, Inc.},
  volume = {35},
  pages = {15281-15295},
  url = {https://proceedings.neurips.cc/paper_files/paper/2022/file/6255f22349da5f2126dfc0b007075450-Paper-Conference.pdf}
}

Metadata:DOI registry

Access the Paper

This paper is available from its original source. Click below to access the PDF.

Open PDF

License: Published with permission

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

Abstract

Topics

Keywords

Table of Contents

Knowls

Knowl 1 — Sample Complexity and Regret Bound of UCBVI-Shaped under Shaped Rewards

Knowl 2 — UCBVI-Shaped Algorithm

Knowl 3 — Pseudosuboptimal, Path-Pseudosuboptimal, and Boundary-Pseudosuboptimal State Spaces

Knowl 4 — Multiplicatively Bounded Reward Shaping Assumption

Knowl 5 — Shaped Empirical Bernstein Exploration Bonus

Knowl 6 — Optimism of Value and Action-Value Estimates in UCBVI-Shaped

Knowl 7 — Online Model Selection for Unknown Shaping Parameter $\beta$

Knowl 8 — Empirical Benefits of Value Projection and Bonus Scaling in Tabular Mazes

Knowl 9 — Empirical Sensitivity of UCBVI-Shaped to State Space Topology and Shaping Quality

References

Citation

BibTeX

Access the Paper