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

1 Introduction

• In the motivating RL setting, random exploration can be exponentially expensive, while theoretical work has sought smarter strategies with polynomial dependence on state-space size.The cited approaches commonly use exploration bonuses to prioritize rarely visited regions.Source: §1 · p. 1
• Practitioners often prefer heuristic reward shaping, while formal analyses of shaping have largely focused on policy invariance or empirical observations.The paper notes that general-purpose exploration may require visiting every state in the worst case, which can remain impractical even with polynomial sample complexity.Source: §1 · p. 2
• The analysis uses UCBVI-Shaped to study how shaped rewards can direct optimism more effectively than uninformed exploration while maintaining asymptotic performance.The algorithm incorporates shaping into optimism-based exploration, and the paper develops a regret-analysis framework for it.Source: §1 · p. 2
• The analysis assumes shaping is a potentially suboptimal approximation of the optimal value function, bounded multiplicatively by a factor β.Source: §1 · p. 2
• The analysis identifies two mechanisms: scaling bonuses with βeV rather than a horizon-based approximation and projecting values to hasten convergence and detect suboptimal actions.Together, these mechanisms can support faster bonus decay and pruning of parts of the state space.Source: §1 · p. 2
• Reward shaping can improve sample efficiency through gains in both state-space- and horizon-dependent terms.The reported benefits depend on shaping quality; the analysis examines bonus scaling and value projection.Source: §1 · p. 2

Regret Analysis in Finite Horizon Episodic Tabular MDPs

• The analysis is model-based and resembles UCBVI’s setting, but adds a multiplicatively bounded approximation of V⋆ and a truncated-interval assumption to obtain an effective-state-space dependence.Unlike the cited regret guarantees that scale with the number of states, the authors’ bound may depend on a smaller effective state space.Source: §2 · pp. 2–3

Regret Analysis with Linear Function Approximation

• Linear-function-approximation work reduces regret dependence to feature dimension or another intrinsic complexity measure; this paper instead asks whether approximate knowledge of V⋆ speeds learning.Source: §2 · p. 3

Practical Reward Design and Reward Shaping

• Practical reward design often uses handcrafted, potentially biased rewards, whereas uninformed exploration methods seek broad state visitation; this paper studies using domain knowledge to direct exploration.Relative to Cheng et al. [15], the stated distinction is reducing effective state-space size rather than effective horizon.Source: §2 · p. 3

3 Overview

• In the maze example, uninformed exploration covers both directions from the starting point, while effective shaping can focus search on the goalward half.The shaped value landscape is shown by color, with green for smaller values and red for larger values.Source: Figure 1 · p. 3, §3 · p. 4
• UCBVI-Shaped modifies UCBVI through bonus scaling based on eV and value projection that clips the empirical value function using a shaping-based upper bound.The overview links bonus scaling with reduced overoptimism and horizon dependence, and projection with pruning unnecessary state-space elements.Source: §3 · p. 4
• When Sremain is much smaller than S, the UCBVI-Shaped regret bound can be substantially smaller than the corresponding full-state UCBVI bound.Sremain contains states that the shaping information was insufficient to rule out; B(eV,M) is a time-agnostic complexity measure depending on the MDP and shaping quality.Source: §3 · p. 4
• The analysis assumes a shaping estimate bounded multiplicatively relative to V⋆ by β, and assumes states reachable at different times are disjoint.The shaping estimate may be below V⋆ for some states; the paper states that β can be learned online.Source: §3 · p. 4
• The paper introduces pseudosuboptimal and path-pseudosuboptimal states to quantify effective state-space size, and says sufficiently good shaping can replace a leading H term with max_s βeV(s).Source: §3 · p. 4

• UCBVI-Shaped changes UCBVI in two ways: scaling exploration bonuses with eV and projecting empirical values via clipping.Source: §4 · p. 5
• Each round estimates transitions from prior data, computes a reward bonus, runs projected value iteration, and uses its returned policy as π_t.Source: §4 · p. 5
• Value projection clips empirical values using an upper bound based on βeV; online model selection can infer β rather than requiring it beforehand.Source: §4 · p. 5

5 Analyzing UCBVI-Shaped

• UCBVI-Shaped clips empirical value functions at β eV and modifies its bonus, yet its Q and V estimates remain optimistic.The bonus scaling uses the empirical second moment of eV, while clipping helps the estimates converge faster and detect suboptimal actions.Source: §5 · p. 6

5.1 Pruning of the State Space

