Automatic Reward Shaping from Confounded Offline Data
Authors: Mingxuan Li
Junzhe Zhang
Elias Bareinboim
Venue: ICML 2025 poster (2025)
Keywords: Causality
Reinforcement Learning
Reward Shaping
Primary area: general_machine_learning->causality
TL;DR: We study the problem of constructing reward shaping functions automatically via confounded offline datasets from a causal perspective.

Abstract: Reward shaping has been demonstrated to be an effective technique for accelerating the learning process of reinforcement learning (RL) agents. While successful in empirical applications, the design of a good shaping function is less well understood in principle and thus often relies on domain expertise and manual design. To overcome this limitation, we propose a novel automated approach for designing reward functions from offline data, possibly contaminated with the unobserved confounding bias.We propose to use causal state value upper bounds calculated from offline datasets as a conservative optimistic estimation of the optimal state value, which is then used as state potentials in Potential-Based Reward Shaping (PBRS). When applying our shaping function to a model-free learner based on UCB principles, we show that it enjoys a better gap-dependent regret bound than the learner without shaping. To the best of our knowledge, this is the first gap-dependent regret bound for PBRS in model-free learning with online exploration.
Simulations support the theoretical findings.

Automatic Reward Shaping from Confounded Offline Data
Mingxuan Li' Junzhe Zhang?
Elias Bareinboim
Abstract
set of optimal policies after reward shaping guaranteed be unchanged compared with the one without shaping. It has been followed in many practical applications since then.
Reward shaping has been demonstrated be an effective technique for accelerating the learning process of reinforcement learning (RL) agents. While successful in empirical applications, the design of good shaping function is less well understood in principle and thus often relies on domain expertise and manual design. To over- come this limitation, we propose a novel auto- mated approach for designing reward functions from offline data, possibly contaminated with the unobserved confounding bias. We propose to use causal state value upper bounds calculated from offline datasets as a conservative optimistic esti- mation of the optimal state value, which is then used as state potentials in Potential-Basse -Base Re- ward Shaping (PBRS). When applying our shap- ing function to model-free learner based on UCB principles, we show that it enjoys a better gap- dependent regret bound than the learner without shaping. To the best of our knowledge, this is the first gap-dependent regret bound for PBRS in model-free learning with online exploration. Simulations support the theoretical findings.
The core of PBRS is the design of potential functions, which denote the potential of a state or how good a state is. First, people generally rely on domain expertise to compose such potential functions. This dependence on experts' knowl- edge could make designing potential functions expensive and time-consuming One may even argue these extensive human efforts are against the promise of Al that domain ex- perts should be free from handcrafting solutions. Moreover, this designing process endures risks of misspecification due to human biases, which in turn could slow down the training substantially or lead to erroneous agents (Ng et al., 1999) Randløv & Alstrom 1998 Pan et al. 2022). An ongoing line of research exists to simultaneously automate the pro- cess of learning the shaping function and training the online
agent (Pathak et al.) 2017 Yuan et al. 2023 Raileanu &
Rocktäschel 2020 Devidze et al., [202]] Zou et al.] [019]
Ma et al. 2024). However, these methods involve non- trivial optimization procedures relying on prior parametric knowledge over the potential function. The risks of mis- specification persist. In other words, designing potential functions is still significant obstacle when applying PBRS.
An alternative strategy is to learn the shaping function from previous offline data, possibly collected by different be- havior policies or observing human operators interacting with the environment (Brys al.) 2015 Mezghani al.) 2022 Zhang al.. 2024). In their seminal work, Ng et al. 1999 noted that the optimal state value is good candidate for potential functions, characterizing the "state potentials" in the underlying environment. In the field of reinforce- ment learning, the problem of evaluating optimal state value functions from past offline data has been studied under the rubrics of off off-policy learning or batch learning (Sutton) 2018 Levine al. 2020). Several algorithms and methods have been proposed, including Q-learning (Watkins) 1989
1. Introduction
Reward shaping is an effective technique for improving sample efficiency in reinforcement learning. It augments the original environment reward with extra learning sig- nals such that the learner is guided towards nigh-rewardiig states in the environment. Though if not designed properly, there is risk of misleading the agent towards suboptimal policies (Saksida et al. 1997 Randløv & Alstrøm 1998)
Potential Based Reward Shaping (PBRS, Ng et al. 1999
solves this problem by constructing the shaping functions as the difference between state potentials. In this way, the
Watkins & Dayan, 1992). importance sampling (Swami-
CCassal AI Lab, Columbia University, New York, USA DDepartment of Electrical Engineering and Computer Science, Syracuse University, New York, USA. Correspondence to: Mingx- uan Li <ml cow..oooluba........
2015 Jiang & Li 2016). and temporal difference (Precup et al. 2000 Munos et al., 2016).. These
nathan & Joachims
algorithms rely on the critical assumption that there is no unobserved confounding (NUC) in the offline data (Murphy) 2003 2005). One might be able to enforce this assumption by deliberately controlling the behavior policies generat-
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Automatic Reward Shaping from Confounded Offine Data
ing the data. However, in many practical applications, the NUC condition can be difficult to enforce and, consequently, does not necessarily hold. In these cases, directly apply- ing standard off off-policy learning could introduce bias in the estimation, leading to misspecified shaping functions. For example, when some input states to the behavior policy are not fully observed, these states could become unobserved confounders, introducing spurious correlations in the of- fline data. When NUC is violated, the effects of candidate policies are generally not identifiable, i.e., the model as- sumptions are insufficient to uniquely determine the value function from the offline data, regardless of the sample size PPaal 2009 Zhang& & Bareinboim 2019).
2. Challenges of Designing Reward Shaping in the Face of Unobserved Confounders
We will focus sequential decision-makinn setting in the Markov Decision Process (MDP. Puterman (1994) where the agent intervenes on a sequence of actions XI,...;XX XH in order to optimize the cumulative return over reward sig- nals ......, YH: H E N is a finite horizon.
Standard MDP formalism focuses on the perspective of the learners who could actively intervene in the environment. Consequently, the data collected from randomized exper- iments is free from the contamination of unobserved con- founding bias and is generally assumed away in the model. However, when considering offline data collected by passive observation, the learner may not necessarily have deliberate control over the behavioral policy generating the data. Con- sequently, this could lead to confounding bias in various decision decision-making tasks, including off pellipolcy learning (Kallus & Zhou 2018 Lu et al. 2023 Zhhag & Bareinboim 2024). and imitation learning Zhang et al. 2020 Kumor et al. 2021 Ruan et al., (024). In this paper, we will consider an extended family of MDPs explicitly modeling the presence of unobserved confounders when generating offline data.
This paper addresses the challenges of confounding bias in designing potential functions for reward shaping. We study the problem of constructing reward-shaping fune- tions automatically via confounded offline data from a causal perspective. We focus on the environment of Con- founded Markov Decision Processes (CMDPs) where unob- served confounders generally exist at each stage of decision- making ZZhan & Bareinboim (2022); [Tennenholtz et al. (2020). Under CMDPs, we demonstrate the difficulties of manually designing proper reward shaping functions with the presence of unobserved confounding, due to the mis- match in the observed input states. Then we show how one can extrapolate informative shaping functions from con- founded offline data using partial causal identification tech- niques (Manski 1989). Finally, we develop novel online reinforcement learning algorithms that can leverage the de- rived shaping functions improve the learning performance in terms of the sample complexity. More specifically, our contributions are summarized as follows:
Definition 2.1. A Confounded Markov Decision Process (CMDP) M is a tuple of (,, 41 H, FF P) where,
S,X, XY y are, respectively, the space of observed states, actions, and rewards;
U is the space of unobserved exogenous noise;
H E N is a finite horizon;
. IF is a set consisting of the transition function Th
S x X x U + S, behavioral policy Bn : SS x U + X. and reward function FA : :S x X x U + y for every time step h = 1, H:
We propose the first theoretically justified (Thm. 3.1 data-driven method (Algo. 2 for learning reward shap- ing functions from confounded offline data.
P is a set of distributions P,, over the unobserved do- main 24 for every time step ,,... H.
We introduce a model-free UCB algorithm that can improve performance by leveraging confounded offline data using the derived shaping functions (Algo. D
Consider demonstrator agent interacting with a CMDP. For every time step / = ,,...,,,..........,, H. the nature draws an exoge- nous noise Un, from the distribution P(4); the demonstrator performs an action Xn. - (Sk, Un), receives a subse- quent reward Y,, + rr (S,, Xn. Un), and moves to the next state Sa+1 <- Th. (Sn, Xn, Un). The observed trajectories of the demonstrator (from the learner's 's perspective) are thus summarized as the observational distribution P(X, S, [
We derive a novel gap-dependent regret bound for the proposed UCB algorithm. Our analysis reveals how and under what condition (Def. [4.1] the derived shap- ing functions affect the learning efficiency of future online learners (Thm. 4.5)
Due to limited space. related work, experiment details and and respectively.
all the proof are provided in Apps. A and
In the data-generating process described above, for every time step t, the exogenous noise Un2 becomes an unobserved confounder affecting the action Xn. reward Y,, and next state Sh+1 1 simultaneously. Therefore, CMDP is also re- ferred to MDP with Unobserved Confounders (MDPUC, Zhang & Bareinboim (022)) and is subclass of Con-
Notations. We will consistently use capital letters (V) to de- note random variables. lowercase letters (v) for their values, and cursive V to denote their domains. Fix indices i, N. We use bold capital letters (V) to denote a set of random variables and let [V] denote its cardinality of set V. Finally, =z is an indicator function that returns 1 if event Z = z holds true; otherwise, it returns 0.
We will consistently use X, X,5. Y to represent sequences ( Xn), (Si,..., (s and (Yi...., Yn)
2

---

Automatic Reward Shaping from Confounded Offiie Data
(a) CMDP, M
(b) CMDP- Online Learning, Mr
Figure 1. (a) Causal diagram of the CMDP modeling the shaping function designing process; (b) Causal diagram of the CMDP modeling the online learning process under policy d=(
offline data CMDPs. More specifically, nodes represent observed variables Xn. Sn, Yn, and arrows represent the functional relationships Sh, Th, among them. The ex- ogenous noise Un. is often not explicitly shown. However, bi-directed arrows X₁. ++ Y, and X <> Sh+1 indicate the presence of an unobserved confounder (UC) Un, affecting X,. Y, and S simultaneously. These bi-directed arrows characterize the spurious correlations among action Xn, re- ward Vn. and state Sh+1 in the offline data, violating the NUC condition. Such violations could lead challenges in evaluating value function and reward shaping, which we will discuss in the next section.
G
(a) Falling walk.
(b) Target task.
Figure 2. Walking Robot Example.
founded Partially Observed MDP (Shi al., 2022 Miao iet al. 2022, Bennett & Kallus 2024) where Markov prop- erty holds. The following example, inspired by human walk-
ing dynamics (O'Connor & Kuo 2009, Wang Srinivasan 2014), demonstrates an instance of CMDP.
Example (Walking Robot). Consider a scenario where robot learns to walk across hallway. The agent take two actions, small mmall-aa stpp and big-step, denoted as X, = 0 and X, = 1, respectively. Whether the agent can move forward 1L depends on both the step size, Xb. and the current body stability status, Fn. It's defined as La+1 + Ln + 11((-F//4 (X,, = Un)) V (Fr, A -X,)]. The body stability modeled as Fn+1 + -X,, h if the body is in stable status Fn. 1 or Fa+1 <- ~X,, @ Un. if it is not stable Fi, 0 and needs adjust step size accordingly. The required step size to stay stable is modeled as uniform random noise Un. The agent receives a reward Y, = 1 if it reaches the goal location or it moves forward. It receives a reward V₁=- = -1 if it cannot stabilize the body accordingly. Formally, Yn <- 1 if La+1 G otherwise Vn 1[(FF, A
2.1. Sitential-Based Reward Shaping
A policy π in CMDP M is sequence of decision rules S - X, for every step h = 1,.... . H, mapping from state to action. Similarly, Ta (3), sn.) is stochastic policy mapping from state space S to a distribution over action space X. An intervention do( is an operation that replaces the behavioral policy 3h in model M with the decision rule Th for every step h. Let M- be the submodel induced by intervention (.). Fig. lb shows the graphical represen- tation of the data generating process in the submodel M bi-directed arrows are now removed.
The interventional distribution Pa (X,3, S,,, Y) is defined as the joint distribution over observed variables in Mg. ie..
X₁ - Uk) v (FA Xx)] - 1[-2%, A XA $ Un].
In this example, body stability Fj affects whether the robot can step forward. We will consider offline data generated by two demonstrators. When the robot is currently unstable FA = 0, competent demonstrator following a behavioral policy (( Xx. +- Un. takes a step in the size of exactly the latent noise Up. As a result. it will always transit from being unstable F2 = 0 to a stable status F = -X,, + UA = -U, + Un = 1. On the contrary, an incompetent demonstrator following 88² X + - will always attempt to remain unstable Fa+1 -X, A e Un = Un +
Pa (o 3,
P(s1)
II h=1
T (2:A | 8h)
(I)
Tn(sn, The sh+1 Rr, Is mn)
where the transition distribution Ta and the reward distribu- tion R2 are given by, for ......,I. H,
2, /. 11 1v=n(aa.
(2)
Un = even when the opposite is preferable.
(,, = / 1g (h(
(3)
Fig. aa shows the graphical representation (i.c., causal di- agram) describing the generative process generating the
For convenience, we write the reward function Rr (s, x) as the expected value E, yR x.)).
3

---

Automatic Reward Shaping from Confounded Offine Data
For reinforcement learning tasks, the agent's goal is to learn an optimal policy xt maximizing the cumulative reward in CMDP M. i.c., n² = arg max, En
reinforcemean
If one sets the potential function Φn == VA the reward shap- ing will add the supplemental signal in favor of transitioning
Σー= Yn In analysis, we also evaluate the state value function (+)= = Ex -h h Yt | Sh = s| following a policy π for every step 1, 1,............... H. A state-action atate-action
from unstable state Fh- = 0 to stable state Fh+11 = 1,
&n (Ta+1 O, Fa+1 = 1) S (T+, 0, Fv. = 0) = 0.5
On the other hand, if one applies standard off-policy meth: ods using offline data generated by the competent behavioral policy / it leads to the following value function,
action value function is defined as Q7 = xx -n Y, Sh = 8, XA = st..
Reward shaping is popular line of techniques for incorpo- rating domain knowledge during policy learning. Common approaches such as Potential- Sotential-Based Reward Shaping (PBRS, Ng et a (1999)) add supplemental signals to the reward function so that it would be easier to learn in future down- stream tasks without affecting the optimality of the learned policy. The following proposition establishes the validity of PBRS in CMDP with finite horizon.
V/ (hn = 0, F4 = 0) = 10, V (T+, = 0, Fv. = 1) = 10
This seems to suggest that being stable does not improve the robot's performance. If we set the potential function v.v% the reward shaping will not encourage the robot
Φ == V, to be stable. More interesting, if we compute the value v function from offline data generated by the incompetent  behavioral policy B(2)) we have the following
Proposition 2.2. For a CMDP M. let M' be a CMDP obtained from M by replacing the reward function with the following, for every time step h I,..., H,,
replacing
V. h
0, Fr 0) = 23, 23, ( (Ln 0, Fr. 1) 42 (L,, (
Being stable F3 = 1 appears to lead to lower future returns. If one sets the potential function on := v/22, shaping will even penalize the robot to transit from being un- stable Fh = 0 to being stable Fh-1 = 1, which contradicts the underlying system dynamics.
T/e :=:=rA TA + (S - (Sh),
(4)
, the reward
where Th is the reward function in M: (n(:)) : + IR is a real valued potential function and (s) = O. Then,
The above example shows that when unobserved con- founders generally exist, naively computing potential func- tions from offline data could lead to biased evaluation. Shap- ing reward with a biased potential function could lead to sub-optimal performance, encouraging undesirable behav- iors. Indeed, when the NUC does not hold, the transition function T and reward function R are generally not uniquely discernible from the offline data, regardless of the sample size (Pear 2009). For the remainder of this paper, we will introduce a robust procedure to design potential functions from confounded offline data, and how to leverage these " potential functions for future online learning tasks.
That is. every optimal policy in M will also be an optimal policy in M', and vice versa.
reward In other words, PBRS modifies the reward function in the system to encourage the learning agent to visit states with high potential in future return. At the same time, the agent is penalized for visiting states with low potential. More impor- tantly, optimal policies remain invariant across this shaping process, i.e., every optimal policy in the after-shaping model M' is guaranteed to be optimal in the original model M.
gu
Designing the potential function is central problem when applying PBRS. The optimal state value functions V/ (s) = VI (s) Ng et al. 1999) are a good candidate for measuring state potential. When the condition holds, is possible to compute such optimal value functions using standard off- policy methods (Sutton 2018). However, when unobserved confounding
3. Robust Potential Functions from Confounded Offline Data
deseeveee confounding generally exists, evaluating value functions from confounded data could introduce bias in the shaping process, promoting states with low potential. The following example demonstrates such challenges.
Our goal is to upper bound the optimal state value for on- line interventional agents, the ones that cannot utilize con- founders, from potentially confounded offline datasets. In- stead of attempting to identify the underlying reward and transition distribution under confounded datasets, we bound them for every s. h E S x X' x S x [H] following similar partial identification Sxategies in Manski 1989).
Example 2 (Confounded Potential Functions). Consider again the Walking Robot in Example I Computing the optimal state value function (Ln, Pt.) from the ground- H.,
Ta (5 8/) < Th s 5 P + (-(ss) ))
(5)
P. (M + (-x
truth model M gives, for every step h = 1,..., .......
Rn( < R,,s, x))
(6)
where R, (s. x) = =E|Y,|S, = =, = 2], 7. (s. x, =
V (La = 0, Fr. = 0) 5.0, (Lk- = 0, Fr = 1) = 5.5
Ph (A( = s'(Sn = 8, Xn = x) and (z(s))) = Pa =
4

---

Automatic Reward Shaping from Confounded Offiiee Data
Skk s) are all empirical estimations from the offline dataset. b is known upper bound on the reward signal,
CMDP with horizon H. For state-action pairs that not visited in the dataset, we will skip those state-action en- tries directly To summarize, the overall algorithmic pro- cedure to calculate causal bounds runs as standard value iteration (Sutton 2018) except that we update the state val- ues backwards in time, i.., from V h-1 to VA by Eq. (8) skip unvisited state-action pairs and take the minimum ac- cording to Corol. 3.2 at last. Algo. in App. shows the full pseudo-code for approximating the optimal value upper bound from offline datasets. Now we can calculate the pro- posed state potentials for the Walking Robot problem and verify if it upper bounds the true optimal state values.
Y, S b. Similar to the bounding approach developed in (Zhang & Bareinboim| 2024). we apply the above bounds to the Bellman Optimal Equation (Sutton & Barto 2018) and arrive at the following Causal Bellman Optimal Equation that calculates the optimal state value optimistically from the confounded offline datasets.
Theorem 3.1 (Causal Bellman Optimal Equation). For CMDP environment M with reward Yn S b, IR the optimal value of interventional policies, (s), Vs E S, is upper bounded by Vi (s) I Vn(s) satisfying the Causal Bellman Optimality Equation. for every step h = -I....,F H,
Example 3 (Potential Functions Calculated for Robot Walk- ing). Recall that running value iteration in the interventional policy space, we have the optimal state value for Example
Vn(s)= maxx [P(((])s) (R)(,,)) + B7 [V (++1(()))
+ Pa Pa((zzls) max (ixx)(()))))
(4A = 0, FA = 0) = 5.0, V (LA = 0, Pi = 1) = 5.5.
and V (+) = 0 for all state 8 S.
As we have shown, directly calculating state value from offiine datasets cannot yield informative potential functions. While with Corol. 3.2 we can extract the following potential functions from the same offline datasets,
Compared with the original Bellman Optimal Equation, ours accounts for the uncertainty brought by confounders in the offline dataset via an extra term, b max./ Vn+1 (s'). This represents the best rewards that the agent could have achieved from those "unselected" actions, i..., Ph (s.)s) With the Causal Bellman Optimal Equation, we can robustly upper bound the optimal state values from a confounded offline dataset generated by CMDP M.
(4, = 0, F2 = 0) = 9.0, on = 0, Fr = 1) = 9.5,
which perfectly upper bound the optimal state values and encourages the agent to stay in stable status. From the interventional policy space optimal value and our potential functions, we see that for interventional agents, stability is always preferred, which can be achieved via taking small steps (X, 0) every time. This also aligns well with the intuition that people glide with small steps when walking on slippery surfaces. See App. B for the the full confounded state values, optimal values and calculated bounds.
When multiple offline datasets from different behavioral policies available, each of them provides unique per- spective on the true underlying CMDP without necessarily overlapping state space coverage. Since the upper bounds calculated for each state from different datasets are all valid according to Thm. 3.I taking the minimum yields the tight- est estimation for the optimal state value.
4. Efficient Online Learning with PBRS
Corollary 3.2 (Unified Causal Optimal Upper Bound). Let the causal optimal value upper bound estimated from offline datasets D(G) be (1))_ ,i = 1,2, ....
In this section, we will apply the derived potential function from the confounded offline data to improve the agent's s performance in an online learning task. For a CMDP M. let Φ1. h = 1,..., H, be the potential functions derived in the previous section. We first apply reward shaping and obtain an augmented CMDP M' following the procedure described in Prop. 2.2
2.., N, the unified causal op-
timal upper bound is defined as V (s) = min SED( v/A) (s)
where E (D)) means state s visited at step h in D(i) and satisfies (s) < (s) for all s.
In actual computation, to avoid over-estimation brought by bootstrapping on the highest value state, we clip the optimistic bonus for the optimal transitions and calculate the value update as follows,
In the augmented CMDP M', an online learning agent attempts to learn an optimal policy T² by performing in- terventions for repeated episodes k == 1, 1,..,, K. For every episode k. the agent picks a policy n², performs intervention do(xx*). and receives subsequent outcomes. The cumulative regret after K 0 episodes of interventions in the augment
(0 Qhe x) (-als) (b+ min max v44 (=")(s"), (s*), wn))
+ p()) (xls) (100 (s, + Σ Th (H (2
(8)
FFor a state not visited in any of the offline datasets, we can simply set the bound optimistically as (s(s) = (H - hhb..
where Wn1- = (H - h)b is the maximum possible next state value an optimistic transition should receive in an episodic
"This can be done by adding supplemental signal Φa (S++1) on (Sn) to every observed reward V,,
5

---

Automatic Reward Shaping from Confounded Offiiee Data
CMDP M' is defined as the sum of the gap between the optimal value function VT following optimal x² and the value function VT induced by policy nh. Formally,
shaping. We start with writing the learned Q-value under shaping at step h episode ls following Algo. 1 as follows,
x)) =
K Σ
E. [Regret(K)) = EM
(1 (S)
Σ o Un -m((6) + (Prh W - P dn+1) + bi).
A desirable property for the agent is to achieve sublinear regret EM [Regret(K)) (K)] = ( This means that it is able to converge to an optimal policy n².
where we use Ph, to denote the empirical transition of cpisode kg. That is, for the value of a function mapping from state space to real numbers, f S + R,its value given the next state s' in episode k; as input is denoted as, f(s') (TPh (s,, Similarly, we write the expected value of such function f over the transitions of an online CMDP under re- ward shaping. M'',a, ,as (s,, x)) Me,, [J(*') ar). of is the cumulative learning rates defined as a = (1 and of a (1 aj). Note that we also assume deterministic reward functions for notation wise simplic- ity (Jin et al.] 2018). With the notations above, we bound the difference between the learned Q-value and the optimal Q-value with high probability in both direction.
We propose an online learning algorithm based on a model- free learner. Q-UCB (Jin et al. 2018). to leverage the po- tential function @ extrapolated from offline data. Details of the algorithm is described in Algo. [ Compared with the original Q-UCB, we make a few modifications for Q-UCB to work with PBRS: (1) Zero initializing the Q-values; (2) Using potential function dependent UCB bonus and value clipping: and finally, (3) Incorporating shaped reward during learning updates. See also App. F for the pseudo-code of the vanilla Q-UCB, As in the original Q-UCB, we have visi- tation counter, (s,, J..), for the state-action pair (k) at step h. Note that the UCB bonus uses as its denomi- nator under the square root, which is the visitation count of (sh, vy ) at the beginning of episode k. The counter is updated after assigning t. (s), =n) < NN. (sh. kn, + 1. We use the same adaptive learning rate as 0t = H+1 and
Lemma 4.2 (Bounded Differences Between Q% and QT)) With probability at least - 2p. the difference be- tween the learned Q-value at the beginning of episode k and step h and the optimal Q-value can be bounded 0 S (5,
(7(5x)) S af(-QR + Ei ot N h+1 - f Vh (s, + -.h where by is the UCB bonus as in Algo.
H
define 2 - log (SS| /p) where p' 2p is the probabil- ity of the event when the difference between learned and the optimal Q- Q-values is bounded.
The final expected regret bound can be built upon this bounded Q-value difference via a gap-dependent decom- position. We can then bridge this gap dependent regret de- composition with the difference between learned Q-values and optimal Q-values on non-optimal actions based on the fact that (s, - Q7, x) 2 (s, (Lem. H.7
As we shall see later in experiments (Fig. using con- founded values in Q-UCB Shaping usually impairs the train- ing efficiency rather than helping. While using potential functions that upper bound the optimal state values, learning efficiency is significantly boosted. This observation also res- onates with the optimism in the face of uncertainty (OFU) heuristics in reinforcement learning (Gupta et al.) 2022 Brafman & Temnenholtz] 2002 Kearns & Singh 2002).. We formalize this observation as the following condition.
H
E [Regret (K) EM'
Σ
Σ
An (5 x
1h=1
Σ K
Definition 4.1 (Conservative Optimism). The learned po- tential function is conservatively optimistic if it satisfies, (x) < Φn (s) < H for all S, h E S [H] where
(1-
(Qt ah) - ( 2x11) + H.
k=1k=1
Utilizing the function clip [z|6] = = 1 > 8 x. 8 E R introduced by Simchowitz & Jamieson 2019) and its
(s) max E. zEnl
Σ Yv
(9)
properties (Lem. G.2 Lem. G.3). we can further write the
difference between learned Q-values and optimal Q-values as a recursion,
This condition ensures that the potential function upper bounds the optimal state value while being informative by not exceeding H (assuming Y, < 1).
A (oht aht
@h ah) - (hh I clip
3bg
2H
Next, we will show that this is indeed a sufficient condition for guaranteed sample efficiency improvement under reward
+ (1+
a
(Q
1
'A function fn) o(g(n)) if for all 0, there exists >>>0 O such that f(n) < eg(n) for 2
where we unify the optimality gaps of each state action pairs across time steps via (8) min, (s x) =
6

---

Automatic Reward Shaping from Confounded Offiiee Data
Algorithm 1 Q-UCB Shaping
pm m Un (8), after running algorithm Algo. 7 for K episodes of length H, the expected regret is bounded by,
1: Input: Potential function Φn (s), Vs, h. Const. c > O.
2: (s, O, (s) 0, v(s, xr, h) E S x X [A]]
3: Calculate maximum potential, 2. = max, (($).
Ho (SAT)
H log (SAT)
4: for k k= 1 to K do
S.mESuba
5: Observe initial state $1-
6: for à = 1 to H do
where T = KH is totally number of steps; Sub is the set of aseudo-suboptimal state action pairs and A ((,,)) = ming (5, x). for all E [H].
7: Take action In- = arg max, Q (sh, t).
8: Observe 81+1, yh-
9:
Update visitation counter and UCB bonus, (s,, < (su, 2n,) + 1, bt ev H H Calculate shaped reward,
See App. H.3 for the full version regret bound and proof de- tails. The first part of the regret is for the set of state-action pairs which offline learned shaping functions would cut unnecessary over explorations resulting in an order of mag- nitude better dependence on the horizon factor H. This improved dependence on H even matches with state-of-the- art Q-learning variant in the literature (Xu et al. (02T). The second part corresponds to the set of state-action pairs that our shaping function cannot decide when to stop exploring during learning matching the gap- gap-dependent regret bound of the vanilla Q-UCB (Yang et al.) 2021.
10:
Vh = Uh + +h+1($s41)) - -r (sh).
11:
Update Q-value,
2ht (sh. 2n) = (1 - as) 2 + aclth + V (86+1)) + by).
12: Update value function, V min( max, tht 13: end for
14: end for
min, Vi (+) 2% ()) where x is a suboptimal action. Though we can already solve the recursion and calculate the regret based on the property of the clip(.) function (Lem. G.3 direct summation cannot reveal the benefits of reward shaping to the online learner. Inspired by Gupta et al. (2022), we denote the set of state-action pairs that are far from being even the second best choices as pseudo- suboptimal state-action pairs based on the minimum optimal gap, A (ss, z).
5. Experiments
In this section, we show simulation results verifying that: (1) Q-UCB with our proposed shaping function enjoys bet- ter sample efficiency, and (2) the policy learned by our shaping pipeline at convergence is the optimal policy for an interventional agent. The baselines include vanilla Q-UCB (No Shaping), Q-UCB shaping with minimum state values learned from offline datasets (Shaping + Min Beh. Value), shaping with maximum offline state values (Shaping + Max Beh. Value), and shaping with average offline state values (Shaping + Avg Beh. Value). We test those algorithms in a series of customized windy MiniGrid environments (Zhang) & Bareinboim 2024 Chevalier- -hevalier-Boisvert et al. 2018).
Definition 4.3 define the set of
State-Action Pairs), We state-action pairs as,
Suba = =s E S x X 3h, (s, S (s)), (10)
where (s, = y on d. + 2B (8)) x] + A (s, x).
We use tabular state-action representations and the rewards are all deterministic in those environments. There is a step penalty of 0.11, +0.2 for getting a coin, 0 for reaching the goal, and 1 for touching the lava. The episode ends immediately when either a goal/lava grid is reached the episode length hits the horizon limit. In windy grid worlds, the state transition is determined by the resultant force of both agent's action and the wind direction if the agent tries to move. For example, if the agent wants to move right when there is a north wind (wind blowing from the north), the agent will end up being in the lower right grid concern- ing its original location instead of the right-hand side grid. However, the wind direction can only be observed by more capable behavioral agents. In our collected offline datasets, wind direction is thus a hidden confounder forming a CMDP. See App. D for detailed experiment setups and more results.
With this set of pseudo-suboppimal state-action pairs, we show that the total number of visits made to such pairs during training can be bounded, contributing to reduction on our final regret bound in Thm. 4.5
Lemma 4.4 (Bounded Number of Visits Suba). The number of visits to (s.z) Subs. 2)) is
bounded by, 1 < 16c² 16
By treating the summation of clipped terms in the regret differently with respect to whether the state action pairs belong to the set Suba or not, we arrive at two-part regret bound that both demonstrates the efficiency gain of reward shaping and subsumes prior result on the gap-dependent regret of Q-UCB (Yang et al. 2021).
Theorem 4.5 (Regret Bound of Algo. D. Given a po- tential function dr (.), with its maximum value defined as
In Windy Empty World (Fig. 3a there is a uniform wind
7

---

Automatic Reward Shaping from Confounded Offine Data
40
40
40
40
40
33
40
40
+0
40
40
40
38
B B3
3
40
40
40
40
40
40
40
40
40
40
40
40
40
10
(a) Windy Empty World.
(b) LavaCross (easy).
(c) LavaCross (hard).
(d) LavaCross (maze).
Figure 3. Windy grid worlds. The blue arrows and circles in the lower right of each grid denote the possible wind directions. The flag the goal and the orange tile is the lava. The agent's 's task is to reach the goal quickly without touching lava and collect coins if possible.
30
Lurre Regett
10
0. 02
10
10 Restressenn Sugpa
2.
Seskstrant State le0
Eevonarnir Stgge 106
Rescnzenon Sugns
(a) Windy Empty World
(b) Windy LavaCross (easy)
(c) Windy LavaCross (hard)
(d) Windy LavaCross (maze)
Figure Cumulative regrets windy grid worlds. Lower better. Orange curve ours.
from each direction and big chance for no wind (denoted as a hollow blue circle). As an interventional agent, there isn't much extra information it can utilize from the shap- ing function. Thus, in Fig. 4a the cumulative regret of our method and other shaping baselines are on par with each other. Note that we do expect the vamilla Q-UCB not per- form well in all our windy grid worlds mainly because that it assumes reward being in [0, 1] and initializes overly opti- mistically as H. Yet, our Q-UCB Shaping (Algo.[) [ lifts this restriction and learns well with simply zero initializations.
gets punished constantly by taking the risky northern route. Only our proposed shaping with causal offline upper bound provides the correct learning signal and helps the online interventional agent converge efficiently to the right optimal policy (Fig. 5a Fig. 5b).
In more challenging LavaCross maze (Fig. 3dl. there three coins. Though the lower left L-shaped route is still safe option, there is a good chance for the agent to get the middle coin given the wind distribution Fig, 4d The other two coins are traps that only behavioral agents sensing the wind could get. If the interventional agent shaped with such confounded values, there a high chance that will be pushed into lava by the wind. As result, we see in Fig. 4d that shaping with our causal upper bound helps the agent converge and find the right optimal policy (Fig. 5c).
(a) Easy mode
(b) Hard mode
(c) Maze mode
6. Conclusion
Figure 5. Optimal polices learned by proposed method.
In this work we study the problem of designing potential- based reward-shaping functions automatically with con- founded offline datasets from a causal perspective. Though the optimal state value is competitive candidate for state potentials, it's not easily accessible or identifiable from confounded offline datasets. We tackle this challenge by extending the Bellman Optimal Equation to confounded MDPs to robustly upper bound the optimal state values for online interventional agents. Then, we propose modified model-free learner, Q-UCB Shaping, which has better regret bound than the vanilla Q-UCB when using pro- posed potentials that upper bound the optimal state values. The effectiveness of our method is also verified empirically.
In both Windy LavaCross easy mode and hard mode, there is a strong north wind and only slight chance of being still across the map. We see from Fig. BiggBbbeas and Fig. 3e that only the lower left L-shaped route is safe for an interventional agent. We provide offline datasets from both a conservative behavioral agent taking the safe route and an adventurous behavioral agent taking the risky northern route. The ad- venturous behavioral agent only moves when there is no wind. This fact is not reflected in the offline datasets though. When shaping with such values, the mixed learning signal from the adventurous agent slows down the learning process since the interventional agent cannot observe the wind and
8

---

Automatic Reward Shaping from Confounded Offline Data
Acknowledgements
Brys, T., Harutyunyan, A., Suay, H. B., Chernova, S., Taylor, M. E., and Nowé, A. Reinforcement learning from demonstration through shaping. In Yang, Q and Wooldridge, M. J. (eds.), Proceedings of the Twenty- Fourth International Joint Conference on Artificial In- telligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, pp. 3352-3358. AAAI Press, 2015. URL http:// ottp://aaa........aatttt////////
This research was supported in part by the NSE, ONR, AFOSR, DoE, Amazon, JP Morgan, and the Alfred P. Sloan Foundation.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here. One major reason that the potential-baae -battilll-baadddeee reward-shaping framework we considered does not alternate the optimal policy of the agent, which is an inherent property of the problem. Our proposed method solely serves as an acceleration for training such agents.
Chen, Z., Maguluri, T., Shakkottai, S., and Shanmugam, K. Yyapunov theory for finite-sample guarantees of markovian stochastic approximation. Oper. Res., 72(4):
1352 1367, 2024. doi: 12wp://////PP.222222222222 URL wwt.:o/gg/......... 12w.0 220.:o/.................... 22022.022
49
Chevalier-Boisverr, M., Willems, L.., and Pal, S. Minimal- istic gridworld environment for gymmasium, 2018, URL
References
https://qithis wew.//aaaaaaoounaaaaaea.aa Minigrid
Ball, P. J., Smith, L. M., Kostrikov, I., and Levine, S. Effi- cient online reinforcement learning with offline data. In Krause, A., Brunskill, E., Cho, K., Engelhardt, B., Sabato, and Scarlett, J. (eds.), International Conference on Ma- chine Learning, ICML 2023, 23-29 July 2023, Honolud,, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pp. 1577-1594 PMLR, 2023, URL https: htts:://procceeeee a 23a. htm
Dann, C. and Brunskill, E. Sample complexity of episodic fixed-horizon reinforcement learning. In Cortes, C., Lawrence, N. D., Lee, D. D., Sugiyama, M., and Gar- nett, R. (eds.), Advances in Neural Information Process- ing Systems 28: Annual Conference on Neural Infor- mation Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada, pp. 281 2826, 2015. URL https://proceedingg/ nww.:gs.neeurige 7 72015/hash/39ffeeeee etwp:es42eeeee22e222222 html
mlr wtwps//wp.ssss..//ee
Banach, S. Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales. Fundamenta Mathematicue, 3:133-181, 1922. |nthtt::/ serranticscoolar.corgr htt.://cccccola.o.ooo/////ooooos
Dann, C., Lattimore, T., and Brunskill, E. Unifying PAC and regret: Uniform PAC bounds for episodic reinforce- ment learning. In Guyon, I., von Luxburg, U., Bengio, S., Wallach, H. M., Fergus, R., Vishwanathan, S. V. N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pp. 5713- 2017. URL https: http:s//ppooeednnnnnneerersso.os
5
Bennett, A. and Kallus, N. Proximal reinforcement learn- ing: Efficient off- off-policy evaluation in partially observed markov decision processes. Oper. Res., 72(3):1071-1088
2024. doi: 10. 10.128870PRE.2221100777 7/doi . hrgpi.org//e 10. wttpo////.......prrre.e... 2021. 0781
URL https:
Bertsekas, D. P. and Tsitsiklis, N. Parallel and distributed computation. Athena Scientific, Belmont, Massachusetts, 1989. URL httltttts///a/ http://aa...maaniccccccces www.nticscnholrrrrrrre.a org/ Ctrr/rrruussaa ID: 60492634
a 836662-Abstract.hh html
Dann, C., Mansour, Y., Mohri, M., Sekhari, A., and Sridha- ran, K. Guarantees for epsilon-greede reinforcement learning with function approximation. In Chaudhuri, K., Jegelka, S., Song, L., Szepesvári, C., Niu, G., and Sabato, S. (eds.), International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Mary- land, USA, volume 162 of Proceedings of Machine Learning Research, pp. 4666-4689, PMLR, 2022. URL https: fttps://prrceed: www.mml..........m.... http:///prrooddddssgn....sssssrs 62/d ann22a.html
Bhargava, P., Chitnis, R.,
Geramifard, A., Sodhani, S., and Zhang, A. Sequence modeling is a robust contender for offline reinforcement learning. arxiv, 2023. httst
7/doi 1ta.bl.ogg/...435//zziiiiii.
113550/arXivv 2 2305 14550
Brafman, R. I. and Tennenholtz, M. R-MAX A general polynomial time algorithm for near-optimal reinforce- ment learning. J. Mach. Learn Res., 3:213 2002. URL https:/ //pprr///m....////////// jmir. wttp:ppppppppppapppppo an02a html
Devidze, R., Kamalaruban, P., and Singla, A. Exploration- guided reward shaping for reinforcement learning under
9

---

Automatic Reward Shaping from Confounded Offinee Data
sparse rewards. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NewrlPS 2022, New Orleans, IA, USA, November 28 December 9, 2022, 2022. URL / .nips. httpaaccccaaprrriiless//pppeee/p (aaac2111hhoubbbbeee20000.6.eee2 cract-Conference..
doi: 10.1 10.1109/AACCESSS.044330045. URL https
//doi. 1ttp:///1.1111/////.1... 2024 3504735
Jiang, N. and Li, L. Doubly robust off-policy value evalu- ation for reinforcement learning. In Balcan, M. F. and Weinberger, K. Q. (eds.), Proceedings of The 33rd Inter- national Conference on Machine Learning, volume 48 of Proceedings of Machine Learning Research, pp. 652- 661, New York, New York, USA, 20 22 Jun 2016. PMLR. URL htt.tttp://ppoceeeeee ngs ml r press/ v 1angl6.hum
Fujimoto, S., Meger, D., and Precup, D. Off-policy deep reinforcement learning without exploration. In Chaudhuri, K. and Salakhutdinov, R. (eds.). Proceedings of the 36th International Conference on Machine Learning, ICMI. 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learning Reseurch, pp. 2062 PMLR, 2019, URL http:://rocceeee dings. Bings.mlr wwm.m.r.ppp. press / v97 / fu 9a. html
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. Is q-learning provably efficient? In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pp. 1188884877
Guo, H., Cai, Q., Zhang, Y., Yang, Z., and Wang. Z. Provably efficient offline reinforcement learning for par- tially observable markov decision processes. In Chaud- huri, K., Jegelka, S., Song, I.., Szepesvári, C., Niu, G., and Sabato, S. (eds.), International Conference on Ma- chine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 8016 8038. PMLR, 2022. URL ml r. prw.s ppress/vv62/g
2018. URL cC [cc_appprr220013//asssc/ca133113 57E9E26a31E72cf-AB6
Kakade, S. M. On the sample complexity of reinforcement learming. University of London, University College Lon- don (United Kingdom), 2003.
Kallus, N. and Zhou, A. Confounding rrouut policy im- provement. In Bengio, S., Wallach, H. M., Larochelle, H., Grauman, K., Cesa-Bianchi, N., and Garnett, R. (eds.), Advances in Neural Information Processing Sys- tems 31: Anmual Conference on Neural Information Pro- cessing Systems 2018, NewrIPS 2018 December 3-8, 2018, Montréal, Canada, pp. 9289-9299, 2018 URL
https://procest
uo22a html
Gupta, A., Pacchiano, A., Zhai, Y., Kakade, S. M., and Levine, S. Unpacking reward shaping: Understanding the benefits of reward engineering sample complexity. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho, K., and Oh, A. (eds.), Advances in Neural Infor- mation Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurlPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022. URL http: http://papprrr....ccccc.c cc/p aper wwtpe///aaapee/00222aaaa22333333 (aaa627777fff000077775555----
72018 22013//888/220022244400008111119
Kang, B., Jie, Z., and Feng, J. Policy optimization with demonstrations. In Dy, J. and Krause, A. (eds.), Pro- ceedings of the 35th International Conference on Ma- chine Learning, ICML 2018, Stockholmsmässan, Stock- holm, Sweden, July 10-15, 2018, volume 80 of Pro- ceedings of Machine Learning Research, pp. 2483-2483. PMLR, 2018. URL Tress/vB0/kanee 18a. html
Ference.htm
Harutyunyan, A., Devlin, S., Vranex, P., and Nowé, A. Ex- pressing arbitrary reward functions potential-based advice. In Bonet, B. and Koenig, S. (eds.), Proceed- ings of the Twenty-Ninth AAAI Conference on Artifi- cial Intelligence, January 25-30, 2015, Austin, Texas, USA, pp. 2652-2658. AAAI Press, 2015. URL hitp: //www. wwww.aaai..o .org wwwp:/aaaa..rgocc/o//aaoao index pwwpsx/.pppAAAAAAA/p A115/paper/view/99
mll
Kearns, M. and Singh, S. Finite-sample convergence rates for q-learning and indirect algorithms. In Kearns, M. J., Solla, S. A., and Cohn, D. A. (eds.), Advances in Neural Information Processing Systems 11, [NIPS Conference, Denver, Colorado, USA, November 30- December 5, 1998], pp. 996-1002 The MIT Press, 1998. URL http:
Ibrahim, S., Mostafa, M., Jnadi, A., Salloum, H., and Osi- nenko, P. Comprehensive overview of reward engineer- ing and shaping in advancing reinforcement learning applications. IEEE Access, 12:175473-175500 2024.
//pppers.ripo.ccpppppr///131111. 1lla---ooerrenee---ttt-a-------- g-and-imdireect-algo--1-
10

---

Automatic Reward Shaping from Confounded Offiiee Data
Kearns, M. J. and Singh, S. Near-optimal reinforcement
Learning Research, pp. 1401-1410. PMIR, 2022, URL
learning in polynomial time. Mach. Learn., 49(2-3):209- 232, 2002. doi:
https://proceed: ngs. m mrlr. press/v205/m e Sighani22a.htm..
URL http
s:
Miao, R., Qi. Z.. and Zhang, X. Off-policy evaluation for episodic partially observable markov decision processes under non-parametric models. In Koyejo, S., Mohamed, S., Agarwal, A., Belgrave, D., Cho. K., and Oh, A. (eds.), Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Processing Systems 2022, NeurIPS 2022, New Orleans, LA, USA, November 28- December 9, 2022, 2022. URL http:
Kumar, A., Zhou, A., Tucker, G., and Levine, S. Con- servative q-learning for offline reinforcement learning. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems 33: Anmual Conference on Neural Information Processing Systems 2020, NeurlPS 2020, December 6-12, 2020, virtual, 2020. URL https:
//pppeessniis..cc/ppppeeeee_eeee htt.:ppppee...llsepppppaapeeee 022 022hassh//Oaffa22775533333 6b789 Dee09--bbbrraat-Cooeeee htm
hash 0ea1:/222220011/2555322111128282
2 2-Abstract.her html]
Kumor, D., Zhang. J., and Bareinboim, E. Sequential causal imitation learning with unobserved confounders. In Ran- zato, M., Beygelzimer, A., Dauphin, Y. N., Liang, P., and Vaughan, J. W. (eds.), Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, De- cember 6- 14, 2021, virtual, pp. 14446699168800 2021. URL ht http:://pprcceceeo www.gggw.......... /2021
Munos, R., Stepleton, T., Harutyunyan, A., and Bellemare, M. Safe and efficient off off-policy reinforcement learning. In Advances in Neural Information Processing Systems, pp. 1054-1062 2016.
Murphy, S. A. Optimal dynamic treatment regimes. Jour- nal of the Royal Statistical Society Series B: Statistical Methodology, 65(2):331-355 2003.
Murphy, A. A generalization error for q-learingg Journal of Machine Learning Research, 6:1073-1097, 2005.
Levine, S., Kumar, A., Tucker, G., and Fu, J. Offline rein- forcement learning: Tutorial, review, and perspectives open problems. arXiv preprint ar w0Xv:20005006643, 2020.
Nakamoto, M., Zhai, S., Singh, A., Mark, M. S., Ma, Y., Finn, C., Kumar, A., and Levine, S. Cal-ql: Calibrated offline RL. pre-training for efficient online fine-tuning. In Oh, A., Naumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S.
Lu, M., Min, Y., Wang, Z., and Yang. 7. Pessimism in the face of confounders: Provably efficient offline reinforce- ment learning in partially observable markov decision processes. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL https: // wet.:/iwww.....eeeemmeeeeeeeeeee for/m/ormmmm// www.ormmmiidppppooo.... UbV
in Neural Information Processing Systems 36: Annual Conference on Neural Information Processing Systems 2023, NewrlPS 2023, New Orleans, LA, USA, December 10 - 16, 2023, 2023. URL http: / 2epp://222/haah/c44442222eeeeee files 19906aald699-bbatracc-ccooo Cow.zaaactCooffeencee
net.
Ma, H., Sima, K., Vo, T. V., Fu, D., and Leong, T. Re- ward shaping for reinforcement learning with an assis- tant reward agent. In Forty-first International Confer- ence on Machine Learning, ICML 2024, Vienna, Austria, July 21-27, 2024. OpenReview.net, 2024. URL wtt.ee/eooorrmmiiaaaaaaaaaeeeee
Ng, A. Y., Harada, D., and Russell, S. Policy invariance under reward transformations: Theory and application reward shaping. In Bratko, I. and Dzeroski, S. (eds.), Proceedings of the Sixteenth International Conference on Machine Learning (ICML 1999), Bled, Slovenia, June 27 - -30, 1999, pp. 278-28228 Morgan Kaufmann, 1999.
Manski, C. F. Nonparametric bounds treatment effects. The American Economic Review, 80:39-333, 1989 URL
https://app wwwanticscholar..oooo wwtp://hhhoo.....oooooooo.. us AsID:153656329
OpenAL, Akkaya, I., Andrychowicz, M., Chociej, M.. Litwin, M., McGrew, B., Petron, A., Paino, A., Plap- pert, M., Powell, G., Ribas, R., Schneider, J., Tezak, N., Tworek, J., Welinder, P., Weng, L., Yuan, Q., Zaremba, W., and Zhang, L. Solving rubik's 's cube with a robot hand. arxiv, 2019. URL http: arxiv. org/ abs 1910 00113
Mezghani, L., Sukhbaatar, S., Bojanowski, P., Lazaric, A., and Alahari, K. Learning goal-conditioned policies of- fline with self-supervised reward shaping. In Liu, K., Kulic, D., and Ichnowski, J. (eds.), Conference on Robot Learning, CoRL 2022, 14-18 December 2022, Auckland, New Zealand, volume 205 of Proceedings of Machine

---

Automatic Reward Shaping from Confounded Offline Data
O'Connor, S. M. and Kuo, A. D. Direction-dependent control of balance during walking and standing. Journal of neurophysiology, 102 3:1411-9, 2009. https //api. www.sttiincttntteeeeeeeee www.aatticccoooaa..oooooooaoooaa ID:17 336
Saksida, L. M., Raymond, S. M., and Touretzky, D. S. Shap- ing robot behavior using principles from instrumental conditioning. Robotics Auton. Syst. 22(3-4):231-249 1997. doi: 0010016/00221-88909900000004 https://don http://..........0/./. 3 100041-2
URL -890
Pan, A., Bhatia, K., and Steinhardt, J. The effects of reward misspecification: Mapping and mitigating mis- aligned models. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April 25-29, 2022. OpenReview.net, 2022. URLthttss 7/openrevie net wtwe:/oormmmm/ id= JYtwGW 1IG.ewLLyeee L7ye
Shi, C., Uchara, M., Huang, J., and Jiang, N. A minimax learning approach to off off-policy evaluation in confounded partially observable markov decision processes. In Chaud- huri, K., Jegelka, S., Song, L.,, Szepesvári, C.,, Niu, G., and Sabato, S. (eds.), International Conference on Ma- chine Learning, ICML, 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research, pp. 20057-20094 PMLR, 2022. URI. attps://proeeed.ngs m hi22f.html
Pathak, D., Agrawal, P., Efros, A. A., and Darrell, T. Curiosity-driven exploration by self-supervised predic- tion. In Precup, D. and Teh, Y. W. (eds.), Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, NSW, Australia, 6-11 August 2017, volume 70 of Proceedings of Machine Learning Research, pp. 2778 2787. PMLR, 2017. URL http: /ttp://proceeee dings.m www.s.....rsss......mmm v wttp0//pppaaaaaaa. .t..mmm...lmmmmmmmm.mmmmm
Simchowitz, M. and Jamieson, K. G. Non-asymptotic gap-dependent regret bounds for tabular mdps. In Wal- lach, H. M., Larochelle, H., Beygelzimer, A., d' Alchh Buc, F., Fox, E. B., and Garnett, R. (eds.), Advances Neural Information Processing Systems 32: Annual Conference on Neural Information Processing Systems 2019, NeurIPS 2019, December 8-14, 2019, Vancou- ver, BC, Canada, pp. 1151-1160, 2019. URL https: / p/prceedingg wttp::/rrrrr..ccaoocea/e/e/ace/a hash e e-Abstract.htm.
Pearl, J. Causality: Models, Reasoning, and Inference.
Cambridge University Press, 2 edition, 2009. doi: 10.101 7/CB097805 1803161.
1899988811100111..
Precup, D., Sutton, R. S., and Singh, S. P. Eligibility traces for off-policy policy evaluation. In Proceedings of the Seventeenth International Conference on Machine Learn- ing, pp. 759 1599-666222 2000.
Singh, S. P. and Yee, R. C. An upper bound on the loss from approximate oatimal-value functions. Mach. Learn., 16 (3):227-233, 1994. doi: 10. 10.10077/F00099933888 URL https://doi.org/ 1007 BF0933300
Puterman, M. L. Markov Decision Processes: Discrete
Stochastic Dynamic Programming. Wiley Series in Prob- ability and Statistics. Wiley, edition, 1994, ISBN 978-0-
471-61977-2 978-0-4700-31688-7 doi: 10.1002/978047 0316887. URL http:attt///onnneeeeiooooeee wile wile c.com/ doi wttam///oo/oooooooooo wttp:///00..00000700770770000
Song, Y., Zhou, Y., Sekhari, A., Bagnell, D., Krishnamurthy, A., and Sun, W. Hybrid RL: using both offline and online data can make RL efficient. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL /tttps::/oppe::t www.:ewww..ete...... net. for d= yyBis801Uuu
Raileanu, R. and Rocktäschel. T. RIDE: rewarding impact- driven exploration for pnocedurally--enerrtee environ- ments. In 8th International Conference on Learning Rep- resentations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenReview.net, 2020. URL https; //openreview.oo net. for worummmmmiooooooo. wttp://oooomimieea-ra-ee
Strehl, A. L., Li, L., Wiewiora, E., Langford, J., and Littman, M. L. PAC model-free reinforcement learning. In Co- hen, W. W. and Moore, A. W. (eds.), Machine Learning, Proceedings of the Twenty-Third International Confer- ence (ICML 2006), Pittsburgh, Pennsylvania, USA, June 25-29, 2006, volume 148 of ACM International Con-
Randløv, J. and Alstrom, P. Learning to drive a bicycle using reinforcement learning and shaping. In Shavlik, J. W. (ed.), Proceedings of the Fifteenth International Conference Machine Learning (ICML 1998), Madison, Wisconsin, USA, July 24-27, 1998, pp. 463-471. Morgan Kaufmann, 1998.
ference Proceeding Series, pp. 881-888. ACM, 2006. doi: 10.1145/1143444114433 //doi (rcol..org//0.1115111444444
URL https
Ruan, K., Zhang, J., Di, X., and Bareinboim, E. Causal imitation for markov decision processes: A partial identi- fication approach. Advances in neural information pro- cessing systems, 2024.
Sutton, R. S. Reinforcement learning: An introduction. A Bradford Book, 2018
12

---

Automatic Reward Shaping from Confounded Offiine Data
Sutton, R. S. and Barto, A. G. Reinforcement Learning: An Introduction. A Bradford Book, second edition, 2018. ISBN 0262039249.
Yang, K., Yang, L. F., and Du, S. S. Q-learning with loga- rithmic regret. In Banerjee, A. and Fukumizu, K. (eds.), The 24th International Conference on Artificial Intelli- gence and Statisties, AISTATS 2021, April 13-15, 2021, Virtual Event, volume 130 of Proceedings of Machine Learning Research, pp. 1576-15844 PMLR, 2021. URL http://proceediinn g2lb hhtml
Swaminathan, A. and Joachims, T. Counterfactual risk minimization: Learning from logged bandit feedback. In International Conference on Machine Learning, pp. 814 823, 2015.
ml r, wwwps/wws./.oooope.p.
Tennenholtz, G., Shalit, U., and Mannor, S. Off-policy eval- uation in partially observable environments. In Proceed- ings of the AAAI Conference on Artificial Intelligence, volume 34, pp. 10276-10283, 2020.
Yuan, M., Li, B., Jin, X., and Zeng, W. Automatic intrin- sic reward shaping for exploration in deep reinforcement learning. In Krause, A., Brunskill, E., Cho, K., Engel- hardt, B., Sabato, S., and Scarlett, J. (eds.), International Conference Machine Learning, ICML 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceed- ings of Machine Learning Research, pp. 40531-40554, mlr
Wang, Y. and Srinivasan, M. Stepping in the direction of the fall: the next foot placement can be predicted from current upper body state in steady-state walking. Biology Letters, 10, 2014. BtRLhtts::///
PMLR, 2023. URL press/ /2055/2202// www2222/yuan// yut.2nc..nnnnll
semantic
scholar. cttp://oorrcoor010::::32000
Zhang. J. and Bareinboim, E. Near-optimal reinforcement
Wang, Y., Dong, K., Chen, X., and Wang, L. Q-learning with UCB exploration is sample efficient for infinite- horizon MDP. In 8th International Conference on Learn- ing Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenRevi,w.net, 2020. httpst Seopenreview.net/EEee (ttp//orrmmmiiiiai1111111
learning in dynamic treatment regimes. In Advances in Neural Information Processing Systems, pp. 13401- 13411. 2019.
Zhang. J. and Bareinboim, E. Can humans be out of the loop? In Schölkopf, B., Uhler, C., and Zhang, K. (eds.), 1st Conference on Causal Learning and Reason- ing, CLeaR 2022, Sequoia Conference Center, Eureka, CA. USA. 11-13 April, 2022, volume 177 of Proceedings of Machine Learning Research, pp. 1010-1025. PMLR, 2022. URL http:ss:/proocceinggggg s s/v177 (117772hhng22a.ktt. html
Watkins, C. C. H. Learning from delayed rewards. PhD thesis, University of Cambridge England, 1989.
Watkins, C. C. H. and Dayan, P. Technical note q-learning. Mach. Learn., 8:279-292, 1992. doi: 10. F007//9999999
pres
98. URL
2698
Zhang, J. and Bareinboim, E. Eligibility traces for confound- ing robust off-policy evaluation. Technical Report R- 105, Causal Artificial Intelligence Lab, Columbia University, May 2024.
Wiewiora, E. Potential- shaping and q-value ini- tialization are equivalent. J. Artif. Intell. Res., 19:205- 208, 2003, doi: 10.1613/JAIR. 1190. URL https: 0/doi.
1190.
Zhang. J., Kumor, D., and Barcinboim, E. Causal imita- tion learning with unobserved confounders. Advances in neural information processing systems, 33: 33:12263-12274 2020.
Wu, L., Zhang, Z., Haesaert, S., Ma, Z., and Sun, Z. Risk- aware reward shaping of reinforcement learning agents for autonomous driving. In 49th Annual Conference of the IEEE Industrial Electronies Society, IECON 2023, Singapore, October 16-19, 2023, pp. 1-6. IEEF, 2023.
Zhang, Y., Qiu, R., Liu, J., and Wang, S. Roler: Effective re- ward shaping in offline reinforcement learning for recom- mender systems. In Serra, E. and Spezzano. F. (eds.), Pro- ceedings of the 33rd ACM International Conference on Information and Knowledge Management, CIKM 2024, Boise, ID, USA October 21-25, 2024, pp. 3269-3278. ACM, 2024. doi: 000114457662767336776633 URL ht tps://6ol..or//D.. http:///1.11111333721373777
doi: 10. 10.1109/ECOOS 270.NN11117...0223332230000 103 URL ht http://.....//110.11111//1101.1 10312422
Xu, H., Ma. T., and Du, S. S. Fine-grained gap-dependent bounds for tabular mdps via adaptive multi-step boot- strap. In Belkin, M. and Kpotufe, S. (eds.), Conference on Learning Theory, COLT 2021, 15-19 August 2021, Boulder, Colorado, USA, volume 134 of Proceedings of Machine Learning Research, pp. 4438 4472. PMLR, 2021. URL v1 34 / xu2 1 a. html
Zhu, Y., Wang, Z., Merel, J., Rusu, A. A., Erez, T., Cabi, S., Tunyasuvunakool. S., Kramár, J., Hadsell, R., de Fre- itas, N., and Heess, N. Reinforcement and imitation learning for diverse visuomotor skills. In Cress-Gazit, H., Srinivasa, S., Howard, T., and Atanasov, N. (eds.).
mlr. www.s/essm./pps.s///me
13

---

Automatic Reward Shaping from Confounded Offine Data
Robotics: Science and Systems XIV, Carnegie Mellon University, Pittsurrh, Pennsylvania, USA, June 26-30, 2018, 2018. doi: 10.15607/RSS.2008XXX.0000. URL
http:/ / www. www.ttoossooceeeeicc..ooo./o.oo.
8 s14/ s14/p09. htmml
Zou, H., Ren, T., Yan, D., Su, H., and Zhu, J. Reward shaping via meta-learning. CoRR, abs/1901.09330, 2019.
14

---

Automatic Reward Shaping from Confounded Offiiee Data
A. Related Work
Reward Shaping. Before Ng et al. (1999) proposed the Potential-Based Reward Shaping (PBRS), the idea of transforming and modifying rewards to better facilitates learning has been studied in various problem settings (Saksida et al.) [997] Randlov & Alström 1998). Ng et al. (1999) first formalized shaping framework that guarantees the policy invariance under reward transformation. Though this policy invariance comes at price that shaping functions are limited to certain forms of state potential functions. There are numerous successful applications of PBRS (Brys et al. 2015 Harutyunyan et al., 2013) but there are also a growing numbers of papers that focus on using carefully designed biased shaping functions (not following the PBRS framework) (lbrahim et al., (024). Such shaping functions have shown effectiveness in robots playing rubic cubes OOpenAl et al., 2019). in autonomous driving (Wu et al. 2023) and more. People are also not satisfied with designing shaping functions manually and tries to learn shaping functions automatically, either serving as an exploration
bonus or a supplement to the task rewards (Zou et al. 2019 Ma et al. 2024 Pathak al. 2017 Yuan al. 2023 Raileanu
& Rocktäschel 2020 Devidze et al. 2022).
Off-Policy Evaluation and Learning. Off- learning has a long history in RI. dating back to the classic algorithms of importance sampling (Swaminathan & Joachims] 2015) Jiang & Li
Q-learning (Watkins 1989 Watkins & Dayan 1992).
2016), and temporal difference (Precup et al.
2000 Munos et al. 2016). Recently, people also propose to utilize offline
datasets to warm start the training (Nakamoto et al.
2023 Bhargava et al., 2023 Kumar et al., 2020), augmenting online 2023) or incorporating imitation loss with offline data (Kang et al.,
training replay buffer (Song al., 2023] Ball et al.
2018 Zhu et al., 2018). However, these work rely on critical assumption that there is no unobserved confounders in the environment. While this assumption is generally true when the off- data is collected by an interventional agent, offline datasets generated by potentially unknown sources can easily break this assumption (Levine et al. (2020). In recent years, there is also a growing interest in identifying policy values from confounded offline data (Shi et al., 2022 Miao et al. 2022
Guo et al. 2022. [ennett & Kallus 2024) or partially identifying the policy values via bounding (Zhang & Bareinboim 2024 2019).
Regret Analysis of Finite Horizon Episodic Tabular MDPs. Many of the prior work on regret analysis focus on the model-based setting where the transitions and reward distributions estimated from collected data and planning is then executed in the learned model to extract the optimal policy (Singh & Yee 1994 Kearns & Singh 1998 Kakade 2003 Dann
& Brunskilll, 2015) Dann et al.] 2017: Simchowitz & Jamieson] 2019). In this work, we mainly focus on the regret analysis for model-free learners (Strehl et al. 2006; Jin et al. 2018:; Wang et al. 2020: Xu et al. 2021 Chen et al., 2024). More specifically, our analysis focuses on a Q-learning variant, Q-UCB (Jin et al. 2018) that incorporates the UCB bonus into Q-learning showing model-free learners can also enjoy VT regret as the model-based learners do. Later, Yang et al. (2021) provides a more fine-grained gap-dependent regret analysis on Q-UCB showing that also enjoys a logarithmic dependency on total training steps T.
B. Walking Robot Example Details
From the environment set up, there are two ways of walking optimally.
If the agent can observe the step size required to stabilize itself (U,), it should always act as X2, = Un when F7, = 0. Under this perfect behavioral policy, walking process should be: (1) When the robot stable, F2 1, it takes a big step X,. = 1 and transit into an unstable status, F = 0. At this stage, the agent's location does not change, Lb+1 La; then (2) the agent takes an appropriate size step, X₁, Un, transits back to stable status F1+2 = 1 and move forward by one step, Ln+2 = Lh+1 + 1. The whole process resembles human walking behavioral policy. Formally, this is defined as ((.)) Xx + Un if Fb. = 0 else X, < 1. (In Example 2 the incompetent behavioral policy is defined as ((²2) Xx, + -U,.)
"controlled falling" process. This is the optimal
However, there is an alternative approach to walking steadily when the robot cannot determine the required step size U, to stabilize itself. By taking small step size every time, X, = O, the agent always stays in stable status F; = 1 and moves forward steadily in each time step. This is the optimal interventional policy. Formally, this is written as . L,, Fi) = 0.
To see the quantitative difference between the optimal behavioral policy and optimal interventional policy, we calculated the optimal state values as shown in the below chart. Note that for each state with given L,, Ft, the optimal behavioral state values are the same for all Ug. We can see from the table that while the optimal behavioral policy can achieve optimal rewards from any stability status, an interventional agent should only stay in the stable status due to observational mismatch.
15

---

Automatic Reward Shaping from Confounded Offine Data
Table 1. Optimal behavioral and interventional policy values.
Behavioral
Interventional
F2
0
F.
F-=0
0
F.
10.
10.
5.0
5.5
9.
9.
4.5
5.
2
8.
8.
4.
4.5
3
7.
7.
3.5
4.
6.
6.
3.
3.5
5
5.
5.
2.5
3.
6
4.
4.
2.
2.5
7
3.
3.
1.5
2.
8
2.
2.
1.
1.5
9
1.
1.
0.
1.
10
0.
0.
0.
0.
In the meantime, state values of the behavioral policies estimated via Monte-Carlo simulation during the offline dataset collection are shown in Table 2 We see clear trend that for the good behavioral policy Tı, it does not show any preference
Table 2. Confounded values of behavioral policics.
Beh. Policy πi
Beh. Policy m2
L,
Fj
= 0
Fr =
Fi =
Fi
10.
10.
-22.5
-41.7
9.
-21.8
-40.1
-2.0
-38.4
3
7.
-00.25
-36.9
19.5
-34.5
-1.75
-33.6
-8.0
-32.5
3.
-17.3
132.1
-16.5
-31.5
0.
0.
over the stability status while for bad behavioral policy TT, it even penalizes being stable. Thus, both confounded values are not good approximation for our optimal interventional state value. The final state potential learned by our method, on We see clearly that our proposed algorithm successfully learns an upper bound to the
the other hand, is shown in Table 3 optimal interventional state values and also showing a clear tendency towards the stable status (F, = 1), the same as the optimal interventional values do.
C. Causal Upper Bound Algorithm
We present the full pseudo-code for calculating causal upper bounds on optimal state values from multiple offline datasets in Algo. 2
D. Detailed Experiment Design and More Results
In this section, we provide a detailed description of experiment setups and additional experiment results.
16

---

Automatic Reward Shaping from Confounded Offine Data
Table 3. Causal state value upper bound.
L
Fj
0
Fi
0
7.6
9.3
7.5
9.3
2
7.5
9.3
3
7.6
9.3
7.6
9.3
7.9
9.1
8.0
8.9
7
7.9
8.6
8
7.6
7.6
5.3
5.3
10
0.
0.
Algorithm 2 Causal Upper Bound Potential
1: Input: Offline datasets, D(0) i 1,.., N and reward upper bound,
2: for = 1 to do
3: while Not Converged do
4: for h Hl to do
5:
for state S do
6:
for action x E X do if 8, not visited in // then
7:
8:
Continue
9:
end if Calculate Q (8, x)) by Eq. 8
end for
Update (s) max
(s)
RED Qn (r|s)
13:
end for
14: end for
15: end while
end for
v (s)
return (s) min min.enp EEDf
D.1. Experiment Setups
All of our experiment results are obtained from 2021 MacBook Pro with MI chip and 32GB memory. The cumulative regret results averaged over three random seeds. We implement the Q-UCB in homogeneous way that there is no step indices for state spaces.
Regarding the environment parameters, for Windy Empty World, the episode length is set to 15 while the LavaCross series has a horizon 20. To compensate for the hard exploration situation, we allow random initial starting states over the whole map walkable area. For training steps, we set total of 100K environment steps for Windy Empty World and 20K for the LavaCross series. We represent the wind distribution in those windy Grid World as five-tuple meaning the probability mass for (WEST WIND, NORTH WIND, EAST WIND, SOUTH WIND, NO WIND). We list them as follows,
Windy Empty World: (.1, 1,1,
Windy LavaCross (easy): (0, 8, 0, 02
Windy Lava Cross (hard): (0, 0..
(0., 5, 0., 0., if if
Windy Lava Cross (maze):
(.5 0., 0., 5) sf] 7
15, 15, otherwise
17

---

Automatic Reward Shaping from Confounded Offine Data
And for each environment, have three different behavioral policies for collecting offline datasets. Here list their brief descriptions below,
Windy Empty World: The first one is good behavioral policy that stands still when the wind is blowing the agent away from the goal and go towards the goal when the wind direction is in its favor. The second one is bad behavioral policy that follows the good policy half of the time while being fully random the other half. And the last one a fully random policy.
Windy LavaCross (easy): The first one is good behavioral policy that takes the L-shaped safe route staying tight the lower and left side walls. The second one is bad behavioral policy that tries cross the upper side gateway when there is no wind. And the last one is again fully random policy.
Windy Lava Cross (hard): The first one is good behavioral policy that takes the same safe route in the lower left side. The second one is bad behavioral policy that collects those coins on the northern bank the lava lake when there no wind then reach the goal. And the last one also a fully random policy.
Windy Lava Cross (maze): The first one is good behavioral policy that goes directly to the goal location. The second one is less preferred that it takes bit detour to get the extra coin near the goal. And the last behavioral policy goes directly to the coin upper right corner without reaching the goal at all.
D.2. Extra Experiment Results
Additionally, have another LavaCross maze with fewer coins. The safe route is still the lower left L-shaped route. The behavioral agents generating offline datasets in this environment include a conservative one taking the safe route, an adventurous one taking the detour to get an extra coin before reaching the goal, and a radical one only looking for the top right comner coin without even reaching the goal. As shown Fig. 6a only shaping with our proposed causal upper bound helps the online interventional agent converge efficiently to the right policy (Fig. [ig (bb). We further provide the ratio of states where the learned policy is optimal in App. D.2 Note that the table we included one more baseline which a deep neural network based learner, BCQ (Fujimoto al. 2019).
Table Optimal ratio across different environments, Higher better.
Algo./Env.
Windy Empty World LavaCross(easy)
LavaCross(hard)
LavaCross(maze)
No Shaping Q-UCB
0.00
0.00
0.00
0.03
Shaping + Causal (Ours)Ours)
0.76
0.70
0.81
0.90
Shaping Min. Val.
0.72
0.49
0.30
0.24
Shaping Max. Val.
0.73
0.52
0.59
0.33
Shaping Avg. Val.
0.74
0.50
0.49
0.24
BCQ
0.79
0,50
0.67
0.50
Shaping BCQ
0.88
0.31
0.22
0.03
Shaping Min Ban Velue
Beeeen Connal Plano
0.0
02
1.2 1.5
20
Bnveeeaar Stpa.
(a) Map
(b) Regret
(c) Learned Policy
Figure LavaCross maze with fewer coins.
18

---

Automatic Reward Shaping from Confounded Offine Data
40
40
+0
33
33
1
+0
14
40
40
+0
+0
+0
12
O
+0
+0
Figure 7. Wind distribution in the LavaCross maze with fewer coins.
E. Shaping and Initialization
have the optimal state value, warm-starting the online learning by initializing state values with such optimal ones seems more straightforward than shaping. But their effects learning only the same under unrealistically strict conditions (Wiewiora, 2003). That is, given the same sequence of samples, the learned Q-values (Watkins & Dayan [1922 after shaping is always less than the one learned without shaping by the amount of the potential functions. A direct implication of this result is that the policy learned under shaping at each time step is indifferent from the one learned without shaping, thus, learning efficiency is unchanged.
Proposition E.1. Given a fixed sequence of samples, the policy distribution learned under shaping is equivalent to that learned without shaping but initialized with ((.).
There is also prior work showing that for the -psildnngreedy exploration strategy, votential-based reward shaping does not directly affect learning efficiency. Instead, how optimistic the initialization is compared with the potential functions affects the learning efficiency (Dann al. 2022). While people also find that for model-based learners, certain forms of reward shaping boost learning efficiency provably (Gupta et al. 2022
F. Original Q-UCB Algorithm
We restate the pseudo-code for origianl Q-UCB in Algo.
For more details please see Jin et al. (2018).
Algorithm Q-UCB
1: Initialize (s,
(s, x) + H, (x) = 0, for all (8, h) E x X' x [A].
2: for & == 1 K do
3: Observe initial state 81-
4: for h to do
5: Take action Fa arg max, Q (sh, 2)) and observe 1 Vh-
6: Update visitation counter and calculate UCB bonus, N₂ (sh, In) t- Nu(sn, 24.) +1 cv HH//tt
7: Update Q-value, Q (sh, 24) = (1 oz) az) (sh, xn) + az (yh + Vitt (Sh41) + b.).
8: Update value function, v min max Q [s),
9: end for
10: end for
G. Useful Results for Proofs
We will first restate some useful claims in the literature to be used later in our proofs for completeness.
Lemma G.1 (Properties of Cumulative Learning Rates). Let ar
H+1
We define af 11/-1 (1 a;) and ot
I (1 az). The following properties hold for oi;
19

---

Automatic Reward Shaping from Confounded Offine Data
(a) J. x 5 i= vi
every 1 1. ái S 2. Joreery
(b) max of S T
2H and (at)² - 2H for every t 2 1.
(c) of of ++ for every! >
In addition, we have (1) 1i 0f = and o = 0 1 12 of = 0 and a, = 1ort = O.
Proof. See Jin et al. 2018 App. B for details.
Lemma G.2 (Property of the Clip Function). Let clip [z=]]] = 1[x 8) (Simchowitz & Jamieson, 2019 For any three positive numbers b, c satisfying + b 2 and for any E (0, 1), the following holds,
+ bs clip
+ (1 +0++x)b
(11)
2
Proof. See Claim A.8 in App. from Xu al. 1022 for details.
Lemma G.3 (Bounded Summation for Clipped Function). The summation of a functiio which scales proportionally the inverse of the square root of the variable has the following bound:
4c²
clip
(12)
1=
Proof. See Claim A.13 in App. A from Xu et al.
2021 for details.
H. Proof Details
H.1. Potential-Based Reward Shaping in CMDP Proof
This is for Prop. 2.2
Proof. Because CMDP also enjoys the Markov property, the overall proof procedure highly resembles the original one in Ng et al. (1999). Only to note that the optimal policy invariance is proved in the online learning sense, which is between M and M,.
H.2. Causal Bellman Optimal Equation Proof
In this section, we derive the Causal Bellman Optimal Equation from the original Bellman Optimal Equation of MDPs. For stationary CMDPs, we also prove that our Causal Bellman Optimal Equation has unique fixed point and the optimality of this unique fixed point.
Theorem H.1 (Causal Bellman Optimal Equation (Thm. 3.1.). For CMDP environment M with reward Y, S E R. the optimal value of interventional policies, Vi)(s, (s), Vs, upper bounded by V*(s) S (s)s) satisfying the Causal Bellman Optimality Equation,
(s(s) = max (x(ss) (s, E7, V (++1 Pa(-ols) (D
max V VN+z(('))
(13)
Proof. Starting from the Bellman Optimal Equation, the optimal state value function given by,
V (s) max 2)) + [T(
(14)
Note that the actions here are done by interventional agent, which is actually do(x) in the context of a CMDP. We swap in the causal bounds for interventional reward and transition distribution,
V (s) max (zll)) bP%(-vrls)
Σ
Pa(--rs)) max V Vi++(
(15)
20

---

Automatic Reward Shaping from Confounded Offiiee Data
where R,(8, x)) |S, s, X, z/. Tn is shorthand for (8, xr P(SN+1 S'S 8, Xn x) and P(z]s) (X, 2/ Sr are estimated from the offline dataset. And b is known upper bound the reward signal, YA S b. In this step, upper bound the next state transition by assuming the best case that for the action not taken with probability Px(-x the agent transits with probability the best possible next state, max," "i+1(s")
Then after rearranging terms, we have,
(s) S max (a(())) (Ra(9,z) + Σ 1 + Pr(-<rss) (b+ max Vitz(6"))
(16)
And optimizing the value function w.r.t this inequality gives us upper bound on the optimal state value,
(A(5) S max Ph(alss) (Ra(o,0)+ + +TTass.. Ph(-xels (b max V va=1(("))
(17)
More interestingly, we will show in Prop. H.2 that this will also converge to unique fixed point in stationary CMDPs. Proposition H.2 (Convergence of Causal Bellman Optimal Equation in Stationary CMDPs). The Causal Bellman Optimality Equation converges to unique fixed point which is also upper bound on the optimal interventional state values under the assumption that P(s,r) O, Vs, x in stationary CMDPs.
Proof. We will first show that the following Causal Bellman Optimal operator a contraction mapping with respect to a weighted max norm. The major proof technique is from Bertsekas Tsitsiklis (1989) (Sec 4.3.2). Then by Banach's fixed-point theorem (Banach) 1922). this Causal Bellman Optimal operator has a unique fixed point and updating any initial point iteratively will converge it. Then will show that this unique fixed point is indeed an upper bound the optimal interventional state value.
Let the operator T be,
(s) max P(rls) R(s,,)) + -I(o,, P(-xo(s) max maxx((""))
(18)
For arbitrary value bound, V1, V,, we can bound their difference under one step update by,
(8) - (V, < max P(xls) (1 - P(-x)()) max Vi(*") - VV((")) (19)
Note that combine the terms together and extract operator out because of its non-expansive property. Then partition the state space as follows. Let S {Sp} be the set of sink state (in episodic CMDP, we always transit into the sink state after we reach the horizon limit). For A: = 2,3, 3.... we define,
S = {ilé &
U ME[LA-1]
Sy A min
max
T(i,x,j) > 0}.
(20)
jeU 1 Spr
The set S₁ intuitively represents the set states that can transit to states closer to the sink state even with adversarial action picks. Let Sm be the last of these sets that is nonempty. We will show that all those nonempty sets cover the whole state space. Suppose the set Sxx {ili Um Sk} is nonempty. Then by definition, for any state i Soc. there exists action Sz. This means that state cannot transit into the sink state with certain actions,
- such that T)) = 0, Vj E - which contradicts with our episodic setting that starting from any state-action pair, the episode will end at the horizon limit.
Then we define the max norm with respect to which we will later show that the difference between value update is a contraction mapping. We set the weight vector w in a way that each of the entry wa, i corresponds to a set Sy and all states inside the same set shares the same weight, that is, w/ = yk if E Sk.
21

---

Automatic Reward Shaping from Confounded Offiie Data
We will for assume the following properties of sequence {y+) hold, prove T is a contraction mapping, and then come back show find such sequences.
y1 < 1/2
ym
(21)
ym
cd) + Wk-1 c S 7 < 1, m
(22)
yk
yk
where = mi2 ming minjes, ΣjeUven Sv T(i, x) is the minimal one-step transition probability that state from later set Sş transfer to state that is closer to the sink state and ô = ming, P(s, x) > 0 from the behavioral dataset.. From previous discussion and probability distribution validity property, we have e E (0, 1].
Let the initial difference between the value vectors ||V - Valls s e where e > a constant. Then we have, for any state s Sk(s) where k(s) means the index of the state set that s belongs to.
Vi(s) - V2(s) & cyk(s))
(23)
Now we can continue to write the value update difference as,
TV (+) - TV2())
< max P(x|s) Σ 2, + P(-x(s) max Yk(s")
(24)
cyk(s)
yk(s)
x
max P(x]s) Σ T(,, + P(-zt(s) max yh(s"))
(25)
yk(s)
Given the fact that S ym, Ak m].
(V
max
P(æ|s) T(s, x, 8 Muse - P(-xxss)m
(26)
Cyk(s)
Uk(s)
We can split the sum over next state s' by differentiating whether it belongs to the sets closer to sink state than s or the sets further away from the sink state than 8,w2
TV (s) (s)(
max P(x(s)
Σ
T(, x. (k(())))))
Cyb(s)
Vk(()
+ P(x
Σ
T( x, 5'),))))) + P(-x|s))m
(27)
Spr
And by the property of (yn 1m 1= = 21
< 422 < ... < ym and the fact that E. T() = 1, we have,
(V2((s)
1 max
(JLco)-1- 3m P(rls)
Σ
T(s,2, + Um 2m P(x|s) + P(-x((s)
(yk(#)
Vl(())
(28)
max Vk((s)
1
(Vic))) P(rls S) Str
Σ
T(s,2,s))
+ Um
(29)
yk(s)
By definition, e lower bounds the transition probability of Σ. Leeeennn Sy T(s x, 8¹), we have,
TV (s) - TVv(s)
1
max P(xls) ((xls)( vm )e + 3m
(30)
Cyk(()
1k((e
yk(s)
Vm
(1 c8) + yk-1 c8
$ V/k
(31)
8k
<
(32)
22

---

Automatic Reward Shaping from Confounded Offine Data
Thus, for the state value bound vectors, have,
ITV TV & qc
(33)
for all 11, 22 satisfying I V2ll S c. Thus, T' is contraction mapping with respect to a weighted max norm.
Lastly, we will show that sequence {ykk mm satisfying Eq. 21 and Eq. (22) realizable. Let yo 0, y1 1. and suppose that y1, 12, - Uk have been chosen. If cδ 1, set t Uk 1. If < 1, we set
uk+1 1/2(1= + 2k)
(34)
where
cd
2 min
1/1 +
(y/ 31-1)
(35)
kE]1,k]
ed
And we can write recursively as,
ed
2/ f
1,
1 1- cō
(Uk
yk 11)-
(36)
We will first show by induction that this sequence satisfies Eq. (1
(1) Base Case: By definition, yo < yı,
(2) Induction Hypothesis: Assume yk-1 < yk holds.
(3) Inductive Step: Our goal is to show that yk < Vk+1- By definition, yk+1 = 2 + 2x), the problem reduced to
whether 1 yk 2ạ yk O. Since yk (y6-1 + zk-1) and we have y/-1 < ykk Thus, we have 2k-1 > yk- And
clearly we have yiu T (y/k yk-1) yk- By the recursive update rule, have,
2 =
min 1k Ul + 1 (yi yk yk-1)}
(37)
As we have shown that both term are bigger than yk. we have yk- Thus, the sequence {ue M satisfies Eq.
21
For Eq.
we first notice that since 2m-1 Um = Um Um-1 > 0, we have,
2m min fmm (2m-1 Vmn +
(ym Vm 1)} > Vnn
(38)
By definition, 2m is also calculated as,
Y/ + 6d
2m min #E[1.m]
(y:s y 8/-
(39)
ed
Swapping this definition into Eq.
38 we have,
ed
(ykk
2k 1) > 3m
(40)
V/n
60
yk 9k-1) yk
1
+ 1 c6
(1
(41)
yk
(1 - c8) Vm
Vk-1
+
ed
<1. 1.
(42)
yk
yk
Thus, we have shown that a weight sequence (yx hm satisfying Eq. 21 and Eq. (22 indeed realizable.
Thus, T is contraction mapping with respect to realizable max norm. There exists unique fixed point V when we optimize V with 7 iteratively till convergence. For the optimal state value vector V*, we can also apply T iteratively until it converges to the fixed point V". By the update rule of (Eq. (17)). VV.V TV. Thus, we have V* < limg-roo TKV" V" where & denotes applying T iteratively for & times. The fixed point of the Causal Bellman Optimal Equation is indeed an upper bound of the optimal state value vector.
23

---

Automatic Reward Shaping from Confounded Offine Data
H.3. Q-UCB with Shaping Regret Analysis Details
We define the adaptive learning rate as Or H+1 and shorthand notion log (IS)) where T K H. We also
7++
have c( ) = 0 according to Prop. 2.2 and assume deterministic reward functions. Throughout the proof, we also assume conservative optimism condition is satisfied (Def.
We first present lemmas used in proving the regret bound of Algo.
Lemma H.3 (Concentration of Transition Weighted Bounded Functions). Let f be a function mapping from state space to a convex set of real values, S + [0, dml, 6m E R. With high probability, the following sum is bounded for all (s, 2, k) E S x X [H] [
bt 2
Vt E [K], Σ a. 1|, < K] ( Pnf)(s,x)
(43)
where t == (s) is the visitation count at the beginning of k-thh episode and we define the index of the episode when state-action pair (s,x) x) is visited for the i-th time be,
k; = min (1k E [K]] > K A (0h, a = (()x)))((+)))
(44)
Proof. Note that K; K +1 1 if (8, is not visited for the i-th time. The sequence {at- 1 1kk < K] (PP -- (s,
a martingale difference sequence w.r.t filtration Fi20 and we have |a 1[k; < K] (f f Pnf) x)1 - af om and
of 1 [Kk k] (f f as) = 0 since no visitation occurs at all when i = O. By Azuma-Hoeffding inequality, we have that Vc > 0,
P(
Σ aj 1=0
1ike < K] (2%) f Pnf)(s 26) S 2exp
(45)
E (at) 22))²0?
Thus, with probability p' S SAT Ei af 1[k < Kj (P f (s,)(s, N V log (SAT/p)H/t= b where > O is constant. By union bound over all (s, h, k) E S x X x [H] [K]. we conclude the proof for the claim. O
2
Lemma H.4 (Bounded Differences Between 0% and Q7 (Lem. 4.2p). The difference between the learned Q-value at the beginning of episode k and step h and the optimal Q-value can be bounded with high probability as follows,
0 (f, S S
af(-Q)(s,
+ Σ at (i
vk: h+1
-10% 1i+ V(+1) + 3b,,
(46)
where Ph denotes the expected transition w.r.t the true confounded MDP and Tot, denotes the sample transition experienced by the agent at episode lo step h.
Proof. First, can rewrite the optimal Q-value as follows by the Bellman equation and Prop. 2.2
=f = Q. + Σ af(un(s (ss) + (PAV + (s.)).
(47)
The learned Q-value can be written as follows using the defined accumulative learning rates Lem. G.I
(x,x))= Σ of (un a(s) + (L0 vil - os, +b.).
(48)
Subtracting Eq.
(47) from Eq. 48 we have,
()(s,)--770 (x,
(49)
=ai(-Q (s, x)) +
a
16 v (Fh
K41
PAV + (Ph: Pno))s, -b:)
(50)
i=1
= =s((-Q x)) + Σ
(1
(
h+1 -P8:11+))0,xx1 + (( (s, +fp (s,)) + b,)
at
1=1
(51)
24

---

Automatic Reward Shaping from Confounded Offine Data
By Lem. H.3
we have that with probability least 1 2p for all k) X
[H] [K]
sa
+
(1 (1
h+1 ((5+) bi) b.
(52)
By Lem.
G.1
we have,
() - x) sa((-Q)(ss) +
Σ
ai (IPt v - (itt2) + ev H + bt
(53)
1=1
{a((-QN(sxx)) +
af (1 (+t)) + +b+..
(54)
This concludes the proof for the right hand side. Then will show that Q Qx(s,2)) 2 0 by induction the steps of the episode from H to 1. Without losing generality, we assume >> 0 since when = it's straightforward to show this holds.
(1) Base case: When h H and for all k, it's the last time step and all future state values are zero by definition. We have,
(s, (s, = Σ at (1P ()) bb).
(55)
By Lem. H.3 and together with the discussion above for the other side, we know (IP d (s,))(, 2 with high probability. While by Lem. G.1 Σt= ob,; 2 by, thus, we have,
(h(,, - x) 2 b + (- 01 2 0.
(56)
The base case holds.
(2) Induction hypothesis: for h = 1/' and for all k. 1% x)) (s, 2 0.
(3) Induction step: Now show that for h' 1. the claim still holds. Recall that we can write the Q-value differences follows when Ê > O,
(57)
Σ ag (1 h+1 - - Vit11 + (1 Vitt1 (s, + (P (n +b))
(58)
1=1
And by Lem. G. and similar discussions as in the base case, we are left with terms,
(+(s,=)) - (5) 2 at Vin Ph (s,x))
(59)
By Algo. v (s*+1) min max, the potential function property (ø 2 V*) and the induction hypothesis, V (sn+1) 2 V (8h=1) holds.
x)}. Thus, matter which value v (sn+1) is getting, by
Thus, we have concluded the proof for the left hand side.
Definition H.5 (Psudo-Sune SuuudppSbtt State-Action Pairs (Def. 4.3 We define the set of pseudo-suboptimal state-acte action pairs to be the set that satisfies,
Suba ((x,x) E x [M], vn - (n(s) + ((P + (s, S (s)),
(60)
where A(8 = ming (s) min, ((,)))
25

---

Automatic Reward Shaping from Confounded Offine Data
Lemma H.6 (Bounded Number of Visits Suba (Lem. 4.4 bounded by,
The number of visits (8,2) E Suba, ( (8,
16c 11 o
1
(61)
A (8,
Proof. When & exceeds the bound,
16c 6
1
(62)
A (8,
by property in Lem. G.I we have,
2 S 2cv H H
2cv H
Vi < 2s)
(63)
This implies 2 E/= obb (s, And by Lem.
H.3 with high probability, we have,
at P.f + b 2
a
Pa
(64)
E=
where f is a bounded real value function f:S + [0. dm]. Apply this to the learned Q value 2% and by the conservative optimism condition (Def. 4.1 that
< Φ.
(s, Σ a 1/1 (s (P h + (s,, + bb:)
(65)
( (s) + 2( on 01 (1), + 26.)
(66)
(67)
Plug 2 E/ abb, < ()) into this,
() Σ afim - (s(ss + ((, ass
(68)
For (s,2) E Suba, by the definition of Suba and the optimistic property of the learned Q-value (Lem. H.4 we have,
(h(,, Σ oot (s)
(69)
(70)
S (
(71)
This indicates that when the number of visits to the state action pairs in Suba. t, exceeds the proposed bound, its learned Q value will be upper bounded by the learned Q value of the optimal actions, and by the greedy action selection rule in Algo. such actions will no longer be chosen going forward.
Lemma H.7 (Lower Bound on Sub-optimal Action's Q- V-luee Differences). For actions that suboptimal but being selected in the algorithm, x + x², with high probability, we have,
(h(,,))- - (7(, 2 Dn (8.
(72)
26

---

Automatic Reward Shaping from Confounded Offine Data
Proof. Because such actions are selected over the optimal, their learned Q-value must be larger. And by Lem. H.4
(+,,=))) (x(s)²") with high probability. Thus, we have,
Q (T 2 (*) - (s)
(73)
2 (h x²) - ())
(74)
(i) (%))
(75)
An(8,)).
(76)
Now we are ready to prove the main theorem.
Theorem H.8 (Regret Bound for Algo. 1 (Thm. 4.5
Given potential function o(.), with its maximum value defined as om after ranning algorithm Algo. for K episodes with H steps each, the expected regret is bounded by,
H m
Ö
Σ
Σ
(77)
(s,
(
B.xESuba
S,7
Suug
where Suba is the set of pseudo suboptimal state action pairs and (8) = min, An x), for all h E (H].
Proof. By the definition of expected regret over trajectories T, we can decompose it as follows,
E Regret []] E,
(i VT (st)
(78)
K
E
(1 ()()))=((())++++++ + - Vi (sft)
(79)
K
E,
A1 x1) + E., (V2 12"h ($2) Tik 2 st1
(80)
(81
K
E, ΣΣ
An xx) x
(82)
We can split trajectories by whether the high probability event in Lem. H.4 happens. When Lem. H.4 happens with at least
1 - 2p probability, Lem. H.7 1.7i: is also satisfied and we have,
E [Regret(KK))
E
a
m
(83)
H K
$ (1 2p)
Σ
(7h + 2pT
(84)
4=1k=1
We can set failure probability to be p = 27
1 and by L.H.S of the inequality in Lem. H.4
"1 K
E Regret (K) S
ΣV (Qh(s)
(sh =f1) H.
(85)
A=1A=1
Now, the regret bound boils down to the cumulative Q value differences. We revisit Lem. H.4 and expand the R.H.S with Bellman equations,
Ohisk, (,t, 5
a (P V
PA (8+1) 3b.
(86)
Σ a
- - Qo+z) +3b--
(87)
27

---

Automatic Reward Shaping from Confounded Offine Data
By Lem. G.2
Lem. H.7
and the fact that (8, ())
( Qh (5% s clip
3bt
A h =hh)
+(1 +
1 H
Σ a [
Qh-1)
(6
(88)
2H
Since QH Q 0. we can expand the above recursion and solve for value difference of all episodes at step Σ (hh, u/) - ( )² as follows,
(s ax%.)
0h . (h
E
(1+
j2(N (2(N'-)) 1)) clip
(89)
H
2H
A s ax(ii)
S e
clip
3byr
(90)
2H
k,
The term (1 + #) )² comes from both the coefficient (1 + H and the fact that Eis 03 S + H by Lem. G.1
Then we
plug this term back into our regret bound (Eq. (85)
( k)
E |Regret [K) S e² Σ
clip
36
+ HH.
(91)
2H
krh
We can rewrite the summations regarding the state action space and split the summation by whether (8, E Suba not,
A (
E Regret (K)) S H
Σ
clip
3b
+ H
(92)
2H
kch
H
NE (0,2)
A x)
= e²
Σ
Σ
clip
3b;
2H
k=1 (S,r)
H
NY
(a,a)
(ss, x))
+
Σ h=1 (s,x)
Σ
clip
3b;
+ H.
(93)
2H
Since from Lem. H.6 we know the total number of visits for each (s, Suba is bounded, we can apply this result on No 2s) for () Suba. And for xs & Suba, apply Lem. G.3 directly. Then the expected regret is bounded as follows,
N (s,20)
8H 9c
Ho
E [(egrett(K)) < 2²
Σ
b + H2
+ H
(94)
A(s,2)
(e.2)
(8,z)
N/ (s.w)
7202 02 11 +
3ce H² / H
(95)
Vi
A
(sar)
i=1
(sa))
16c Ho2 (8
72 02 H4r
3 H² / H
H
(96)
A A
(s.r)
(s,r) 72c2 02 H4,
12c2 H3, A(s,
+
(97)
A(s
(aba)
(s,0)
3 log (SAT)
& H1 log (SAT) A(8,1)
=0
(98)
A(s x))
(A.r)ESuba
(Nar)
28

---

Automatic Reward Shaping from Confounded Offine Data
We further simplify the regret bound by the fact that d(+) S H and arrive the final bound,
6 H log (SAT)
6 H log (SAT)
(99)
(8,
A (8,
(S,
(S,2)
H log (SAT)
H log (SAT)
=0
E
(100)
(1)
A (5,
B,zESuba
SargSuba
29


Reviews:
[{"review_id": "t4qWT36cay", "reviewer": "Reviewer_dtkk", "summary": "This paper focuses on the automated design of a reward shaping function from offline data, potentially contaminated by unobserved confounding bias. The authors propose leveraging causal state value upper bounds from offline datasets as a conservative, optimistic estimate of the optimal state value, which is then used as a state potential in Potential-Based Reward Shaping (PBRS) to achieve a more favorable gap-dependent regret bound. Experimental results demonstrate the effectiveness of the proposed approach.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your thoughtful feedback. We appreciate your acknowledgment of the significance of our work and have addressed your concerns in the sequel. \n> “The only one concern is how would the proposed method in more realistic environments, like MuJoCo?”\n\nIn this paper, we primarily focus on learning shaping functions from observational data and using the learned functions to accelerate online learning processes. Like many online RL algorithms, we use UCB as our basic learning method. The theoretical guarantees of UCB’s performance require the state-action space to be discrete, which may not directly apply to continuous environments like MuJoCo. However, this is a common challenge for most online RL algorithms. Extending these to continuous domains is an exciting challenge, and we appreciate the suggestion.\nThat said, we would like to briefly explain how our proposed method can be extended to high-dimensional and continuous state/action domains. For each component in our causal bound – i.e., policy distribution, reward, transitions, and values – we can train neural networks to learn these from offline data. The primary challenge is that the max operator of the bound in high-dimensional and continuous spaces cannot be computed exactly, necessitating approximation. Specifically, we can train a separate neural network to select the next possible best state based on observational data and then extract values from the learned value networks. This is a natural extension of our contributions; however, we were unable to provide more formal results at this point. Thus, we leave these out of the current manuscript. \n\n> “Could you provide more real-world examples or case studies to illustrate the broader applicability of your proposed method?”\n\nUnobserved confounders naturally arise when decision-makers consider factors that a passive observer cannot access. For instance, when training autonomous vehicles, data is often collected from engineering prototypes equipped with costly laser radars. However, to reduce production costs, we may wish to train less expensive vehicles equipped only with cameras using this data. Here, radar information becomes an unobserved confounder for the learner. Similarly, in robotics, numerous factors influence action outcomes without being monitored, contributing to what is known as the “sim-to-real gap”, caused by unobserved confounding. For example, friction and instability in demonstrators’ joints may be unmonitored, affecting their behaviors. The method proposed in this work can be used to design denser reward signals when training robots or autonomous vehicles, using confounded data as such.\n\n> “Furthermore, it would be beneficial if Figure 2 included the transition functions and a clearer demonstration of how the unobservable confounder operates, as this would enable a quicker and more thorough comprehension.”\n\nIn the robot walking example, the step size ($U_t$) required to stabilize its body (($F_t=0 \\rightarrow F_{t+1}=1}$)) is an unobserved confounder. We will update the manuscript to clarify this issue. Thank you for the suggestion.\n\n> “In which scenarios are confounders critical for policy learning, and in which cases might they be less relevant or unnecessary? How should one identify and account for such confounders in practice? Can I regard it as one kind of partial observation?”\n\nConfounders can be taken as partial observations, except that behavioral policies may access some of them. Consequently, the learned policy should account for these – though, as we will explain next, there are cases where this may not be necessary. However, the unobserved confounders are not directly accessible to the learned policy and require special treatment, which is the objective of the causal bounds proposed in this work.\nRegarding optimality, as demonstrated in our experiments, the learned policy proves to be a safer choice compared to one that aims to collect all coins and reach the goal location. This latter policy is the best possible outcome the agent could achieve without observing the wind. However, it is no longer optimal when compared to a behavioral agent with greater sensory capabilities. Generally, when unobserved confounders exist, it is understood in the literature (Pearl, 2009) that the optimal policy is under-determined by observational data (not identifiable) without additional experiments or assumptions.\nInterestingly, the current models usually assume away the confounders, and not the other way around. In other words, our goal is not to learn the unobserved confounders, since they are unobserved, but to have methods that are robust and could protect against them (without having to measure them explicitly). We argue in this paper that it is hard to assume away confounders in many real-world domains and propose solutions to it. In a way, we are relaxing something baked in many methods in the literature. \n> Typos\n\nThanks! We will fix it in the revised version.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes. The proposed method demonstrates strong potential for supporting offline reinforcement learning with reward shaping, and the evaluation benchmark aligns well with the primary focused challenges.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "The expeimental environment support the fucused challenge well. The proposed method outperform baselines and the provided visualization of the policy make sense to me.\n\nThe only one concern is how would the proposed method in more realistic environments, like MuJoCo?", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "**Strength**\n\n- The paper is well written and easy to follow.\n- The problem is interesting and important to me. \n- The examples provided are very helpful for my understanding. \n\n**Weakness**\n\nHowever, I am somewhat concerned about the generality of the setting. As it is hard to say in the realistic task, how the confounders exist, like between state and action, or only action and reward. Could you please provide additional real-world examples to illustrate its broader applicability? \n\nFurthermore, it would be beneficial if Figure 2 included the transition functions and a clearer demonstration of how the unobservable confounder operates, as this would enable a quicker and more thorough comprehension.\n\nLastly, I would like to confirm my understanding: the confounders can be viewed as hidden states of the environment. Consequently, not only must the behavior policy account for these confounders, but the learned policy should also incorporate them when making decisions. Is that right? Could you please also clarify the role of the confounders in decision-making and policy learning? Is it possible to learn the optimal policy without observing the confounders?", "other_comments_or_suggestions": "In Line 210, it seems a copy-paste error here.", "questions_for_authors": "- Could you provide more real-world examples or case studies to illustrate the broader applicability of your proposed method, beyond the standard benchmark environments?\n\n- In which scenarios are confounders critical for policy learning, and in which cases might they be less relevant or unnecessary? How should one identify and account for such confounders in practice? Can I regard it as one kind of Partitial Observation?", "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": "", "extra_scores": {}}, {"review_id": "aZRjwHXZTC", "reviewer": "Reviewer_89wj", "summary": "This paper addresses the challenge of designing reward shaping functions in reinforcement learning, particularly in the context of Potential-Based Reward Shaping, which traditionally relies on manually crafted potential functions. To overcome this limitation, the authors propose a data-driven approach that automatically learns reward shaping functions from confounded offline data using causal state value upper bounds. The study focuses on Confounded Markov Decision Processes, where unobserved confounders exist at each decision step, making standard offline reinforcement learning methods unreliable. The paper introduces a model-free UCB-based algorithm that leverages derived shaping functions to improve learning efficiency and provides the first theoretical gap-dependent regret bound for PBRS in model-free settings. Finally, empirical results support the theoretical findings.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for your detailed comments. We have addressed your concerns in the sequel.\n\n> Optimality of the learned policy & Question 1\n\nWhile we adopt the regret analysis framework, we acknowledge that it offers only a weaker guarantee of convergence to the optimal policy. A PAC framework may be more suitable for optimality analysis. For empirical evidence of the learned policy quality, we have visualizations in the experiment section (Fig. 5). Since the learned policy is deterministic, we further report the ratio of states where the learned policy is optimal, averaged over three seeds with values closer to 1 indicating better performance. \n\nalgo/env|Windy Empty World|LavaCross(easy)|LavaCross(hard)|LavaCross(maze)\n-|-|-|-|-\nVanilla Q-UCB| .0 | .0 | .0 | .03 \nQ-UCB Shaping (Ours)|.76|**.70**|**.81**|**.90**\nShaping w/ Min. Val.|.72 |.49 | .30 | .24 \nShaping w/ Max Val.|.73 |.52 | .59 | .33\nShaping w/ Avg. Val.|.74 |.50 | .49 | .24\nBCQ| .79|.50|.67|.50\nShaping + BCQ| **.88**|.31|.22|.03\n\n> Applicability to high-dimensional and continuous envs & Weakness 1 & Question 2\n\nThanks for the question! You can refer to the first part of our response to reviewer dtkk.\n> Tight upper bounds\n\nOur proposed method is data-driven, so the learned bound in practice may not be tight. Bound tightness can be improved when multiple datasets are available by taking the minimum over those. Theoretically, the tightness is determined by the natural bounds, without requiring further assumptions about the environment. To illustrate this, we provide a simpler example involving bandits to demonstrate how the bound on rewards can be tight. Our proposed bounds in Equations 5 and 6 are conditional extensions of this idea.\n\nExample: Consider a confounded MAB where reward $Y$ depends on action $X$ and they are confounded by a variable $U$. All variables are binary. The natural bound indicates that the distribution of the reward under interventions can be bounded as $P(y|do(x))=P(x,y)+\\sum_u P(y|x,u)(P(u)-P(u,x))\\leq P(x,y)+\\sum_uP(u)-P(u,x) = P(x,y)+1-P(x)$. Equality is achieved and the bound is tight when $u=0,1,P(y|x,u)=1$, which is possible if the reward is deterministic given an action. \n\n> Latent variable distribution shifts\n\nIn this paper, we study the problem of reward shaping in confounded MDPs. To the best of our knowledge, this work is novel and extends reward shaping methods to address the practical challenges of confounders. We acknowledge that reward shaping in confounded POMDPs and under distribution shifts is a challenging and exciting research question. We appreciate the suggestion.\n\n> More complex confounding biases structures \n\nSince our work is built upon the framework of CMDPs, we do not impose additional constraints on how confounders may correlate with each other. As a result, our approach can handle hierarchical confounders when they fit within the causal diagrams of CMDPs. Exploring the multi-agent case is an interesting direction for future work, as this paper focuses on designing shaping functions for training single agents.\n\n> Related works:\n\nWe have extended the discussion on both offline RL and causal bandits in the revised version. Briefly, many existing offline RL methods learn q-values without accounting for confounders. Some approaches involve learning initial values offline and then fine-tuning them online, but this offline initialization often diminishes during online learning. Our proposed method addresses confounders in the offline data and preserves the extracted knowledge during the online phase through reward shaping. \n\nRegarding causal bandits, our approach shares the same motivation of using causal bounds to address confounding biases and reduce the regret. However, we extend this idea by combining bounds with UCB exploration in sequential domains and applying it to the optimal Bellman equation.\n\n> Weakness 2: Compare with SOTA offline baselines\n\nWe have added experiments to the revised version comparing our method with BCQ, and we summarize the state ratio with optimal policies in the table provided in the first part of our response. We train BCQ using the same mixed confounded datasets as our method’s inputs. We evaluate the performance of the policy extracted directly from BCQ q-values, and the performance of Q-UCB using BCQ values as shaping functions. Our method outperforms both BCQ baselines in non-empty windy grid worlds, where confounder information is essential for completing the tasks.   \n\n> Question 3: performance change under imperfect offline data\n\nIn the revised version, we provide performance results when the good behavioral policy is excluded. To summarize, the final regrets remain nearly unchanged [[img link]](https://ibb.co/album/JBYSZm). Because the bounds from optimal demonstrations are typically overly optimistic; When unifying such bounds with others from imperfect demonstrations, they are not selected by the min operator and thus have minor effects on the shaping functions.", "claims_and_evidence": "The paper claims that Q-UCB Shaping improves sample efficiency, enables convergence to the optimal interventional policy, and provides theoretical guarantees for its causal upper bounds. These claims are partially well-supported.\nThe causal Bellman bounds provide a solid theoretical foundation, making the claim about upper bounding optimal state values convincing. The empirical results show better performance compared to baselines in confounded environments, supporting claims of improved sample efficiency.\nHowever, convergence to the optimal interventional policy is assumed rather than directly analyzed. Additional policy divergence or optimality gap analyses would strengthen this claim.", "methods_and_evaluation_criteria": "The use of CMDPs and causal bounds is well-motivated for the problem of learning from confounded offline datasets. The choice of MiniGrid windy environments is reasonable for demonstrating confounding effects.\nHowever, the limited scale of the environments makes it unclear how the method generalizes to high-dimensional settings.\nThe paper does not compare against stronger offline RL baselines, such as BCQ, CQL, or IRM-based methods, which would provide a better context for the performance gains.", "theoretical_claims": "The paper presents three key theoretical results: (1) the Causal Bellman Optimality Equation (Theorem 3.1), which derives an upper bound for the optimal value function in CMDPs, (2) the Unified Causal Optimal Upper Bound (Corollary 3.2), which extends the bound when multiple offline datasets are available, and (3) the Regret Bound for Q-UCB Shaping (Theorem 4.5), showing improved regret bounds. While these proofs appear correct, they have some limitations. \n1. They assume a tight upper bound on state values, which may not always hold in practice.\n2. They do not explicitly analyze the impact of latent variable shifts under partial observability.", "experimental_designs_or_analyses": "The experiment settings clearly simulate confounding effects in offline reinforcement learning, and the comparison against multiple reward shaping strategies is insightful.\nHowever, the environments are relatively small-scale, limiting their real-world applicability.\nAdditionally, the study would be more compelling if it included experiments with more complex confounding structures, such as hierarchical or multi-agent confounders.", "relation_to_broader_scientific_literature": "The paper connects to:\n1. Offline RL: The method is related to batch-constrained RL and robust RL, but does not compare against conservative Q-learning or implicit Q-learning.\n2. Exploration via UCB: The paper applies UCB exploration in CMDPs, but prior works (e.g., bandit-based causal RL) should be discussed to highlight novelty.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "**Strengths**\n1. The writing is clear and well-structured.\n2. The introduction of causal Bellman optimality bounds is a valuable contribution.\n3. Combining UCB-based exploration with causal bounds is an interesting and underexplored direction.\n\n**Weaknesses**\n1. The approach is tested in small grid-worlds but not in larger RL settings.\n2. The paper does not compare against state-of-the-art offline RL methods, such as CQL, BCQ or IQL.", "other_comments_or_suggestions": "I acknowledge that there are aspects of this paper that I am not fully familiar with, and I may not be a fully qualified reviewer for this topic. However, I am very willing to discuss the work with the authors.", "questions_for_authors": "1. Can you provide empirical evidence showing how close the learned policy is to the optimal interventional policy? Policy divergence metrics would help clarify this.\n2. How well does the method scale to continuous or large state-action spaces? Have you considered testing in Mujoco or other RL benchmarks?\n3. How does the performance change when the offline dataset is sparse or comes from suboptimal behavior policies?", "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": "", "extra_scores": {}}, {"review_id": "VGinqspCMl", "reviewer": "Reviewer_AQkY", "summary": "The paper aims to automate reward shaping when learning policies online via Reinforcement Learning (RL). Authors propose an automated approach for designing reward functions utilizing previously collected offline samples with unobserved confounders. State value upper bounds are calculated and used as a conservative optimistic estimation of the optimal state value function. These estimates are then plugged in to the Potential-Based formulation. Empirical results on toy tasks demonstrate that shaping function provides a better regret bound.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the detailed feedback and appreciate your recognition of the significance of our work. We have addressed each of your concerns in the responses below.\n\n> Weakness 1: “Could the authors provide if they inject any noise in the data distribution? How much confounding does the agent encounter on average? It would be worthwhile to inspect the shaping function on varying grid sizes and under different settings of robustness, i.e- different start states or a larger challenging setting.”\n\nThis paper investigates reward shaping using confounded observational data and demonstrates how the learned shaping function can accelerate future online learning processes. Like many online reinforcement learning (RL) algorithms, the performance guarantee of our proposed method relies on the assumption that the measured variables are discrete (as in MDPs). To our knowledge, the evaluation environments we used are comparable to those in existing studies on online RL and reward shaping in terms of state space and complexity.\n\nAlthough the discrete state space may seem simple, reward shaping remains significantly challenging when unobserved confounding is present or cannot be assumed away. For instance, in our simulation shown in Figure 4(b), naively learning shaping functions from confounded observations, while ignoring the confounders, often fails to capture valuable information, resulting in inconsistent improvements in the performance of online RL algorithms. In contrast, our proposed causal approach achieves an order-of-magnitude improvement.\n\nIn our current experimental setup, uniform random starting positions are used to sample offline data from the environment. We acknowledge that in a large state space with limited starting locations, the offline data may not sufficiently explore the state space, resulting in optimistic estimates for those under-explored states. However, this optimistic estimation is the most reasonable guess at the optimal values of those states, as no other information or assumptions can rule out the possibility that these under-explored states may be highly rewarding.\n\n> Weakness 2: “Could the authors explain their reasoning behind these choices? Also, could a comparison between the causal shaping function and Q-UCB be provided?”\n\nThank you for the opportunity to clarify this issue! We have conducted experiments on vanilla Q-UCB, which corresponds to the “No Shaping” baseline in Fig. 4. In the revised version, we have updated the experiment legend to use the term “vanilla Q-UCB.”\n\nRegarding the design choices we made in Q-UCB Shaping:\n1. **Zero Initialization of Q-values**: Zero initialization is used because when applying a shaping function that serves as an upper bound of the optimal state value, the optimal state values after shaping are shifted downward by the magnitude of the shaping function, which is now at most zero.\n\n2. **Modification of the UCB Bonus**: We modify the UCB bonus to use potential functions because the standard UCB bonus applies an overly optimistic estimate (i.e., number of steps times the maximum reward per step). Since we now have a better upper bound, using it helps reduce overestimation.\n\n3. **Shaped Reward During Updates**: Shaped rewards are used during updates to incorporate additional information extracted from offline data, thereby enhancing the online learning process.\n\n> Weakness 3: “Plots corresponding to experiments could be enlarged and reduced in file size as the paper takes a long time to load. Grammatical errors could be reduced.”\n\nWe appreciate the reviewer’s careful reading of our work. We have corrected the typos, reduced image file sizes, adjusted figure sizes, and further polished the language in the revised version. We will upload it once the portal opens.", "claims_and_evidence": "Please refer to strengths and weaknesses.", "methods_and_evaluation_criteria": "Please refer to strengths and weaknesses.", "theoretical_claims": "Please refer to strengths and weaknesses.", "experimental_designs_or_analyses": "Please refer to strengths and weaknesses.", "relation_to_broader_scientific_literature": "Please refer to strengths and weaknesses.", "essential_references_not_discussed": "Please refer to strengths and weaknesses.", "other_strengths_and_weaknesses": "### Strengths\n* The paper is theoretically rich and detailed in its explanations.\n* The paper studies an important problem in the online setting, often overlooked by the RL community.\n\n### Weaknesses\n* **Empirical Evaluation:** While the paper makes a theoretical contribution, authors have provided empirical experiments to support the regret bound. My main concern is the empirical evaluation carried out on gridworld tasks which present a lower number of confounding states. State spaces for these tasks are countable and thus, it is non-trivial to study the effects of confounders in such a setting. Could the authors provide if they inject any noise in the data distribution? How much confounding does the agent encounter on average? It would be worthwhile to inspect the shaping function on varying grid sizes and under different settings of robustness, i.e- different start states or a larger challenging setting.\n* **Comparison to Q-UCB:** I am struggling to understand the differences and contributions of the shaping scheme when compared to Q-UCB. Primarily, authors introduce zero initialization of Q-values, UCB bonus based on potential function and shaped reward during the updates. Could the authors explain their reasoning behind these choices? Also, could a comparison between the causal shaping function and Q-UCB be provided? In its current form, it is difficult to understand the improvements of utilizing PBRS.\n* **Overall Presentation and Writing:** The presentation and writing quality of the paper could be further improved. Various portions of sections 2 and 3 could be made more intuitive. Theoretical explanations following theorems and corollaries could be made more concise and clear. Plots corresponding to experiments could be enlarged and reduced in filesize as the paper takes a long time to load. Grammatical errors could be reduced. A few are mentioned below.", "other_comments_or_suggestions": "### Minors\n\n* line 85: levering $\\rightarrow$ leveraging\n* line 97: denote the their $\\rightarrow$ denote their\n* line 210: optimal optimal $\\rightarrow$ optimal\n* line 210: state function $\\rightarrow$ state value function\n* line 216: form $\\rightarrow$ from", "questions_for_authors": "Please refer to strengths and weaknesses.", "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": "", "extra_scores": {"ethical_review_concerns": "NA"}}]

Author rebuttal:

Meta-review: This paper tackles the important problem of reward shaping in the presence of unobserved confounding. The authors propose an approach that constructs conservative, optimistic reward shaping functions by leveraging causal state value upper bounds derived from offline datasets. This method is then applied within the PBRS framework to yield improved gap-dependent regret bounds. All reviewers appreciated the clarity of the paper and its strong theoretical foundation, particularly the derivation of causal Bellman optimality bounds and the integration of UCB exploration with causal reasoning. On the other hand, the reviewers consistently expressed concerns about the limited empirical evaluation and the comparison of the existing benchmarks, which would be better highlight in the future, despite the theoretical background of this paper.
Decision: Accept (poster)