Unpacking Reward Shaping: Understanding the Benefits of Reward Engineering on Sample Complexity
Authors: Abhishek Gupta
Aldo Pacchiano
Yuexiang Zhai
Sham M. Kakade
Sergey Levine
Venue: NeurIPS 2022 Accept (2022)
Keywords: Reward Shaping
Regret Analysis

Abstract: The success of reinforcement learning in a variety of challenging sequential decision-making problems has been much discussed, but often ignored in this discussion is the consideration of how the choice of reward function affects the behavior of these algorithms. Most practical RL algorithms require copious amounts of reward engineering in order to successfully solve challenging tasks. The idea of this type of ``reward-shaping'' has been often discussed in the literature and is used in practical instantiations, but there is relatively little formal characterization of how the choice of reward shaping can yield benefits in sample complexity for RL problems. 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 show that these results hold in practice in experimental evaluations as well, providing an insight into the mechanisms through which reward shaping can significantly improve the complexity of reinforcement learning while retaining asymptotic performance. 

Understanding the Benefits of Reward Engineering on Sample Complexity
Unpacking Reward Shaping:
Abhishek Gupta"
Aldo Pacchiano" Microsoft Research, NYC
University of Washington wwwp:p/aaaaa..awssggtt...ooo
abhgupta@cs.. washington. edu
apacchi opaccciinn com
Yuexiang Zhai UC Berkeley, EECS
Sham M. Kakade
Harvard University
s simonzhai@@errkelyyccom edu
sham@seas www.aharade..... edu
Sergey Levine UC Berkeley, BECS
svlevinedeecs wew.seer.eelleeeeeeee
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 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 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- exploration to provide 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 expected to be significant and show how this can be connected practical algorithms in the literature. We confirm that these results hold in practice in experimental evaluation, providing an insight into the mechanisms through which reward shaping can significantly improve the complexity reinforcement learning while retaining asymptotic performance.
Introduction
Reinforcement learning (RL) its most general form presents very difficult optimization problem: when there are constraints on the reward function or dynamics, learning algorithm may need to exhaustively explore the entire state space to discover high-reward regions. Naïve algorithms that rely entirely on random exploration are known to be exponentially expensive [26, 3]. and much of the theoretical work on efficient RL algorithms has focused on smarter exploration strategies that aim to more efficiently cover state space, typically in time polynomial in the state space cardinality [6, 8, 24, 55, 27, 32, 52]. Much of this work is based on upper confidence bound (UCB) principles and prescribes some kind of exploration bonus to prioritize exploration of rarely visited regions. Analogous strategies have also been employed in a number of practical RL algorithms [41, 40, 10,
"Equal Contributions
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

12, 22, 36, 43, 42, 37]. However, perhaps surprisingly, much of the empirical work on reinforcement learning does not make use of explicit exploration bonuses or other dedicated exploration strategies, despite numerous theoretical results showing them to be essential to attain tractable sample complexity. Instead, practitioners often incorporate prior knowledge of each task into designing or shaping the reward function [31, 38, 39, 44, 5, 11, 50, 54], preferring this heuristic approach over the more principled exploration strategies, At this point, one may wonder why is reward shaping often practically preferable to dedicated exploration?
likely answer to this question lies in the fact that even the best purposs exploration strategies still require visiting every state in the MDP at least once in the worst case. This is of course unavoidable without further assumptions. However, practice, sample complexity that is polynomial in the size of the entire state space might still not be practical, and hence prior knowledge in the form of reward shaping is required to render such tasks tractable. Surprisingly, despite the widespread popularity of reward shaping in RL applications, the analysis of reward shaping has remained limited to proving policy invariance [31] or largely empirical observations, often relegating reward shaping to folk knowledge. In this work, we take a step towards studying the effect of reward shaping on the efficiency of RL algorithms, by asking the following question:
Can we theoretically justify the sample complexity benefits that reward shaping from prior domain knowledge can provide for reinforcement learning?
We aim to provide a set of tools that formally analyze how reward shaping can improve the complexity of tabula-rasa RI. and better direct exploration. To perform this analysis, we first propose a simple modification to standard RI. algorithms -" "UCBV "UCBVI-Shaped" that incorporates shaped rewards into optimism based exploration. We use this algorithm instantiation to then provide a regret analysis framework that studies how this introduction of shaped rewards can (in certain cases) provide much more directed optimism than uninformed exploration, while maintaining asymptotic performance.
To approach our analysis, we specifically consider problems where the reward shaping is provided through term V. a (potentially suboptimal) approximation of the optimal value function V*. In particular, we assume that the shaping V is multiplicatively bounded approximation of the optimal value function V*, i.e., V(s)= I V*()) S BV()), Vs, for finite multiplicative factor B. This type of shaped reward function V can be incorporated into standard RL algorithm like UCBVI [8] through two channels: (1) bonus scaling - simply reweighting a standard, decaying count- based by the per-state reward shaping and (2) value projection adaptively projecting VAy(sa] learned value functions into ranges of value functions derived from the reward shaping.
bonus
We show that this relatively simple algorithmic instantiation lends itself to analysis that shows significant sample complexity benefits with shaping. Intuitively, the key pieces in our complexity analysis of VCBVaeh are: (1) A multiplicative sandwich condition (via B) between V and V* allows for the bonus scaling to depend on BV instead of a coarse approximation of V such as H. This allows for reduction of complexity from horizon // dependent term to one scaling with B < BV by allowing for faster decay of the exploration bonuses while still providing enough optimism. (2) A projection of the value function prevents "over optimism" by hastening the convergence of the empirical Q functions during value iteration, thus allowing for faster detection of sub-optimal actions. This results in the ability to prune out large parts of the state space, as we also validate empirically.
To summarize, the key contribution of this work is to characterize how reward shaping can provably improve sample efficiency by providing gains in both |S] and I/ dependent terms. We do so by analyzing the gains from reward shaping in two different ways: bonus scaling and value projection. We show that the "quality" (determined by B) of the provided shaping can significantly improve the sample efficiency of the resulting reinforcement learning algorithm, provide a set of analysis techniques to understand improvements in sample complexity from shaping, and confirm our findings with numerical experiments.
2 Related Work
Regret Analysis in Finite Horizon Episodic Tabular MDPs. Recent research on regret analysis has studied both model-based and model-free RL methods. Model-based methods [23,4, 8, 20, 17, 35] first learn a model from previous experience and use the learned model for future decision making. In contrast, model-free methods [24, 9, 55, 46, 30, 27] aim to learn the value function without the

---