• Path-pseudosuboptimal states are reachable only through ∆-pseudosuboptimal state-action pairs, and UCBVI-Shaped can stop visiting them after identifying boundary pairs.Once BoundaryPseudoSub∆ has been visited enough, states in PathPseudoSub∆ are no longer visited; the regret bound can therefore avoid dependence on their number.Source: §5.1 · pp. 6–7
• Theorem 5.2 bounds regret using the states outside PathPseudoSub∆ and a boundary-dependent term, with horizon dependence scaling as Hβ eV max.When |BoundaryPseudoSub∆| is small, the state dependence in the second term may be logarithmic in |S|, at a quadratic 1/∆² cost.Source: §5.1 · p. 7

5.2 Proof Intuitions and Sketch for Theorem 5.2

• The proof splits regret between trajectories intersecting pruned or pseudosuboptimal pairs and trajectories that avoid them, bounding the latter through |S\PathPseudoSub∆|.The pruned-region terms include a 1/∆² contribution with logarithmic state dependence.Source: §5.1 · p. 7, §5.2 · p. 8

6 Practical Considerations: Online Model Selection

• Stochastic CORRAL or RegretBalancing can jointly infer β from N candidate values and learn the corresponding UCBVI-Shaped value function online.The paper states that these techniques yield meaningful regret guarantees and provides pseudocode in Appendix B.4.Source: §6 · p. 8

7 Numerical Simulations

• The simulations use deterministic tabular maze environments with reward 1 at the goal sink and 0 elsewhere, and vary shaping quality by scaling the optimal value function per state.The environments include open gridworld, single corridor, and double corridor layouts.Source: §7 · p. 8, Figure 3 · p. 9

7.1 Does reward shaping help direct exploration over optimism under uncertainty?

• Across all three environments, UCBVI-Shaped with projection and bonus scaling performs most favorably, typically followed by projection-only, bonus-scaling-only, and standard UCBVI.The comparison uses cumulative regret with imperfect shaping at β = {1.5,1.9}.Source: §7.1 · p. 9, Figure 4 · p. 9

7.2 How does the effectiveness of reward shaping vary across environments?

• UCBVI-Shaped is more effective in the double corridor with irrelevant paths than in the single corridor, where exploration is directed the same way.The authors suggest larger benefits when shaping can rule out an entire part of the exploration space.Source: §7.2 · pp. 9–10, Figure 6 · p. 10

7.3 How does the suboptimality of reward shaping affect learning?

• Open-path environments show little degradation until shaping is very suboptimal, whereas suboptimal shaping along the few corridor routes significantly hampers progress.Figure 5 reports little difference at β = 1.2,1.5, but degradation at very large β.Source: Figure 5 · p. 9, §7.3 · p. 10

7.4 Is online UCBVI-Shaped able to infer β online without prior knowledge?

• Online model selection with Stochastic CORRAL achieves results comparable to knowing β beforehand, with performance degrading as β increases.The reported pattern suggests practicality for moderate levels of value corruption.Source: §7.4 · p. 10

8 Discussion

• Figure 7 concerns the performance of online model selection in UCBVI-Shaped.The supplied discussion passage identifies the figure's topic but gives no further result.Source: Figure 7 · p. 10
• Incorporating shaped rewards into modified UCBVI can prune state space and sharpen optimism, reducing regret-bound dependence on state-space size and horizon under suitable shaping and MDP conditions.The paper states that this can yield significant sample-complexity benefits while retaining asymptotic performance.Source: §8 · p. 10
• The analysis modifies UCBVI through bonus changes and value-function projection to use reward shaping in exploration.The discussion frames this as a step toward formally analyzing shaping rather than keeping sample-complexity analysis reward-agnostic.Source: §8 · pp. 10–11

A Full Proofs

• A refined concentration argument controls dependence on the support size of the true transition distribution, enabling final bounds to depend on the effective state space.The proof uses an ε-net restricted to the support of the true transition distribution.Source: A Full Proofs · pp. 17–18

A.1 Proof of Lemma 5.1

• The proof establishes optimism for all state-action pairs, invoking the inductive optimism assumption and inequalities associated with Corollary A.2 and Corollary A.3 applied to the definition of bt.Source: §A.1 · pp. 18–19

B Supporting Results for Section 5.1

• High-probability empirical-Q bounds, together with optimism, limit selections of pseudo-suboptimal pairs and visits to paths containing them.The appendix establishes bounds for all Δ in [0,1] and all T; the supplied passages omit the bound formulas.Source: B Supporting Results for Section 5.1 · pp. 19–20

B.1 Full Proof of Theorem 5.2

• UCBVI-Shaped’s full regret guarantee is refined to depend logarithmically on the state space at the cost of quadratic dependence on Δ².The appendix states the full version of Theorem 5.2; the supplied passage does not include its bound’s formula.Source: §B.1 · pp. 28–29

B.2 Generalizations

• For action-dependent shaping, clipping preserves optimism under the stated optimal-action condition and yields UCBVI-Shaped regret guarantees that recover min-max rates from.The argument restricts visits to actions whose shaped values meet the optimal-value threshold.Source: §B.2 · p. 30
• Clipped StrongEuler operates on a pruned state-action space and recovers the instance-dependent results of.The result can also be stated using return gaps over the effective state space.Source: §B.2 · p. 31

B.3 Connections with instance dependent rates for reinforcement learning

• Rates can improve when both gaps and the effective state space are small, and this space may be much smaller than the original state space.The authors identify state pruning as the main innovation behind these improvements.Source: §B.3 · p. 32

B.4 Model Selection

• A parameter-free version can select among β guesses initialized on an exponential grid, with Corral learning rates based on a putative regret bound.The appendix suggests guesses from β₁ = 1 through β_N = 2^N; the supplied text does not fully specify the putative-bound expression.Source: §B.4 · p. 32
• The appendix derives regret guarantees for Algorithm 1 using Stochastic CORRAL and Regret Balancing, with high-probability bounds that may hide polynomial factors in |S| and |A|.Algorithm 3 samples a β value from a model-selection distribution, runs UCBVI-Shaped with it, and updates the distribution using an online model-selection algorithm.Source: §B.4 · pp. 32–33

C Supporting Technical Lemmas

• The technical appendix supplies concentration and counting lemmas, including Freedman and empirical Bernstein bounds and a sum-of-inverse-counts result.These lemmas are stated for martingale differences, bounded i.i.d. variables, and sequences of trajectories, respectively.Source: C Supporting Technical Lemmas · pp. 33–34

D Supporting Algorithms

• The stated UCBVI-Shaped analysis improves on unshaped UCBVI rates when the effective state space is small, despite a base rate with suboptimal dependence on H and |S|.The appendix describes UCBVI as adding a count-based reward bonus and running value iteration on the empirical model.Source: D Supporting Algorithms · pp. 34–35

E Experimental Details

• Experiments use open gridworlds, a 10x10 corridor, and a 10x20 double corridor, with reward only at the goal and averages over three random seeds.The appendix also illustrates PseudoSub and PathPseudoSub in a deterministic chain; for the described shaping, around half of the states can be eliminated to direct exploration.Source: E Experimental Details · p. 35, F Intuition for PseudoSub∆and… · p. 35

G Results for Corrupted eV

• Greater Gaussian-noise corruption of the shaping value function worsens regret, yet still performs better than using no shaping.The evaluation tests zero-centered noise variances of 0, 0.1, 0.5, and 1.0 in the corridor environment with β = 1.5.Source: G Results for Corrupted eV · p. 35

H Results for RND

• Figure 8 illustrates how PseudoSub∆ pairs relate to PathPseudoSub∆ states that can be pruned through shaping.Its rows show the optimal value function, the shaping-derived Q values and PseudoSub∆ pairs, then PathPseudoSub∆ states.Source: Figure 8 · p. 36
• RND-based pseudocounts make UCBVI-Shaped-BS considerably slower than exact counts, likely because of count-estimation noise.The authors suggest environment-specific tuning may improve the results; Figure 10 illustrates the RND-based behavior.Source: H Results for RND · p. 36, Figure 10 · p. 36

I Discussion of Applicability of Reward Shaping Assumption

• The shaping assumption requires prior information that can multiplicatively bound the optimal value function; the paper says shaping cannot improve regret bounds without such information.The authors assume eV(s) ≤ V⋆(s) ≤ βeV(s) for finite β.Source: I Discussion of Applicability of… · p. 37
• Examples include goal-distance proxies in mazes, simulation-learned values for real-world training, and object-distance proxies when obstacle counts are bounded.The simulation example further assumes Lipschitz-bounded dynamics and bounded state- and dynamics-estimation errors.Source: I Discussion of Applicability of… · p. 37
• An anytime motion planner can supply a β-sandwiched suboptimal path to guide RL, while RPG object-distance shaping may support pruning in large state spaces.The paper also says these settings can admit a multiplicative approximation to V⋆ for use as eV.Source: I Discussion of Applicability of… · p. 37

J Limitations

• Reward shaping must be provided beforehand rather than learned or inferred; point-wise bounds can also be vulnerable to outlier rewards with large β.The authors additionally identify function approximation behavior as an area for further study.Source: J Limitations · p. 37

J.1 Does decaying suboptimal reward shaping help over standard shaped rewards?

• With suboptimal shaping, UCBVI-Shaped dampens its effect and succeeds, whereas linear addition can trap the agent at a suboptimal point.Figure 11 compares adaptive decay with standard reward shaping under shaping misspecification.Source: §J.1 · p. 38, Figure 11 · p. 38