model estimation stage and use the learned value function for decision making, Our analysis lies in the model-based framework and is similar to the setting of [8] but with additional assumptions on knowing V as a multiplicatively bounded approximation of V*. The main difference between our results and the aforementioned works is that we consider the reward shaping setting with a truncated interval assumption. As a result, we reduce the state dependency |S] to the some smaller "effective state space". Our work is also closely related to [21]. We discuss this in Section 3.
Regret Analysis with Linear Function Approximation. A recent line of literature has investigated the linear function approximation setting by assuming the transition kernels or the value functions can be represented by d-dimensional linear features [25, 53, 7, 56, 13, 48, 47, 45] or even general function classes [49]. With the aforementioned assumptions, the regret analysis will only depend on the ambient dimension d (or other intrinsic complexity measure), instead of S.A in the tabular setting [45, 48, 13, 56, 7, 52, 25], which could greatly decrease the complexity of learning. Instead of posing structural assumptions on the function class representing the MDP's values dynamics, ask the question of whether having approximate knowledge of V* can improve the speed of learning.
Practical Reward Design and Reward Shaping. Ng al. [31] proposed a potential potential-based shaping function F that ensures policy invariance under transformation. However, unbiased potential based reward shaping is rarely used in practice. In most applications, heuristic reward design is carefully performed with potentially biased reward functions. In some large-scale practical RL tasks [11, 50, 51], the reward functions are heavily handcrafted based on prior knowledge. Besides reward engincering, distinct line of work applies uninformed exploration algorithms like count-based reward shaping or intrinsic rewards to encourage greater state visitation [41, 40, 10, 12, 22, 36, 43, 42, 37, 28]. Importantly, these methods optimize for the worst case, as they try cover all states since the exact location of the reward is unknown. In contrast, we look at the problem of incorporating domain knowledge via reward shaping into the exploration process. Closely related to our work is that of Cheng et al. [14], which studies how to incorporate shaping (heuristics) into the RL process via reducing the effective horizon. This work provides gains by reducing the horizon factor while our work provides gains by reducing the size of the effective state space that needs to be searched through.
3 Overview
We consider an episodic Markov Decision process M (S,A,P .r.)) where S corresponds to the state space, A the action space, P is the transition operator, r: S:S A- [0, the reward function and H is the problem horizon. We use |S), |A| to denote the number of state and actions, and we use (- a) to denote the transition probability of state action pair (s.a). The value function (T((s) of policy π starting at an initial state so is defined as VT((o) := Ex r a+)] where Eg denote the transition dynamic of M under πτ Similarly, V*(No) is the value function of the optimal policy X². We consider a sequential interaction between a learner and the MDP . occurring in rounds indexed by N. At the start of round the learner selects a policy π, that is used to gather sample trajectory from M. As is standard in the literature, we measure the learner's 's performance up to round T by Regret(T): == X (so) V (5o).
Our goal to show that knowing a reward shaping term V allows for sig- nificantly more sample efficient learn- ing, which with high probability has sublinear regret upper bound. This bound has a leading term that depends on an "effective state space" of M, determined by the quality of a reward shaping term V and the nature of the particular MDP being solved. This pruned effective state space can be much smaller than (S]. Additionally, we will show an improved horizon de- pendence as the shaping term V al- lows for the bonus terms to be smaller
ETSTE
Figure 1: Reward shaping can allow for reduction of the "effective" state space size. the above maze environment, the initial state in the middle the maze so finding the goal only requires solving half of the maze (Left). While uninformed state covering exploration (Middle) would go both directions since it has no knowledge of goal location, effective shaping (Right) would allow for halving of the effective state space. The green circle represents and the red square represents the goal. Different colors represents the landscape of the shaped value function (green indicates smaller value and red indicates larger value).
starting point
and therefore decay faster thus replacing horizon factors of H with BV ones.
3

---

Intuitively, reward shaping allows for the consideration of reduced effective state space. Consider the maze environment in Fig. 1 with agent starting in the middle. Without knowing where the goal is, an uninformed exploration algorichm needs to explore nearly the entire maze. However, an effectively incorporated reward shaping term V would allow the algorithm to prune out the entire left half of the maze, effectively halving the effective state space size. This can happen in two ways: firstly, if the shaping can directly indicate that certain actions are sub-optimal, then entire regions of the space can be eliminated from search. Secondly, even if states are not eliminated, if their corresponding bonuses are scaled according to their shaped value from the shaping rather than uniformly with H, it limits unnecessary exploration of suboptimal states.
Based on this intuitionn, we propose modifications a standard reinforcement algorithm that allows us to perform this analysis effectively. To aid our analysis, we introduce VC-B---h a modification of the UCBVI algorithm [8] that uses an additional reward shaping term V in two ways: (1) Bonus scaling: V is used to provide exploration bonus that combines inverse state visitation counts with reward shaping. This allows for the reduction of overoptimism and the dropping of the horizon H dependence (2) Value projection: the shaping term is used to clip the empirical value function (s).. which enables pruning unnecessary elements of the state space and allows for bound that depends only on the effective state space size. Informally, our main result for UCBVi-Shaped can be summarized follows:
Theorem 3.1 (Main Informal). With probability at least 1 - ô, the regret of UCBVI- - Shaped satisfies?
RT) O ( BB MM) /8) + Regret - UCBVI(S : A.T)).
Here, Syemain corresponds to the set of states in M where the information contained in V was not enough to rule them out, and Regret- - UCBBI((SemainA,"" is a UCBVI regret upper bound function evaluated on Spemain and A. B(V, MM) is time-agnostic complexity measure that depends solely on the M and the quality of the shaping V.
We will define Sremain and (VV,M and describe their relationship to V preciscly in Section 5, If Sremain < S, the regret of UCBVI Shaped can be substantially smaller than Regret- A.)) particularly since the first term of the regret grows logarithmically while the second scales with vT. We state our assumptions next:
Assumption 1. The quality of the shaping term V is described by a parameter B. We assume access to shaping "value functiin"" estimators Vn S + R such that V (s) < (V)(s). for all s E h HH] and for some B 2z! I.
Instead of absorbing B into the definition of V we allow Vs(() < (i) for some states s E S. We'll show that learning a value of ß that turns this assumption true can be performed online. This assumption is intimately related to the optimistic @ assumptions of [21]. A thorough comparison with this work can be found in Appendix B.2.
Assumption 2. We assume the reward functions satisfy r(s;a) (0. [0.1), ESX Assumption 3. The states S are h h-indexed, i.e., the states reachable at time h E [HT] are disjoint from the states reachable at time h' [M] when h + ht.
Contributions. Our main conceptual innovation is to introduce the notions of pseudosuboptimal and path- saath-ssuudoubbppiiaall states to quantify the "effective" size of the state space as a function of the quality of the shaping term V and use these notions to show how UCBVI-Shaped can attain significantly improved regret rates. In contrast with for example [21], where the regret rates will always scale at least with the number of states, our regret guarantees depend on an effective state size that may be orders of magnitude smaller. We believe this captures the real complexity improvement that reward shaping may yield, namely, avoid exploration of unnecessary areas of the state space. Other approaches such as [21] may (in general) most yield an improvement in the dependence on the effective size of the action space. We further show that incorporating shaping into the exploration bonus term improves the -ereedendeeendence in the bound when the shaping is good enough, allowing us to replace a leading H term with max, (V.).
2Our main result, Theorem 5.2, is slightly more complex than this statement. We have chosen this simplified form to aid the reader form the right intuition.

---

The UCBVI-Shaped Algorithm
To perform analysis of reward shaping, we build on the framework of the UCBVI algorithm [8]. UCBVI is an exploration algorithm based on the upper confidence bound, described in detail in Appendix D. This forms a convenient base algorithm for incorporating shaped rewards in a way that admits faster learning while maintaining asymptotic performance (as we will discuss in Section 5). Our algorithm, UCBVI-Shaped
is combination of two changes to the upper confidence bound algorithm. First, we modify the bonus scaling to depend on V. Second, we introduce projection subroutine into value iteration, implemented as standard clipping operation.
Algorithm UCBVI- - Shaped
I: Input reward function (assumed to be known), confidence parameters
2: for I,..,
3:
Compute P using all previous empirical transition data (s')s,
Mlkass))
Vh,s,a,s
4: Compute reward bonus by, (s,a) from Eqn. 1 (roughly of order VN(iaa)
Bonus scaling
5: Run Value-Iteration with Projection (Algorithm 2).
6: Set as the returned policy of VI.
7:
End for
As in standard UCBVI, we define (s.a) to be the visitation count for the state-action pair (s,a) iteration for horizon h: (s, == E (() = (s,a)). Similarly (s, we use (s, = E- 1 (1 " (s, as the visitation count of state-action pair (s,a) and the subsequent state 5'. We then use (s' transition kernels at iteration r. UCBVI uses value iteration with the empirical transition function P. and reward function augmented with exploration bonus, given by rл + b/.. This is defined as a dynamic programming procedure that starts at // and then proceeds backward in time to O, updating according to Algorithm and 2. The key algorithmic changes between UCBVI and UCBVI- Shaped are highlighted in blue: (1) scaling bonus b/, by the shaping term V and (2) projecting the empirical value function (s) by an upper bound based on the sandwiched shaping, (v, As we discuss in Section 6, we also show how the sandwich factor B does need to be provided beforehand but instead can inferred through a straightforward technique for online model selection. While
Mixar))
Wh,s,a,s' to denote the empirical
AgGaaa
more detailed description can be found in the approximate order of the bouns term is V(s,a)
Section 5.
Algorithm 2 Value Iteration with Projection
H-1
1: Input Pr, Pr,r+ b/ k=O
2: (s) (s)
0, Vs. (s.a) 3: While not converged
4: (s, min (( (s (-(ss,) H
5:
(s)) min max, ((s,)),
Value projection
6: (s) arg max, (s,,), Vh,saa
Analyzing UCBVI-Shaped
In this section, we will derive our main result on the sample complexity of the UCBVI-Shaped algorithm, and along the way introduce pseudosuboptimal and path-pseudosuboptinal states as a tool for deriving bounds that depend only on the "effective" state space as determined by the provided
The P. here is dependent on the horizon h, but since we have assumed (Assumption 3) the states h-indexed, we will use P, for notation simplicity.
5

---

reward shaping. We will first introduce some notation to use in our analysis. As described in the previous section, UCBVI-Shaped proceeds in rounds. At the beginning of round r, the learner has access to an empirical model IP, built from the data collected up to iteration / - 1. The bonus terms we consider are built by taking the empirical second moment of V. This related to the definition of bonus; in Azar et al. [8]. Importantly, the empirical value functions V/ are clipped above by BV₁;
V (s") [s.a] aa In 2
P-Pi (.,)
12BV max
In ||5||A||r .2V (1)
(s,a) min 16B
(s.a)
(s.a)
where V/mi max; Vs')') and Vmax max N (sy)
Despite clipping and modified bonus term, the Q and V values of UCBVI-Shaped optimistic: Lemma 5.1. With probability at least 1 ô we have
(50) 2 Vō (so), Vso S:; and Tn(s,a) 2 (%ss)), V(s,a) ( SxA.
for all 1, E [M] where VH is computed via Algorithm 2.
The proof of Lemma 5.1 can be found in Appendix A.I. Optimism (Lemma 5.1) and the simulation Lemma [2] imply that:
H Σ (sh + (Ph(-1sh:ah) -P (-1st,aa)) Viti
V"(so) - v (so) s Vi(o) (so) Bgg
We now turn our attention to characterize the information contained in V.
5.1 Pruning of the State Space
Consider the following "surrogate" Q functions, 0% :8
PathPacnnaaa Sansl A
induced by V via:
x A
[r(s.a) 1
Boundary Peadodfuh
PseadoSuby
By Assumption 1, we can bound Q" via () - (s.a). The basis of our main results is the following observation. If action satisfies Q (s. a) < (s)ss) for state s, then is suboptimal action for state s. The projection (Step 5 of Algorithm 2) ensures the 'em- pirical' Q-functions 02 (s, a) of Algorithm will quickly converge to values upper bounded by (s. Since optimism guarantees that 2 (s. (s)) 2 (s),,. and the policy executed by UCBVI-Shaped greedy w.r.t 2₁p- actions belonging to state-action pairs such that (s, < (s) will quickly stopped being played by the algorithm. Moreover, all states that are only accessible through state-action pairs of this kind will also stop being visited by the algorithm after only a few iterations. In the subsequent diseussion we will call PseudoSub to the set of state action pairs that are quickly 'prunned out' by UCBVI-Shaped the set of states only accessible through these state action pairs as PathPseudoSub and the set of state-action pairs in PseudoSub that are not in PathPseudoSub x A as BoundaryPseudost Boundary PseudoSub have been visited enough, no states in PathPseudoSub will be visited again. Provided this happens sufficiently fast, we can show a regret bound that is independent on the size of PathPseudoSub. The subsequent discussion is aimed at formalizing this and culminates with our main result (Theorem 5.2).
Suppert (er (4.o))
Figure 2: Path PucuudSSuSSb x A is split from Support(d** (s,a)) by BoundaryPseudoSube Shaped can avoid exploring over Path PseudoSuuS x A.
UCBVI-
Once all states in
Given a parameter A > 0, we say that an action a is A p-sseudosuboptimal for state if (s) Z A + (s) We denote the set of A- p-sssuuosuuooptimal state action pairs as:
PseudoSuba = {(s a) E x A V (s) > A (s)
*We add the qualifier pseudo our name to distinguish between suboptimality as captured by our surrogate values and true suboptimality between the true values of Ø

---

The intuition we want to capture is that all states á that can be accessed only through traversing state action pair in PseudoSub,, can be safely ignored because we can determine their suboptimality as soon as the state action pairs in PseudoSuba that lead to 5 are visited enough.
Now define the set of peaadhosouuo states the states that can be reached only by traversing a d-sseuuoouubopinal state action pair:
PathPseudoSuub {s E S s.t. all feasible paths from initial states to intersect PseudoSubs).
Notice that there may be state action pairs in PathPseudoSubs x A that may not be in PseudoSubx. In fact, there may exist states s in PathPseudoSuba such that no (s.a) ) is PseudoSub, for all E A. We will show that states in PathPseudoSub, will not be explored by UCBVI-Shaped af- ter a few iterations. Intuitively, this happens because the support of the state visitation distribu- tion of the optimal policy does not contain any state in PathPseudoSubg, VA 0 (or equivalently, Support (dt ()) PathPseudoSubs = 0, AA 0). Hence, once the UCBVI-shaped identifies some sub-optimal state action pairs, the algorithm will not visit these state-action pairs again.
For any state action pair (s.a), define its set of neighboring states Neighbor(s, a) as the set of states with nonzero probability in IP* a)) By definition of PathPseudoSuba, for all (s,a) E (S x ()aahaaPssuuuuu x A) UPseudoSuba), we have:
Neighbor(s.a) S S PathPPeuddoSub..
(4)
In other words, the neighborhood of any state action pair (s.a) whose state is not in PathPseudoSub, are not in PuthPseudoSubs. We also introduce the
and such that (s,a) is not A d--psudoo-uubopttii notion of "boundary pseudosuboptimal" state action pairs to capture the set of state action pairs that are A A-sAA--subbnnn suboptimal but whose states are not in PathPPeudoSubx.
Psenddrr, = {(s, a) E PseudoSuby and s E PathPseudoSubs).
Naturally, one of these states has to be traversed by any trajectory that contains any state in PathPseudoSuba-
Although we only use Q" in the definition of PseudoSubg. PathPseudoSubs. and BoundarysseudoSuby. the size of these sets is modulated by the scale of B and the width of the intervals (sssa))(((ssa
We will show that (in the notation of Theorem 3.1) Spraned & S PathPeedooSSb.. With this notation, the formal version of our main results is stated follows. Theorem 5.2. With probability at least 68, the regret of UCBVI-Shaped is upper bounded by
mmax S|I
Σ v (sp) - V (s0) = o min HBBmax
|S PathPsccudoSSb |
8
B² (vmax) H BouunaryPscuuooSuu// 1/2 In
max SIAAT
min (A(A), ))
8
1//// and B(A)= Bimax H BoundaryPseuddSSuhy 1/2
for all T E N. Where A(A)
A
Theorem 5.2 instantiates the desiderata of Theorem 3. Although this regret upper bound cannot be decomposed into a sum of two term as in Theorem 3.1. For any fixed A, the regret upper bound has two components, one where Syemain can be identified with |S' PathPseudooSu and second one that scales logarithmically in T. the next section we flesh out the steps in the proof of this result. The full argument can be found in Appendix A. The bonus scaling also allows us to ameliorate the horizon dependence of the upper bound. Instead of obtaining a H dependence as the bound of theorem 7.1 [2], the first term depends on H HBvmax Notice that the state dependence in the second term may be only be of order log((S)) if there is a A such that [BoundayysseudoSuby << |S] (albeit could
at the cost of quadratic dependence on 1 1/A²). Moreover notice that GoouddayPseuuoSSun be much smaller than PaathPseudoSub/ (the set of states that are reachable only by visiting states in [PseudoSuba] thus showing that in some cases we can guarantee that even in the low order terms, the regret of UCBVI-Shaped that has polynomial dependence on an effective state space size that may be orders of magnitude smaller than the original one. The full version of this bound, with all the low order terms we have omitted for the sake of readability can be found in Appendix B. Theorem B. I. Note that Theorem 5.2 is a strict generalization to the UCBVI regret upper bounds, as setting A to value that is smaller than the minimum gap recovers the exact result (Theorem 7,6in (2]).
7

---

5.2 Proof Intuitions and Sketch for Theorem 5.2
Improved Horizon Dependence. An empirical Bemsttii bound shows that adding bonus scaling (up to low order terms) with O
(V Var (Viti (s') s( 2|5 (N is sufficient to ensure optimism. Since V is not known, this variance term can be substituted by the empirical second moment of BV++1- Finally, the scaling of these terms can be upper bounded by BVrmax Without knowledge of V, achieving this scaling would be challenging, since the only proxy for V available H both of which may vastly overestimate it.
V
State Pruning. The value function clipping mechanism ensures that By (1s..))
1 ( S
BE (( (h+1((") and therefore the empirical gap between 0, (s,a) and V*(s) is decreasing at rate of at most O (Biinax /VN,(s,a) Since optimism ensures that 0 xs, 2 V*(s).
once @(s,a)= < (s),, action a will not be chosen anymore. Thus, for any A, the number of times any state action pair in PseudoSubs may be visited by UCBVI-Shaped is upper bounded
by B² ((mmx) /A². Since any visit state action pair in PathPseudoSubs x A PseudoSuba requires visit to state in BoundaryPseudoSuby, which allows us to bound the total number of visits state (or trajectory containing such state) in PathPseudoSuba x A U PseudoSub, by
I/ [BBoundaryPseudoSuuuJ]]] B²
mmmax /
Finally, split (a version of) the regret decomposition in Eqn. 3 into two sums, state action pairs in 2/bad = PathPseudoSuba x AU PseudoSub, (or trajectories intersecting 2 and second one over state action pairs in 2/8ood (S x A)) (PathPseudoSubx AU PseudoSubx) then apply the upper bound the vis- itation of state action pairs in PathPseudoSuba x A U PseudoSuba to derive regret upper bound over these states scaling with 1/A. Using the bound on the number of trajectories that intersect PathPscudoSuba x AA PseudooSub, the trajectory decomposition yields the term scaling with 1/A² (but having only logarithmic state dependence) in Theorem 5.2. Recall that Eqn. 4 implies that the transition operators over state action pairs in 2/good have support only over S PathPPeeudoS.b Our proofs use this fact to prove a polynomial dependence on (S) PathPseudoSub, and not [S] in Theorem B.11 (see Appendix B. the full version of Theorem 5.2. Detailed proofs are in Appendix A.
(or trajectories without intersection with had ). We
6 Practical Considerations: Online Model Selection
Now may notice that UCBVI-Shaped requires knowledge of the scaling is in order actually perform the value projection. While this can be pre-provided by a user or set conservatively. this section we discuss how this can be inferred by viewing this as an online model selection problem. In particular, given a set of N different values of B - BB, B2.....,.. Bv], each of which parameterizes a different setting of the learning algorithm JCBVI-Shaped(1) (B), an online model selection algorithm such as Stochastic CORRAL [1, 34] or RegretBalancing [33, 15] jointly infers the value of ß and learns the appropriate value function online. In Appendix B.4 we show how these techniques can yield meaningful regret guarantees and we provide pseudocode.
7 Numerical Simulations
To show the practical relevance of our analysis reward shaping we perform some numerical simulations on a family of maze environments with tabular state-action representations, as shown in Fig. 3. These environments have deterministic dynamics and reward. The reward is 0 at all states except goal sink state, which has reward These simulations are aimed studying the following questions: (1) Does reward shaping improve sample complexity in these types of maze environments over uninformed UCBVI? (2) What is the relative importance of the bonus reweighting and the V projection? (3) How does the "suboptimality" of V impact the resulting sample complexity? (4) Does introducing decayed shaping actually allow for policy convergence? In these experiments, is constructed by scaling the optimal value function V* by per-state scaling factors sampled independently within the range B.
8

---

(b) Value function of Single Corridor (c) Value function of Double Corridor Figure 3: Environments used for numerical simulations. (Left) Open Gridworld (Middle) Single corridor, agent starts bottom right has to reach goal in top left (Right) Double corridor, agent starts in the middle and has to reach a goal the left, with many irrelevant states the right hand side
(a) Value function of Gridworld
7.1 Does reward shaping help direct exploration over optimism under uncertainty?
We conducted numerical simulations on tabular environments to understand how reward shaping via UCBVI-Shaped provides benefits over standard UCBVI. Fig. 4 shows cumulative regret accumulated with different variants of UCBVI-Shaped (with both projection and bonus scaling), UCCNV--Shaped-P (with only projection), CCBVI-Shaped--SS (with only bonus scaling). UCBVI (standard UCBVI without shaping, as described in [8].. This is benchmarked across the three environments described in Fig. 3, with various levels of imperfect shaping applied by varying β 1..5, As seen from Fig. 4, across all environments UCBV VIshaadd with projection and bonus scaling performs most favorably, followed typically by UCBVI- Shhapedsa followed by -CBVI-Shaped-BB -BS and UCBVI, suggesting that reward shaping can significantly help with learning efficiency.
(a) Open Gridworld. f = 1.5
(b) Single Coriiar, P = 1.5
(c) Double Corrider, 0 =15
(d) Open Gridworld, B == 1.9
(c) Single Corridor, B = 1.9
(9 Double Corridor, B = 1.9
Figure 4: Cumulative regret for learning in various environments with varying amounts of shaping, as compared with UCBVI, and ablations UCBVI-Shaped-BS (no projection) and UCBVI-Shaped-P (no bonus scaling).
7.2 How does the effectiveness of reward shaping vary across environments?
We next conducted some numerical simulations across environments to understand how the nature of the environment itself affects the sample complex- ity of learning with shaping via UCBVI-Shaped.
As shown in Fig. 6, we see that UCBVI shaped can be very effective in environ- ments with many irrelevant sub-optimal paths like the double corridor environment in Fig. 3, but relatively less effective in environments where all exploration is directed the same way such as the single corridor. Even incorrect but optimistic shaping will provide guidance towards the goal, making UCBVI relatively less dominant in the single corridor environment as compared to the double corridor. This suggests that in environments where
(a) Single Corridor
(b) Double Corridor
Figure 5: Effect of suboptimality of reward shaping on the performance of UCBVI-Shaped. While B = 1.2, 1.5 don't make much of difference, very large B leads to performance degradation

---

(a) Heatmap of intermodiate visita- (b) Heatmap intermediate visita- (c) Learning progreas of UCBVI- tions of UCBVI single corridar tions UCBVI- Shupel single Shaped cumpared to UCBVI gle corridor
shaping)
ridor
(d) Heatmap intermediate visita- (e) Heatmap intermediate visita- (f) Learning progress
tions of UCBVI double corridor tions of UCBpe double Shaped compured UCBVI an dou- (no shaping)
corridor
ble corridor
Figure 6: Visualization of how different environments are affected by reward shaping differently. (Left) intermediate visitations (Right) learning progress of UCBVI vs UCBVI-Shaped. The single corridor environment on the top sees much smaller gains for UCBVI-Shaped compared to double corridor environment.
ruling out an entire part of the exploration space is easy from the shaping, we can expect to see larger benefits.
7.3 How does the suboptimality of reward shaping affect learning?
We next compared how different levels of suboptimality of the sandwich term in the reward shaping affect cumulative regret across environments. As shown in Fig. (a) and (d), we see that for environments with open paths (like the open gridworld), the shaping degradation has minimal negative effect until it gets very suboptimal. On the other hand, for corridor and double corridor (Fig. (b)). where there are only few paths to the goal, suboptimal reward shaping along those paths significantly hamper progress.
7.4 Is online UCBVI-Shaped able to infer B online without prior knowledge?
As described in Section 6, UCBVI-shaped can be freed of the sumption of B being known by performing online model selection of B and learning values jointly. particular, we use the Stochastic CORRAL algorithm [34], variant of the method introduced in [1] to perform online model selection, with the episodic return being the requisite criterion for updating the model selection distribution. As we see Fig 7, this scheme is able show comparable results to when the actual B is known beforehand, only degrading as the value of B increases. This suggests that online UCB VI-shaped can be practical in regimes with moderate levels of value corruption.
Figure 7: Understanding perfor- mance of online model selection in UCB
Discussion
In this work, we take a step towards formally analyzing the benefits reward shaping, proving that effective reward shaping can lead more efficient learning than uninformed exploration strategies. In our analysis, we study an algorithm that incorporates reward shaping into modified version of UCBVI, using it to modify bonuses and value function projection. Our analysis shows that incorporating shaped rewards allows for pruning significant parts of the state space and sharpening of optimism task directed way. This reduces the dependence of the regret bound on the state space size and on the horizon, depending on the quality of the shaping term and parameters of the MDP. This shows how reward shaping can direct exploration and provide significant sample complexity benefits while retaining asymptotic performance. We hope that this work is step towards moving sample complexity analysis away from being reward agnostic to actually considering reward shaping more formally in analysis.
10

---

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. Pe-pg: Policy cover directed exploration for provable policy gradient learning. Advances 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: 170.00700, 2017.
[5] O. M. Andrychowicz, B. Baker, M. Chociej, R. Jozefowicz, B. McGrew, J. Pachocki, A. Petron, M. Plappert, G. Powell, A. Ray, al. Learning dexterous in-hand manipulation. The Interna- tional 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 regression. In International Conference Machine Learning, pages 463-45 474. PMLR, 2020.
with
[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, Dębiak, C. Dennison, D. Farhi, Q. Fischer, S. Hashme, C. Hesse, et al. Dota 2 with large scale deep reinforcement learning, arXiv preprint 1912v
2019.
[12] Y. Burda, H. Edwards, A. Storkey, and O. Klimov. Exploration by random network distillation. arXiv preprint arXiv: 12894, 2018.
[13] Q Cai, 7. 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-guider reinforcement learning. In M. Ranzato, A. Beygelzimer, Y. N. Dauphin. Liang, and W. Vaughan, editors. Advances in Neural Information Processing Systems 34: Anmual Conference on Neu- ral Information Processing Systems 2021, NeurIPS 2021, December 6-14, 2021, virtual, pages 13550-135633 2021. URL https: /ttp//eeeeeen....//////////...sp senceedings.neuripp. neurips.com wtwppps..cpppp////////p 2220/hashh/ 704311887b60224411566633 23eb84a306- 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 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 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-ram range robotic navigation tasks by combining reinforcement learning and sampling- 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.1 10.1109/. 2018.8461 8018.841199. URL https: / //w.i.o...//// 10g/10.1/0 1109 CORO//////..... 2018. 8861096.
[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 bias-span- span-constrainneeee exploration- exploitation in reinforcement learning. In International Conference on Machine Learning, pages 1578-15866 PMLR, 2018.
[21] N. Golowich and A. Moitra. Can q-learning be improved with advice? Learning Theory, pages 4548 4619. PMLR, 2022.
Conference on
[22] R. Houthooft, X. Chen, Y. Duan, Schulman, 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. q-learning provably efficient? Advances in neural information processing systems, 31, 2018.
[25] C. Jin, Yang. Z. Wang. and M. Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference on Learning Theory, pages 2137-2143. PMLR, 2020.
[26] S. M. Kakade 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, Gupta, A. Reddy, V. Pong, A. Zhou, J. Yu, and S. Levine. Mural: Meta-learning uncertainty-awarr rewards for outcome-driven reinforcement learning. In International Confer- ence on Machine Learming, pages 6356-6356. PMLR, 2021.
[29] A. Maurer and M. Pontil. Empirical bernstein bounds and sample variance penalization. arXiv preprint arXiv:0907.37400 2009.
[30] P. Ménard, O. D. Domingues, X. Shang, and M. Valko. Ueb 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. /9/1, 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, 11110002103333 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.
12

---

[36] D. Pathak, P. Agrawal, A. A. Efros, and T. Darrell. Curiosity-drived 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 TJBFPB.
[38] D. Silver, A. Huang, J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanetot, 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 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: http://pooeeeeeeeecceoeo neurips. Pww.e0000000---ep.eoeeeeee cc cc/paper/2017/filee http:///......000000002222224600 2ttaa/////////////o//aaaa022a2a0
pdf.
[43] S. Vezhnevets, S. Osindero, T. Schaul, N. Heess, M. Jaderberg. D. Silver, and K. Kavukcuoglu. Feudal networks for bierarchical reinforcement learning. In Proceedings of the 34th Interna- tional 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-334 2019.
[45] Y. Wang, R. Wang. S. S. Du, and A. Krishnamurthy. Optimism in reinforcement learning with generalized linear function approximation. arXiv preprint arXiv: 1rXiv: 1912.04126,3... 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 feature space: Matrix bandit, kernels, and regret bound. In International Conference on Machine Learning, pages 10746-10756. PMLR, 2020.
[49] Z. Yang, C. Jin, Wang, M. Wang, and I. Jordan. On function approximation in reinforce- ment 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, Chen, Z. Liu, Qiu, H. Yu, Y. Yin, B. Shi, L. Wang, T. Shi, Fu, W. Yang, L. Huang, and W. Liu. Towards playing full moba games with deep reinforcement learning. Balcan, and H. Lin, editors, Advances in Neural Information Processing Systems, volume 33, pages 621-632, Curran Associates, Inc., 2020. URL https: httppp/:e///popoppppeeeeee wewpeeeeiinn..euuiipi..ee. www.nnuuruccmmm cc/ Paper pdf.
Larochelle, M. Ranzato, R. Hadsell, M. R
paper/2020/Ein httpe//////////e////eeeeeeeeeeee htt.r///eeeoooeeeeeeeeeeeeeeeee0
13

---

[51] T. Yu, D. Quillen, Z. He. R. Julian, K. Hausman, C. Finn, and S. Levine. Meta-worid: 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, CoRI. 2019, Osaka, Japan, October 30 November 2019, Proceedings, volume 100 of Proceedings of Machine Learning Research, pages 1094-1100. PMLR, 2019. URL http: htttt::p/ppooceedngge mlr. wwt.ppessevvile http//11000///// html.
[52] A. Zanette and E. Brunskill. Tighter problem-dependers regret bounds in reinforcement learning without domain knowledge using value function bounds. In International Conference Machine Learning, pages 7312-7312. PMLR, 2019.
[53] A. Zanette, D. Brandfoombenner, E. Brunskill, M. Pirotta, and A. Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference 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 Machine Learning, pages 12802. PMLR, 2021.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section 8
(c) Did you discuss any potential negative societal impacts of your work? [Yes] See Section 8
(d) Have you read the ethies review guidelines and ensured that your paper conforms to them? [Yes] This work does not actually use human subjects, and is largely done in simulation. But we have included discussion in Section 8
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A] Math is used theory/formalism, but we don't make any provable claims about
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] See Appendix
A for link to URL and run instructions in the README in the github repo.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix A.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] All plots were created with random seeds with std error bars.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Appendix A
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] Envs we used cited in section
(b) Did you mention the license of the assets? [Yes] This is in Appendix B
14

---

(c) Did you include any new assets either in the supplemental material or as a URL? [Yes] We published the code and included all environments and assets as part of this
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [Yes] We used three open source domains and collected our own data on these domains.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [No] We did not include full text since we didn't 't use an exact script, but we summarized the instructions and included images of the environments used.
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A] Only human involvement was data collection with system.
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A] Human testers were volunteers
15


Reviews:
[{"review_id": "lLqLX-ejr0d", "reviewer": "Reviewer_3Wkq", "summary": "This paper attempts to shed light on reward shaping (RS) in reinforcement learning (RL) from a theoretical perspective. The authors contend -- correctly, in my opinion -- that the majority of work in RS has focused on RS from a practical point-of-view, while there is relatively less work developing theoretical characterizations of it. \n\nThe authors ask the question *\"Can we theoretically justify the sample complexity benefits that reward shaping from prior domain knowledge can provide reinforcement learning?\"*. In seeking an answer to this question, the authors make some assumptions (e.g., bounds on $\\tilde{V}$) and propose a specific algorithm, UCBVI-shaped, which is amenable to analysis. \n\nGiven the set-up describe in the preceding paragraph, the contributions of this paper are:\n1. A new algorithm that incorporates the RS method of the paper called UCBVI-shaped\n2. A theoretical upper-bound on the regret of this method showing lower regret compared to vanilla UCBVI (along with some mathematical tooling, e.g., pseudosuboptimal states)\n3. Empirical analysis of the proposed method showing its strengths and weakesses.\n\nIn short, the paper puts forth a question and then quite thoroughly studies it. The end result is an affirmation in the sense that the authors are able to derive a bound on regret when they enhance an algorithm (UCBVI) to use their specific instantiation of RS.", "questions": "*Suggestions for Improvement*\n1. One of my main issues while reading this paper was that the UCBVI algorithm was not described. As a result, some of the points of the text were lost on me as I list below.\n* L63 refers to some $H$. I'm not sure where this came from as it isn't previously defined, and so I can only assume it has something to do with UCBVI.\n* Moreover, some of the argument in Section 5 compares the regret of UCBVI and UCBVI-shaped. It's difficult to understand this as UCBVI isn't discussed.\n\n2. How does UCBVI-shaped fare if we corrupt $\\tilde{V}$? I'm quite curious about this experiment.\n\n3. I'd have been interested in seeing some experiments where UCBVI-shaped uses RND as a method to compute \"pesudo-counts\"?\n\n4. Figure 4e - Why is there that one state with really high visitations?\n\n5. Figure 3e - What happened to UCBVI-shaped? Some explanation of this peculiar degradation would be helpful\n\n6. L100 \"...H is the problem horizon...\" - Is H fixed? Can you clarify exactly what H means?\n\n7. Number of seeds used in the experiments is not mentioned?", "limitations": "N/A", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "*Strengths*\n1. In terms of quality and scientific soundness, this paper is difficult to fault. The object of inquiry is clearly stated, as are the assumptions made of the investigation into it. A theoretically justified answer to the question is derived, and the paper goes even further by analysing the strengths and weaknesses of the method upon which their theoretical results are based.\n2. Moreover, in terms of originality, the paper deserves merit. I can only think of one other work which attempts to develop some theoretical results about RS (which is cited -- Ng et al., 1999).\n3. Modulo one major complaint and a few minor issues (described below), the paper is also eminently readable and clear. I rarely found myself repeatedly re-reading anything to try to deduce what was being said.\n\n*Weaknesses*\n1. My central issue with the paper is its significance. By this I mean that the assumption of the type of shaped reward function -- $\\tilde{V} \\leq V^* \\leq \\beta \\tilde{V} $ -- limits the impact and applicability of the results of the paper. It is a significant assumption. In fact, I would argue that it's almost expected that given such a form for the RS that there would be benefits to sample complexity. I know your assumption is looser than this, but the following is just to explain  why I made the last statement. Suppose we have access to the $V^*$. We can essentially just set the values of the $V$ we are learning to the intrinsic rewards generated by $V^*$, and this will almost certainly benefit sample complexity.  While I do appreciate that some simplifying assumptions are required, I think this really limits the scope and impact of this paper. With that said, it's interesting to see how sample complexity is affected by pseudosuboptimal states and so on.\nNote: I may have misunderstood/missed something here, in which case I urge the authors to clarify.\n\n2. Further to the point above, I'm also a little unconvinced about the characterization of what kind of problems RS helps. The intuition about dubious paths makes sense in grid-worlds, but I don't see exactly how this intuition generalizes to general RL problems.\n\n*Minor Issues*\nFurthermore, below is a list of minor textual errors I was able to catch.\n \n* Figure 1 - Very nice, but what do the colours mean?\n* Figure 5 appears before Figure 4 in the text. This was a bit confusing for a moment.\n* Assumption 3 - What's $[H]$? I don't think this is defined?\n* Theorem 3.1/Lemma 5.1 - What's $\\delta$? Not sure if I missed something but as far as I can tell it is not defined.\n\n* L3 \"...choice of reward function...\" - I found this a bit misleading as normally in RL we just accept the reward function that comes with the environment.\n* L47 \"...tabula-rasa RL\" - I don't know what tabula-rasa means\n* L47  \"...better direct. exploration...\" - typo\n* L73 \"...aim to learning...\" - should it be \"learn\"\n* L111 \"...high probability having...\" - should it be \"has\"\n* L108-117 - very long run-on sentence was quite confusing to parse\n* L183 - \"bonus_2\"? \n* L 296 - \"As shown in Fig 5., we see that for environments with open paths...\" - But Fig. 5 doesn't show Gridworld (which is the env I assume has open paths)\n\nI am open to reconsidering my evaluation if the authors can convince me of the broader applicability of their results in this paper.\n\n[1] - 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.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "d4Lrp1AWIZ", "reviewer": "Reviewer_PYg1", "summary": "This paper investigates the regret analysis of a particular form of reward shaping where the shaping function is an approximation of the optimal state value function. This reward shaping is integrated into an extension of the UCBVI algorithm to obtain UCBVI-Shaped. Experiments show benefits of this approach by enabling the elimination of potentially large subsets of the state space by ignoring regions where the value is low during exploration.", "questions": "1. Can you justify the assumption that the reward shaping function is an approximation of the optimal state value function? How strong of an approximation does it need to be? If there is a close enough approximation, this trivializes the problem.\n2. Why do you choose the bonus term to be the empirical second moment of \\tilde{V}?\n\nMinor comments:\n* \"has focused smarter\" -> has focused on smarter\n* In Algorithm 2, line 5: should the k superscript be a t? Should \\tilde{V} have a subscript of h?\n* \"\\beta . .\"\n* \"\\beta = \\{1.5, 1.9\\}\" -> \\beta \\in \\{1.5, 1.5\\}\n\n", "limitations": "The authors state that Section 7 covers the limitations of their work. It does not seem to. But, elsewhere, it is stated that for some experiments (like the single corridor example), the reward shaping may not be very informative and something like an optimistic shaping function can yield better results. ", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n* The proposed algorithm has good sample complexity and a detailed regret analysis\n\nWeaknesses\n* It seems like a strong assumption is being made whereby the shaping signal is an approximation of the optimal value function. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "RzSXtLxQZ", "reviewer": "Reviewer_utjg", "summary": "Learning near-optimal policies in sparse reward environments with large state space is challenging. In theoretical reinforcement learning (RL) literature, it has been understood that directed (optimistic) exploration strategies (provably) improve sample complexity over random exploration techniques. However, in practice, people use heuristic-based (exploiting domain knowledge) reward shaping to demonstrate successful results. This paper conducts a formal theoretical investigation on the impact of such reward shaping methods on the sample complexity of RL algorithms. In particular, the authors propose two simple modifications to the well-known UCBVI algorithm and show how these changes lead to tight regret bounds. In the experiments, they studied: \n- the importance of the two modifications that they introduced, \n- the type of environments where the utility of reward shaping can be realized, and \n- the impact of the quality of the shaping function on the sample complexity. ", "questions": "Questions:\n\n1/ I couldn't fully understand Assumption 3; please explain with an example and point me where it is used in your analysis. \n\n2/ I have noticed several inconsistencies in the theoretical section, for example:\n- In Eq.(1), $N_h^t$ is already defined, but $N_t$ is not. \n- Does $\\widehat{P}_t$ depend on $h$? In line 168, it is defined based on $N_h^t$ not $N_t$. \n- $\\widetilde{V}$ is a function of $\\mathcal{S}$ only not a function of $\\mathcal{S} \\times \\mathcal{A}$, right? In Assumption 1, line 174, and Algorithm 2, $\\widetilde{V}(s,a)$ is used. \n\nPlease fix them. \n\n3/ The PseudoSub and PathPseudoSub sets introduced in Section 5.1 are clearly explained. However, illustrating these notions for some specific environments (e.g., deterministic chain MDP) would help the reader understand the tightness/improvement of the regret bound presented in Theorem 5.2. \n\n4/ Regarding section 6.2, it would be interesting to consider a formal investigation on the type of environments where the reward shaping function improves/hurts the learning process. See Section 5 of [Dann et al. 2022]. \n\n5/ Regarding section 6.3, how does your work theoretically/empirically relate to [Cheng et al. 2021], who also investigate the quality of shaping functions in improving the sample complexity. \n\nReferences:\n\n[Dann et al. 2022] Dann et al. Guarantees for Epsilon-Greedy Reinforcement Learning with Function Approximation. ICML, 2022. \n\n[Cheng et al. 2021] Cheng et al. Heuristic-Guided Reinforcement Learning. NeurIPS, 2021. \n\n", "limitations": "Their proposed method does not seem to cause any direct potential negative societal impacts. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Post Rebuttal:** I thank the authors for the detailed response that addresses most of my concerns. I hope that the authors can incorporate the details in the rebuttal in the updated version of their draft. I have updated my score accordingly. \n\n----\n\nStrengths:\n\nDespite the practical success of reward shaping (exploiting domain knowledge), theoretical understanding (specifically in sample complexity) is still lacking in the literature. Thus, the formal investigation of this paper is an important step in this direction. The proposed changes to the UCBVI algorithm are theoretically motivated, novel, and easy to implement. \n\nThe related work is clearly discussed in Section 2, and the current work is clearly positioned in the literature.\n\n****\n\nI have checked the theoretical claims in the main paper but haven't checked the proofs (or verified the correctness) in the appendix. However, the theoretical claims seem to match with the intuition. The authors have explained the role of reward shaping in pruning the unnecessary part of the state space in the theoretical section. \n\nSince the paper is theoretical, the conducted experiments are sufficient/reasonable enough to flesh out the essential characteristics of reward shaping (or to validate the paper's central claims).\n\n****\n\nWeaknesses:\n\nFor most of the part, the paper is well written; the motivation and the story are well conveyed. However, the writing of the theoretical section can be improved, and some intuitive examples would also help non-theoretical readers. \n\nAlso, see the questions below. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PHLkOvlKXI1", "reviewer": "Reviewer_Xcjp", "summary": "Reward shaping is used to speed up reinforcement learning, i.e., it is expected to make exploration more focused and to allow the algorithm to find the optimal policy without the need to explore the entire state space. This means that reward shaping is expected to reduce regret. This is exactly what the authors of this paper study within the family of UCB algorithms. These algorithms use an exploration bonus, which can be seen as a shaping reward. The authors assume that some background knowledge is available. This knowledge can be used to design an informative exploration bonus. This assumption is absolutely correct since this is a common requirement in research on reward shaping, e.g., potential-based reward shaping requires the potential function that can be seen as a very similar assumption. Though I have to admit that the multiplicative bounding of the current paper is a bit strong an assumption, but I think that the contribution is still excellent. The theoretical investigation in this paper is relevant and timely. Having some insights into the impact of reward shaping on regret is very useful, and it is remarkable that the authors managed to get rid of the impact of the horizon H. The two uses of shaping information presented in this paper lead to an interesting algorithm. Empirical evaluation on three domains is also provided, and the experiments confirm the merit of the contribution.", "questions": "Initially I wanted to ask how V was determined, but this was clarified in the appendix. I don't have any specific questions.\n\nThis paper studies the impact of reward shaping on regret, and it generated insightful results. I feel that it would be interesting if, either the authors of this paper or someone else with similar skills, analysed  the impact of policy or representation transfer [2] or other tweaks with an assumption of optimism [3] that make the exploration more focused. This is of course beyond the scope of this paper, but it would beneficial for the community if this was explored in the future.\n\n[1] Asmuth, John, Michael L. Littman, and Robert Zinkov. \"Potential-based Shaping in Model-based Reinforcement Learning.\" AAAI. 2008.\n[2] Taylor, Matthew E., and Peter Stone. \"Representation Transfer for Reinforcement Learning.\" AAAI Fall Symposium: Computational Approaches to Representation Change during Learning and Development. 2007.\n[3] Grzes, Marek, and Daniel Kudenko. \"PAC-MDP learning with knowledge-based admissible models.\" Proc. of AAMAS. (2010): 349-358.\n\nFonts in Figures 3, 5, 6 are too small.\n\nThe paper reads well, and I did not see technical problems, but I have to admit that I only scanned the proofs in the appendix. I would probably need to spend a week or more if I wanted to trace all the steps in the proofs.", "limitations": "I am not sure if there is anything to say here.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper addresses a very relevant and useful question, and it provides a convincing and competent answer.\n\nThis is something that can be fixed easily, but the paragraph entitled \"Practical Reward Design and Reward Shaping\" is a bit unclear because the authors seem to be unaware of one topic in the related literature. The authors indicate that the potential-reward shaping methods try to cover all states and the shaping reward is unknown. This is not entirely true because the literature on potential-based reward shaping has good insights into that, and optimism is also studied and required. For an excellent treatment of this issue, the authors could check [1]. I feel that the current discussion in lines 87-96 is a bit misleading because [1] shows that potential-based reward shaping is a principled method too, the right bias is known (i.e., we know which information is required), and the number of explored states can be reduced (even in the Rmax type of algorithms). As I said above, this is a minor comment, but I hope that the authors could address it in this paragraph.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept