Learning to Shape Rewards using a Game of Two Partners
Authors: David Henry Mguni
Jianhong Wang
Taher Jafferjee
Nicolas Perez-Nieves
Wenbin Song
Feifei Tong
Hui Chen
Jiangcheng Zhu
Yaodong Yang
Jun Wang
Venue: ICLR 2022 Submitted (2022)
Keywords: Reinforcement learning
Reward Shaping
Markov game
Sparse rewards

Abstract: Reward shaping (RS) is a powerful method in reinforcement learning (RL) for  overcoming the problem of sparse or uninformative rewards. However, RS typically  relies on manually engineered shaping-reward functions whose construction is time consuming and error-prone. It also requires domain knowledge which runs contrary  to the goal of autonomous learning. We introduce Reinforcement Learning Optimal  Shaping Algorithm (ROSA), an automated RS framework in which the shaping reward function is constructed in a novel Markov game between two agents. A  reward-shaping agent (Shaper) uses switching controls to determine which states to add shaping rewards and their optimal values while the other agent (Controller) learns the optimal policy for the task using these shaped rewards. We prove that ROSA, which easily adopts existing RL algorithms, learns to construct a shaping reward function that is tailored to the task thus ensuring efficient convergence to high performance policies. We demonstrate ROSA’s congenial properties in three carefully designed experiments and show its superior performance against state-of-the-art RS algorithms in challenging sparse reward environments.

Under review as conference paper at ICLR 2022
LEARNING TO SHAPE REWARDS USING A GAME OF TWO PARTNERS
Anonymous authors Paper under double-blind review
ABSTRACT
Reward shaping (RS) is powerful method in reinforcement learning (RL) for overcoming the problem of sparse or uninformative rewards. However, RS typically relies on manually engineered shaping-reward functions whose construction is time-consuming and error-prone. also requires domain knowledge which runs contrary the goal of autonomous learning. We introduce Reinforcement Learning Optimising Shaping Algorithm (ROSA), an automated RS framework in which the shaping-rewand function is constructed in novel Markov game between agents. A reward-shaping agent (Shaper) uses switching controls to determine which states add shaping rewards and their optimal values while the other agent (Controller) learns the optimal policy for the task using these shaped rewards. We prove that ROSA, which easily adopts existing RL algorithms, learns construct shaping- reward function that is tailored to the task thus ensuring efficient convergence high performance policies. We demonstrate ROSA's congenial properties in three carefully designed experiments and show its superior performance against titte-ofthheait RS algorithms challenging sparse reward environments.
INTRODUCTION
Reinforcement learning (RL) offers the potential for autonomous agents to learn complex behaviours without the need for human intervention [39]. Despite the notable success of RL in variety domains [8, 31, 35, 24], enabling RI algorithms to learn successfully in numerous real-world tasks remains a challenge [41]. A key obstacle to the success of RI. algorithms is the requirement
rich reward signal that can guide the agent towards an optimal policy [7]. In many settings of interest such as physical tasks and video games, rich informative signals of the agent's performance are not readily available [14]. For example, in the video game Super Mario [33], the agent must perform sequences of hundreds actions while receiving no rewards for it to successfully complete its task. In this setting, the sparse reward provides infrequent feedback of the agent's 's performance. This leads to RL algorithms requiring large numbers of samples (and high expense) for solving problems [14]. Consequently, there is great need for RL techniques that solve these problems efficiently.
Various biological systems have mechanisms that produce rewards for activities that present little or direct biological utility. Such mechanisms, which have been fashioned over millions of years are designed to provide intrinsic rewards to promote behaviours that improve chances of outcomes with biological utility [1]. In RL, reward shaping (RS) tool to introduce intrinsic rewards known as shaping rewards that supplement environment reward signals. These rewards can encourage explo- ration and insert structural knowledge in the absence of informative environment rewards which can improve learning outcomes [10]. In general however, RS algorithms assume hand-crafted and domain- specific shaping functions whose construction typically highly labour intensive. This runs contrary to the aim of autonomous learning. Moreover, poor choices of shaping rewards can worsen the agent's performance [9]. To resolve these issues, a useful shaping reward must be obtained autonomously.
Inspired by naturally occurring systems, we tackle the problem of sparse and uninformative rewards by developing a framework that autonomously constructs shaping rewards during learning. Our framework, ROSA, works by introducing additional RL agent, Shaper, that adaptively learns to construct shaping rewards by observing Controller (the agent whose goal is to solve the environment task) while Controller learns solve its task. This generates tailored shaping rewards without the

---

Under review as conference paper at ICLR 2022
need for domain knowledge or manual engineering. The shaping rewards supplement the environment reward and promote effective learning, our framework therefore addresses the key challenges in RS.
The resulting framework is two-player nonzero-sum Markov game (MG) [34] an extension of Markov decision process (MDP) that involves two independent learners with distinct objectives. In our framework, the two agents that have distinct learning agendas, cooperate to achieve Controller's objective. This MG formulation confers various advantages:
1) The shaping-reward function is constructed fully autonomously. The game also ensures the shaping reward improves Controller's performance unlike RS methods that can lower performance.
2) By learning the shaping-rewar function while Controller learns its optimal policy, Shaper learns to adaptively facilitate Controller's s learning and improve Controller's ' performance.
3) Both learning processes converge so Controller learns the optimal value function for its task.
4) ROSA learns subgoals [28] to decompose complex tasks and promote complex exploration patterns.
An integral component of ROSA is novel combination of RL and switching controls [2. 22]. This enables Controller to quickly determine useful states to learn to add and calibrate shaping rewards (i.e. the states in which adding shaping rewards improve Controller's performance) and disregard others. This is in contrast with an RL controller (i.e. Controller) which must learn its best actions at every state. This leads to Shaper quickly finding shaping rewards that guide Controller's 's learning process toward optimal trajectories (and away from suboptimal trajectories, c.f. Experiment 1).
For our two-player framework to succeed we have to overcome several obstacles. Solving MGs involves finding stable point in which each player responds optimally to the actions of the other. In our MG, this stable point describes a pair of policies for which Shaper introduces a shaping reward that improves performance and, with that, Controller executes optimal policy for the task. Tractable methods for solving MGs are rare with convergence of MG methods being seldom guaranteed except in a few special cases [42]. Nevertheless, using special features in the design of our game, we prove the existence of stable point solution of our MG. We then prove the convergence of our learning method to the solution of the game and show that the solution coincides with the solution of the Controller's 's problem. This ensures Shaper learns a shaping- reward function that improves Controller's 's performance and that Controller learns the optimal value function for the task.
2 RELATED WORK
Reward Shaping (RS) adds a shaping function F to supplement the agent's reward to boost learning. RS however has some critical limitations. First, RS does not offer a means of finding F. Second, poor choices of F' can worsen the agent's performance [9]. Last, adding shaping rewards can change the underlying problem therefore generating policies that are completely irrelevant to the task [20]. In [27] it was established that potential-based reward shaping (PBRS) which adds shaping function of the form F( 8,) = r0($++1) - (((;)) preserves the optimal policy of the problem. Recent variants of PBRS include potential-based advice which defines F over the state-action space [13] and approaches that include time-varying shaping functions [11]. Although the last issue can be addressed using potential-bas based reward shaping (PBRS) [27], the first two issues remain. To avoid manual engineering of F. useful shaping rewards must be obtained autonomously. Towards this [45] introduce RS method that adds a shaping-rewar obtained over many tasks. Recently, [16] use a bilevel technique to learn a scalar coefficient for an already-given shaping-reward function. Nevertheless, constructing F' while training can produce convergence issues since the reward function now changes during training. [17]. Moreover, while F' being learned the reward can be corrupted by inappropriate signals that hinder learning.
function prior which fits distribution from data
Curiosity based reward shaping aims to encourage the agent to explore states by rewarding the agent for novel state visitations using exploration heuristics. One approach is use state visitation counts [29]. More elaborate approaches such as [6] introduce measure of state novelty using the prediction error of features of the visited states from random network. [30] use the prediction error of the next state from learned dynamics model and [15] maximise the information gain about the agent's 's belief of the system dynamics. In general, these methods provide no performance guarantees nor do they ensure the optimal policy (of the underlying MDP) is preserved. Moreover, they naively reward exploration to unvisited states without consideration of the environment reward. This can lead to spurious objectives being maximised (see Experiment 3 in $6).
Within these two categories, closest to our work are bilevel approaches for learning the shaping function [16, 36). Unlike [16] which requires useful shaping reward to begin with, ROSA constructs
2

---

Under review as conference paper at ICLR 2022
a shaping reward function from scratch leading to a fully autonomous method. Moreover, in [16, 36], the agent's 's policy and shaping rewards are learned with consecutive updates. In contrast, ROSA performs these operations concurrently leading to a faster, more efficient procedure. Also in contrast to [16, 36], ROSA learns shaping rewards only at relevant states, this confers high computational efficiency (see Experiment 2, $6)). As we describe, ROSA, which successfully learns the shaping- reward function F. uses a similar form as PBRS. However in ROSA, F is augmented include the actions of another RL agent to learn the shaping rewards online. Lastly, unlike pariosity-baseed methods e.g., [6, 30), our method preserves the agent's 's optimal policy for the task (see Experiment 3, 56) and introduces intrinsic rewards that promote complex learning behaviour (see Experiment 1, $6).
PRELIMINARIES & NOTATIONS
In RL, an agent sequentially selects actions to maximise its expected returns. The underlying problem is typically formalised as a MDP (S, A, P. R) where S is the set of states, A is the discrete set of actions, P: : x A + [0, 1] is transition probability function describing the system's 's dynamics, R: x A- + IR is the reward function measuring the agent's performance, and the factor 7 E [o, 1) specifies the degree which the agent's rewards are discounted over time [39]. At time the system is in state E S and the agent must choose an action a₂ E A which transitions the system to new state 5t-1 ~ P(-|s az) and produces reward R(st, de). policy π S x A [0. 1] is a probability distribution over action pairs where [[ass) represents the probability of selecting action a E AA in state s E S. The goal of an RL agent is to find policy I' II that maximises its expected returns given by the value function: v (8) EE 7 R[(s,, ax) ~ x (-11s)] where II is the agent's policy set. We denote this MDP by Dt.
A two-player Markov game (MG) is an augmented MDP involving two agent that simultaneously take actions over many rounds [34]. In the classical MG framework, each agent's 's rewards and the system dynamics are now influenced by the actions of both agents. Therefore, each agent i {1, has its reward function Rg : S x A₁ x A + I and action set A₁ and its goal is to maximise its own expected returns. The system dynamics, now influenced by both agents, described by a transition probability P : S x Ai x A x S + [0, 1]. As we discuss in the next section, ROSA induces a specific MG in which the dynamics are influenced by only Controller.
In RS the question of which & to insert has not been addressed. Moreover it has been shown that poor choices of hinder learning [9]. Consequently, in general RS methods rely on hand-crafted shaping-reward functions that are constructed using domain knowledge (whenever available). In the absence of a useful shaping-reward function F', the challenge is to learn a shaping-reward function that leads to more efficient learning while preserving the optimal policy. Naturally, we can formalise the problem of learning such an F by constructing F as a parametric function of E Rm.
F( 8y; 0) == 70 0) ((8t, 0). Now the problem to find 0* E T for ((x) = (x 0*) such that F( st) = F (S1+1, Sc: ), i.e., we aim to find 0* that yields a useful reward function. Determining this function is significant challenge; poor choices can hinder the learning process, moreover attempting to learn the shaping-function while learning the RL agent's policy presents convergence issues given the two concurrent learning processes [44]. Another issue is that using an optimisation procedure to find 0* directly does not make use of information generated by intermediate state-action-rewaes tuples of the RL problem which can help guide the optimisation.
4
OUR FRAMEWORK
We now describe the problem setting, details of our framework, and how it learns the shaping-rewe reward function. We then describe Controller's 's and Shaper's objectives. We also describe the switching control mechanism used by Shaper and the learning process for both agents.
To tackle the challenges described above, we introduce Shaper an adaptive agent with its own objective that determines the best shaping rewards to give to Controller. Using observations of the actions taken Controller, Shaper's goal is to construct shaping rewards (which the RL learner Controller cannot generate itself) to guide the Controller towards quickly learning its optimal policy. To do this, Shaper learns how to choose the values of an shaping-rewan at each state. Simultancously, Controller performs actions to maximise its rewards using its own policy. Crucially, the two agents tackle distinet but complementary set problems. The problem for Controller is to learn to solve the
3

---

Under review as conference paper at ICLR 2022
task by finding its optimal policy, the problem for Shaper is to learn how to add shaping rewards to aid Controller. The objective for Controller is given by:
(((s), + Foe, of 11 of d |s ] 1
E
where a π is Controller's is action, F is the shaping-reward function which is given by F(.) = ((st, af) - r 1(,,,, - for any St, st-1 E S and až ~ x² is chosen by Shaper (and aj 0, Vt < 0) using the policy x :S A - [0, 1] where A₂ C IP is the action set for Shaper. The function Φ S x A2 + R is continuous map that satisfies the condition 6(s, 0) = 0 for any E S (ø can be, for example, a neural network with fixed weights with input (s, a Ag can be for example a set of integers {L.... }). Therefore. Shaper determines the output of f (which it does through its choice of az). With this, Shaper constructs thaping-reward function which is tailored for the specific setting. The transition probability P: S x A - [0, takes the state and only Controller's actions as imputs. Formally, the MG is defined by tuple G = (N, S, A, A2, P. R1, R2, 7) where the new elements are N {1,2] which is the set of agents, Ri =- R + F is the new Controller reward function which now contains a shaping reward F, the function R₂ S x A A2 - E is the one-step reward for Shaper (we give the details of this function later) and lastly the transition probability P S x A x S + [0, 1] takes the state and only Controller action as inputs.
As Controller's policy can be learned using any RL method, ROSA easily adopts any existing RL algorithm for Controller, Note that unlike reward-shaping methods e.g. [27], the function & now contains an action term a² which is chosen by Shaper which enables the best shaping-reward function to be learned online. The presence of an action term may spoil the policy invariance result in [27]. We however prove policy invariance result (Prop. 1) analogous to that in [27] and show RIGA preserves the optimal policy for M.
4.1 SWITCHING CONTROLS
So far Shaper's problem involves learning to construct shaping rewards at every state including those that are irrelevant for guiding Controller. In order to increase the (computational) efficiency of Shaper's learning process, now replace the policy space for Shaper with form of policies known as switching controls. This enables Shaper to decide at which states to learn the value of shaping rewards it would like to add. Therefore, now Shaper is tasked with learning how to shape Controller's s rewards only at states that are important for guiding Controller to its optimal policy. This enables Shaper to quickly determine its policy x² and how to choose the values of F unlike Controller whose policy must learned for all states.
Now at each state Shaper first makes binary decision decide switch its shaping reward F for Controller affecting a switch I, which takes values in {0,13, This leads to an MG in which, unlike classical MGs, Shaper now uses switching controls perform its actions.
The
is: where I = 1 It., which is the switch for the shaping rewards which is 0 or (and 7, = O, Vt S 0) and {Tx} are times that switch takes place for example if the switch is first turned on at state 35 then turned off at 87, then T 5 and T2- = 7 (we will shortly describe these in detail). The switch I, is managed by Shaper, therefore by switching I, between 0 1, Shaper activates or deactivates the shaping reward.
new
Controller
objective
0j n, (so. lo)
[EEon' 7 (R(s, ..) + F(s,, at 8t- at af of )..]].
We now describe how at each state both the decision to activate a shaping reward and their magnitudes determined. Recall that of ~ x² determines the shaping reward through F. At any st, the decision to turn on 1 and shape rewards is decided by a (categorical) policy 02 S - {0,1). 1]. Therefore, $2 determines whether (or no) Shaper policy x² should be used to execute action af ~ x² It can now be seen the sequence of times 7 = inf > T E S. (s,,) = 1} are rules that depend on the state. Hence, by learning an optimal g2. Shaper learns the best states to activate F.
Summary of events:
At time L 0,
4

---

Under review as conference paper at ICLR 2022
Both players make an observation of the state s; E S. Controller takes an action de sampled from its policy я.
Shaper decides whether or not activate the shaping reward using 92 : : {0, 1]
If (sx)) = 0:
o The switch is not activated (I, = 0). Controller receives a reward r ~ R(s, (e) and the system transitions to the next state 81+1-
If (2()) =
Shaper takes an action of sampled from its policy x².
o The switch is activated (4, 1), Controller receives a reward R(st, ar) +
F(s,, ((-1) x 1 and the system transitions to the next state 81+1.
We set 7 = Ovk I 0 and o
0, vk N (a (1..+ m remain non-zero) and o =
0 vk and use the shorthand [(t) L.
4.2 THE SHAPER'S OBJECTIVE
The goal of Shaper to guide Controller to efficiently learn to maximise its own objective (given in M).. The shaping reward F' is activated by switches controlled by Shaper. As we later describe, the termination times occur according to some external (probabilisttc) rule. To induce Shaper to selectively choose when to switch the shaping reward, each switch activation incurs fixed cost for Shaper. The cost has two effects: first it reduces the complexity of Shaper problem since its decision space determine which subregions of S it should activate the shaping rewards (and their magnitudes). Second, it ensures that the information-ged gain from Shaper encouraging Controller to explore given of states is sufficiently high merit activating the stream of rewards. Given these remarks the objective for Shaper is given by
2. (su, Ia) En,
Σn
aa Σ
c1l1,-1-)8mmm- + L(si) 121
(I)
The objective encodes Shaper agenda, namely to maximise the expected return. Therefore, using its shaping rewards, Shaper seeks to guide Controller towards optimal trajectories (potentially away from suboptimal trajectories, c.f. Experiment 1) and enable Controller to learn faster (c.f. Cartpole experiment in Sec. 6). The function e : {0, 132 + R=o is a strictly negative cost function which imposes cost for each switch and is modulated by the Kronecker-delta function 8 8 which is 1 whenever t = T2k-1 and O otherwise (this restricts the costs to only the points at which the shaping reward activated). Lastly, the term L S + IR Shaper bonus reward for when Controller visits infrequently visited states and tends to 0 as the states are revisited. For this there are various possibilities e.g. model prediction error [37], count-based exploration bonus [38].
With this, Shaper constructs shaping-reward function that supports Controller's learning which tailored for the specific setting. This avoids inserting hand-designed exploration heuristics into Controller's objective as in curiosity-basee later prove that with this objective, Shaper's s optimal policy maximises Controller's 's (extrinsic) return (Prop. 1). Additionally, we show that the framework preserves the optimal policy of MT.
methods [6, 30] and classical reward shaping [27]. We
There are various possibilities for the termination times } (recall that (T2++1) } are the times which the shaping reward F is switched using g2). One is for Shaper determine the sequence. Another to build a construction of {T2x) that directly incorporates the information gain that a state visit provides
defer the details of this arrangement Sec. 10 of the Appendix.
4.3 THE OVERALL LEARNING PROCEDURE
The game G is solved using our multi-agent RL algorithm (ROSA). In the next section, we show the convergence properties of ROSA. Here, we first give a description of ROSA (the full code is in Sec. 8 of the Appendix). The ROSA algorithm consists of two independent procedures: Controller learns its own policy while Shaper learns which states to perform switch and the shaping reward magnitudes. In our implementation, we used proximal policy optimization (PPO) [32] as the learning algorithm
Note that can that R₂ R(8s, ) F(s,, as: 8t-1, 1 di Exe c(J,, 16
5

---

Under review as conference paper at ICLR 2022
for all policies: Controller's policy, switching control policy, and the reward magnitude policy. For Shaper L term we used L(s)) := [[h(st) - ( as in RND [6] where h is random initialised, fixed target network while h is the predictor network that seeks to approximate the target network. We constructed F using a fixed neural network f R + R and one-hot encoding of the action of Shaper. Specifically, (0(8,, az) ((+) i(a?) where i(af) is one-hot encoding of the action of picked by Shaper. Thus, F(s,, af: St-1, -f- f(s)) i(aa) - - f((=1) i(aā_1). The action
set of Shaper is thus A₂ == {0, 1.... m. where each element is an element of N, and T2 is a MLP 222 : Rd + Rm Precise details are in the Supplementary Materials Section
Algorithm I: Reinforcement Learning Optimising Shaping Algorithm (ROSA)
Input: Initial Controller policy mu, Shaper policies 92g m RL learning algorithm A Output: Optimised Controller policy n
for f = 1,7 do
Given environment state 8t, sample a, from (ss:) and obtain 81+1, T1+1 by applying a, to environment
Evaluate (s;) according to Prop. 2
(2({s) = then
Shaper samples an action a²+1 (-1941) Shaper computes ri+1 = F(,, at, 8241, 0241) Set shaped reward r = r++1 + ri+1
8
else
L Setr Tt+1
10
Update π, 92; 2 using (st, ae, r, 8141) and A Learn the individual policies
CONVERGENCE AND OPTIMALITY OF OUR METHOD
The ROSA framework enables Shaper to learn shaping-reward function with which Controller can learn the optimal policy for the task. The interaction between the two RL agents induces two concurrent learning processes which can occasion convergence issues [44]. We now show that our method converges and the solution ensures higher performing Controller policy than would be achieved by solving D1 directly. To do this, we first study the stable point solutions of G.
Unlike MDPs, the existence of stable point solution in Markov policies is not guaranteed for MGs [5] and is rarely computable." MGs also often have multiple stable points that can be inefficient [25]; in G the outcome of such stable point profiles would be poor performing Controller policy. To ensure the framework is useful, we must verify that the solution of G corresponds to Wt. We solve these challenges with the following scheme: [A] The method preserves the optimal policy of Mt. [B] stable point of the game G in Markov policies exists and is the convergence point ROSA. [C] The convergence point of ROSA yields payoff that is (weakly) greater than that from solving Di directly. [D] ROSA converges to the stable point solution of G.
We now prove [A] which shows the solution M. is preserved under the influence of Shaper:
Proposition 1 The following statements hold:
i) max vj s.m TEll
(s) max of (s), Vs E S,VT' 112, where uf [2
"*(ss,, at)l
HEll
ii) The Shaper's optimal policy maximises (s) for any E S.
Result (i) says that the Controller's 's problem is preserved under the influence the Shaper. Moreover the (expected) total return received by the agents is that from the environment (extrinsic rewards). Result (ii) establishes that Shaper's 's optimal policy induces Shaper to maximise its (Controller's extrinsic total return. The result is established by careful adaptation of the policy invariance result in [27] to our multi-agent switching control framework in which the shaping reward is no longer added at all states. Building on Prop. we deduce the following result:
Special exceptions are team MGs where agents share objective and zero-sum MGs [34].

---

Under review as conference paper at ICLR 2022
Corollary ROSA preserves the MDP Mt. In particular, let (f , be a stable point policy profile? of the MG induced by ROSA 9 then a² is a solution to the MDP, MR.
Therefore, the introduction of Shaper does not alter the fundamentals of the problem.
We now show that G belongs to special class of MGs which possess stable point Markov policies which can be computed as a limit point of a sequence of Bellman operations. We later exploit this result to prove the convergence of ROSA.
We begin by defining some objects which are central to the analysis. For any π E II and n² E 112, given function V= S x N + R, we define the intervention operator M by MM M" (s7,, ((T))) = (a(sT,;((Tk), ar a + c(IR, Eves a,, (s', I(Tx+1)) for any Sn, E and VTy where an ~ ((1( and where a (-1s)))) We define the Bellman operator T of the game & by TV (St ((Tx)) max {M ((T)), R(sre a) + ymax function (V:)e the quantity MV; measures the expected future stream of rewards for agent i after an immediate switch minus the cost of switching.
aeA Eves P(s'; 8ry A (T))) Given a value
We now show that stable point of G can be computed using dynamic programming:
Theorem Let V S + R then the game has a stable point which is given by lim Th
k-00
sup V = V*",, where ît is a stable policy profile for the MG, G.
#ell
Theorem 1 proves that the MG G (which is the game that is induced when Shaper influences Controller) has a stable point which is the limit of a dynamic programming method. In particular, Crucially,
it proves the that the stable point of G is the limit point of the sequence T TVV. (by Corollary 1) the limit point corresponds to the solution of the MDP M. Theorem is proven by firstly proving that G has a dual representation an MDP whose solution corresponds to the stable point of the MG. Theorem enables a distributed Q-learning method [4] to tractably solve the MG.
Having constructed procedure to find the optimal Controller policy, our next result characterises Shaper policy 22 and the optimal times to activate F.
Proposition 2 The policy g2 is given by the following expression: g2(st) = (M V Vs. (s,, It), V(s,, Te) E S x 13, where V is the solution in Theorem I and H is the Heaviside function, moreover Shaper's switching times are Tk inf(T > Tk- Tm-1IMM..''m.>>
Va,=²)
Hence, Prop. 2 also characterises the (categorical) distribution g2. Moreover, given the function V. the times (Tk} can be determined by evaluating if MV = V holds. In general, introducing shaping rewards may undermine learning and worsen overall performance. We now prove that the ROSA framework introduces shaping rewards that yield higher total (environment) returns for Controller as compared to solving 21 directly ([C)).
Proposition 3 Controller's (extrinsic) expected return x,x² whilst playing & is (weakly) higher than vi, the (extrinsic) expected return for M. i.e. vi (s,-) of (s), Vs E S.
Prop. 3 shows that the stable point of G improves outcomes for Controller. Unlike reward shaping methods in general, the stable points generated never lead to reduction to the total (environment) return for Controller as compared to its total return without F. Note that by Prop. 1, Theorem compares the environment (extrinsic) rewards accrued by the agents so that the presence of Shaper increases the total expected environment rewards.
We now prove the convergence to the solution with (linear) function approximators. In what follows, we define a projection 11 on function A by: IIA := arg min ||A A/
AE(Vr|rER*)
Theorem ROSA converges to the stable point of 9, moreover, given set of linearly independent basis functions V {Vi,.... } with the E L2, Vk, ROSA converges a limit point r* RRP which
'B stable point profile mean a configuration in which agent can increase their expected return by deviating unilaterally from their policy given the other agents' policies, i.c. Markov perfect equilibrium [12].
7

---

Under review as conference paper at ICLR 2022
is the unique solution to (T3()r*) = Vrr where 3 is defined by: BA = Ru + max (MA, A}
where r" satisfies: ||rr"* - Q-1 Σ (1 (1- IQQ - Q*Il-
Theorem 2 establishes the solution to 9 can be computed using ROSA. This means that Shaper converges to a shaping-rewee -rwwrrd function that necessarily improves Controller's performance and Controller learns the optimal value function for the task. Secondly, the theorem establishes the convergence of ROSA to the solution using (linear) function approximators. Lastly the approximation error is bounded by the smallest error that can be achieved given the basis functions.
EXPERIMENTS
We performed a series of experiments to test ROSA (1) learns a beneficial shaping-rewars function (2) decomposes complex tasks into sub-goals, and (3) tailors shaping rewards encourage Controller to capture environment rewards (as opposed to merely pursuing novelty). In these tasks, we com- pared the performance of our method to random network distillation (RND) [6]. intrinsic curiosity module (ICM) [30], learning intrinsic reward policy gradient (LIRPG) [43], bi-level optimization of parameterized reward shaping SiPaRRSIMGLA [16]* and vanilla PPO [32]. We then compared our method against these baselines on performance benchmarks including Sparse Cartpole, Gravitar, Solaris, and Super Mario. Lastly, we ran a detailed suite of ablation studies (supplementary material).
1. Beneficial shaping reward. Our method is able to learn shaping- reward function that leads to improved Controller performance. In particu- lar, it is able to learn to shape rewards that encourage the RL agent to avoid suboptimal but easy to learn poli- cies in favour of policies that attain the maximal return. To demonstrate this, we designed Maze environment with two terminal states: a suboptimal goal state that yields a reward of 0.5 and an optimal goal state which yields reward of 1. In this maze design, the sub-optimal goal more easily reached. A good shaping-reward function discourages the agent from visiting the sub-optimal goal. As shown in Fig. our method achieves this by learning to place high shaping rewards (dark green) on the path that leads to the optimal goal.
ROSA
Arhak Suleptina (Oglinal
Suteopimml
Count Based
Ostimall
0.75
AND
11
0.25
82
01aT
Stops (163)
Figure 1: Left. Proportion of optimal and suboptimal goal arrivals. Our method has a marked inflection (arrow) where arrivals at the sub-optimal goal decrease and arrivals the op- timal goal increase. Shaper has learned to guide Controller to forgo the suboptimal goal in favour of the optimal one. Right. Heatmap showing where our method adds rewards.
2. Subgoal discovery. We used the Subgoal Maze introduced in [21] to test if ROSA can discover sub- goals. The environment has two rooms separated by gateway. To solve this, the agent has discover the subgoal of reaching the gateway before it can reach the goal. Rewards are -0.01 everywhere except the goal state where the reward is 1. As shown in Fig. 2, our method successfully solves this environment whereas other methods fail. Our method assigns im- portance to reaching the gateway, depicted by the heatmap of added shaped rewards.
RODA
Court RNC
70 Stops (3:3)
103
350
Figure 2: Discovering subgoals on Subgoal Maze. Left. Learning curves. Right. Heatmap of shaping rewards guiding Controller gate. 3. Ignoring beneffeefiaa shaping reward. Switching control gives our method the power to learn when to attend to shaping rewards and when to ignore them. This allows us to learn to ignore "red-herrings"; i.e., unexplored parts of the state space where there is no real environment reward, but where surprise novelty metries would place high shaping reward. To verify this claim, we use modified Maze environment called Red- eed-Herring Maze which features a large part of the state space that has environment reward, but with the goal (and accompanying real reward) in different part
"BiPaRS-IME IIGL requires manually crafted shaping-
reward (only available in Cartpole). 'The sum of curves for each method may be less that if the agent fails arrive either goal.
8

---

Under review as conference paper at ICLR 2022
of the state space. Ideally, we expect that the reward shaping method can learn to quickly ignore the large part of the state space. Fig. shows that our method outperforms all other baselines. Moreover, the heatmap shows that while RND is easily dragged to reward exploring novel but non rewarding states our method learns ignore them.
ROSA
Count Based
Start
Ratur
Gool
RND
100
150
Steps (1e3)
Figure 3: Red- Red-Herring Maze. Ignoring non-beneficial shap- ing reward. Left. Leaninng curves. Right. Heatmap of added shaping rewards. ROSA ignores the RHS of the maze, while RND incorrectly adds unuseful shaping rewards there.
Learning Performance. We com- pared our method with the baselines in four challenging sparse rewards en- vironments: Cartpole, Gravitar, So- laris, and Super Mario. These envi- ronments vary in state representation, transition dynamics and reward spar- sity. In Cartpole, a penalty of -1 received only when the pole collapses; in Super Mario Brothers the agent can go for 100s of steps without encoun- tering a reward. Fig. shows learn- ing curves. In terms of performance, ROSA either markedly outperforms the best competing baseline (Cartpole, Gravitar) or is on par with them (So-
Cartpole
730
200
Length
Epionde retur
520
Steosile31 Soleris
400
Steps11c6)
2000
Super Mario
Epxade Return
1003 2200
Ruturn
500
Stcps
Stepsited)
BIPars-IMEL
laris, Super Mario) showing that is
(Harmful shoping reward)
ROSA
robust to the nature of the environ- ment and underlying sparse reward. Moreover, ROSA does not exhibit the failure modes where after good initial performance it deteriorates. E.g., in Solaris both ICM and RND have good initial performance but deteriorate sharply while ROSA's performance remains satisfactory.
BIPaRS-IMGL
shaping reward)
PPO
URPG
Figure 4: Benchmark performance.
CONCLUSION
In this paper, we presented novel solution method to solve the problem of reward shaping. Our Markov game framework of primary Controller and secondary reward shaping agent is guar- anteed to preserve the underlying learning task for Controller whilst guiding Controller to higher performance policies. Moreover, our method is able to decompose complex learning tasks into subgoals and to adaptively guide Controller by selectively choosing the states to add shaping rewards. By presenting theoretically sound and empirically robust approach to solving the reward shaping problem, our method opens up the applicability of RL to range of real-world control problems. The most significant contribution of this paper, however, is the novel construction that marries RL, multi-agent RI. and game theory which leads to new solution method RI. We believe this powerful approach can be adopted solve other open challenges in RI.

---

Under review as conference paper at ICLR 2022
REFERENCES
[ Gianluca Baldassarre. "What are intrinsic motivations? A biological perspective". In: 201 IEEE international conference on development and learning (ICDL). Vol. 2. IEEE. 2011,
pp. 1-8.
[2] Erhan Bayraktar and Masahiko Egami. "On the one-dimensional optimal switching problem".
In: Mathematics of Operations Research 35.1 (2010), pp. 140-159.
[3]
Albert Benveniste, Michel Métivier, and Pierre Priouret. Adaptive algorithms and stochastic approximations. Vol. 22. Springer Science & Business Media, 2012.
[4]
Dimitri P Bertsekas. Approximate dynamic programming. Athena scientific Belmont, 2012.
[5] David Blackwell and Tom S Ferguson. "The big match". In: The Annals of Mathematical Statistics 39.1 (1968), 159-163.
[6] Yuri Burda et al. "Exploration by random network distillation". In: arXiv preprint 18 12894 (2018).
[7] Henry Charlesworth and Giovanni Montana. "PlanGAN: Model-based Planning With Sparse Rewards and Multiple Goals". In: arXiv preprint arXiv:2006.000 00900 (2020).
[8] Mare Peter Deisenroth, Carl Edward Rasmussen, and Dieter Fox. "Learning to control a low-cost manipulator using data-efficient reinforcement learning". In: Robotics: Science and Systems VII (2011), pp. 57-64.
[9] Sam Devlin and Daniel Kudenko. "Theoretical considerations of potential-based reward shaping for multi-agent systems". In: The 10th International Conference on Autonomous Agents and Multiagent Systems- Volume 1. International Foundation for Autonomous Agents and Multiagent Systems. 2011, pp. 225-232.
[10] Sam Devlin, Daniel Kudenko, and Marek Grzeš. "An empirical study of potential -based reward shaping and advice in complex, multi-agent systems". In: Advances in Complex Systems 14.02
(2011), 1), pp. 251-278.
[1]] Sam Michael Devlin and Daniel Kudenko. "Dynamic potential-base -based reward shaping". In: Proceedings of the 11th International Conference on Autonomous Agents and Multiagent Systems. IFAAMAS. 2012, pp. 430-440.
[12] Drew Fudenberg and Jean Tirole. "Tirole: Game Theory". In: MIT Press 726 (1991), 764.
[13]
Anna Harutyunyan al. "Expressing arbitrary reward functions as potential-bate -based advice".
In: Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 29. 2015.
[14]
lonel-Alexandru Hosu and Traian Rebedea. "Playing atari games with deep reinforcement learning and human checkpoint replay". In: arXiv preprint arXiv: 0tt0//600000777 (2016).
[15] Rein Houthooft et al. "Vime: Variational information maximizing exploration". In: arXiv preprint arXiv: /60500967 (2016).
[16] Yujing Hu al. "Learning to Utilize Shaping Rewards: A New Approach of Reward Shaping".
In: Advances in Neural Informaiinn Processing Systems 33 (2020).
[17] Maximilian Igl et al. "The Impact of von-stationaritt on Generalisation in Deep Reinforcement Learning". In: arXiv preprint Niv:22006008822 (2020).
[18] Tommi Jaakkola, Michael Jordan, and Satinder P Singh. "Convergence of stochastic iterative
dynamic programming algorithms". In: Advances in neural information processing systems. 1994, pp. 703-710.
[19] Sergio Valcarcel Macua, Javier Zazo, and Santiago Zazo. "Learning Parametric Closed-Loop Policies for Markov Potential Games". In: arXiv preprint 1802, 00899 (2018).
[20] Patrick Mannion et al. "Policy invariance under reward transformations for multi-objective reinforcement learning". In: Neurocomputingg 263 (2017), pp. 60-73.
[21] Amy McGovern and Andrew G Barto. "Automatic discovery of subgoals in reinforcement learning using diverse density". In: (2001).
[22] David Mguni. "A Viscosity Approach Stochastic Differential Games of Control and Stop-
ping Involving Impulsive Control". In: arXiv preprint arXiv:1803: 113.1145. 1432 (2018).
[23] David Mguni. "Cutting Your Losses: Learning Fault-Toleran Control and Optimal Stopping under Adverse Risk". In: arXiv preprint arXiv:1902.0504 (2019).
10

---

Under review as conference paper at ICLR 2022
[24] David Mguni, Joel Jennings, and Enrique Munoz de Cote. "Decentralised learning in sys- tems with many, many strategic agents". In: Pherot--ecood AAAI Conference on Artificial Intelligence. 2018.
[25] David Mguni al. "Coordinating the crowd: Inducing desirable equilibria in non-cooperative systems". arXiv preprint arXiv: 1901. 10923 (2019).
[26] David Mguni et al. "Learning in Nonzero-Sum Stochastic Games with Potentials". In: arXiv preprint arXiv:2103.0923 (2021).
[27] Andrew Ng, Daishi Harada, and Stuart Russell, "Policy invariance under reward trans- formations: Theory and application to reward shaping". In: ICML. Vol. 99. 1999, pp. 278- 287.
[28]
David C Noelle. "Unsupervised methods for subgoal discovery during intrinsic motivation in model-free hierarchical reinforcement learning". In: KEG@ AAAI. 2019.
[29] Georg Ostrovski et al. "Count-basee based exploration with neural density models". In: arXiv preprint arXiv: 703.01310 (2017).
[30]
Deepak Pathak et al. "Curiosity-driver Exploration by Self-supervised Prediction". In: Inter- national Conference on Machine Learning (ICML... 2017,, pp. 2778-2787.
[31] Peng Peng et al. "Multiagent inirectionallyccordinaee nets: Emergence of human-level coordination learning to play starcraft combat games". In: arXiv preprint arXiv:1703. (2017).
[32]
John Schulman et al. "Proximal Policy Optimization Algorithms". In: CoRR abs/1 707.06347 (2017).
[33] Kun Shao et al. "A survey of deep reinforcement learning in video games". In: arXiv preprint arXiv: 10944 (2019).
[34] Yoav Shoham and Kevin Beyton-Browe Multiagent systems: Algorithmic, game-theoretic, and logical foundations. Cambridge University Press, 2008.
[35] David Silver al. "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play". In: Science 362.6419 (2018), pp. 1140-1144.
[36] Bradly Stadie, Lunjun Zhang, and Jimmy Ba. "Learning Intrinsic Rewards as a Bi-Level Optimization Problem".. In: Conference on Uncertainty in Artificial Intelligence. PMLR. 2020, pp. 111-120.
[37] Bradly C Stadie, Sergey Levine, and Pieter Abbeel. "Incentivizing exploration in reinforcement learning with deep predictive models". In: arXiv preprint arXiv:1507.00814 (2015).
[38] Alexander L Strehl and Michael L Littman. "An analysis of model-based interval estimation for Markov decision processes". In: Journal of Computer and System Sciences 74.8 (2008), pp. 1339-1331)
[39] Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press. 2018.
[40] John N Tsitsiklis and Benjamin Van Roy. "Optimal stopping of Markov processes: Hilbert space theory, approximation algorithmis, and an application to pricing high-dimensional financial derivatives". In: IEEE Transactions on Automatic Control 44.10 (1999), pp. 1840- 1851.
[41] ICML Workshop. Reinforcement Learning for Real Life, ICML 2021 Workshop. https / //sites. /ooggeee...///LLLLLLLLLLALLLLLL
http:/view//LAARRR.
[42] Kaiqing Zhang. Zhuoran Yang. and Tamer Başar. "Multi-agent reinforcement learning: A
selective overview of theories and algorithms". In: arXiv preprint arXiv: (2019).
[43] Zeyu Zheng, Junhyuk Oh, and Satinder Singh. "On Learning Intrinsic Rewards for Policy Gradient Methods". In: Advances in Neural Information Processing Systems (NeurIPS). 2018.
[44] Martin Zinkevich, Amy Greenwald, and Michael Littman. "Cyclic equilibria in Markov games". In: Advances in Neural Information Processing Systems 18 (2006), p. 1641
[45] Haosheng Zou et al. "Reward shaping via meta-learning".. In: arxiv preprint arXiv: /9tr:iiv:99..... 190309930 (2019).
11

---

Under review as conference paper at ICLR 2022
Appendix
Table of Contents
8 Algorithm
2
Further Implementation Details
10 Shaper Termination Times
3
11 Experimental Details
4
11.1 Environments & Preprocessing Details
4
11.2 Hyperparameter Settings
4
12 Ablation Studies
5
13 Flexibility of ROSA Accommodate different Exploration Bonus Terms L
7
14 Robustness to choices of Φ Parameters
8
15 Notation & Assumptions
9
Proof Technical Results
Additional Experiment Replacing RND Bonus Reward
28
18 Additional Experiment 2 Robustness to initialisation of
28

---

Under review as conference paper at ICLR 2022
ALGORITHM
Algorithm 2: Reinforcement Learning Optimising Shaping Algorithm ROSA
Input:
Environment F
Initial Controller policy яо with parameters OxD
Initial Shaper switch policy 82, with parameters 0 920
Initial Shaper action policy T with parameters Oz3
Randomly initialised fixed neural network ((:,))
Neural networks h (fixed) and for RND with parameter 0g.
Buffer
Number of rollouts Nr, rollout length T
Number mini-batch updates Nu. Switch cost c(-), Discount factor y, learning rate
Output: Optimised Controller policy π
T,, 02 TT, TØ. 92.
2 for n = N, do
I/ Collect rollouts
for t = I, do
Get enviromment states s, from
Sample a, from (s;) Apply action a, environment E,, and get reward rt and next state 81+1 Sample 9r from @2(s:) // Switching control
gt = then
Sample at from (st) Sample af41 from n² (8t-1)
ri = 70(8841, (241))(4))))))) o( at) // Calculate F(st, ats S1+1, Oc+1)
12
else
14
L a
Dummy values
Append (sc, ae. Gt, at Te, St41) to B
for N,, do
Sample data (st, at, 9t, of rz, rí, s(41) from B if gt then
18
Set shaped reward to r Tt rl
20
else
Set shaped reward to r rt
// Update RND
LOSSEND |1/((e)) 1(
23
9 - 0; VLOSSRND
1/ Update Shaper
4 [1h(st) 1((s)))22 // Compute L(st)
= c(-)gt
Compute Loss using (st, at, St, Ct, Te, ri, 4, se+1) using PPO loss // Section 4.2 Compute Loss using (st, ar, gt, Ti, ri 8141) using PPO loss // Section 4.2 0,2 0²
30
L
0g +- 02 a V Vosss
// Update Controller
32
Compute Loss, using (St, az, rf, s(+1) using PPO loss // Section 4
34
0x f fx a Losss
2

---

Under review as conference paper at ICLR 2022
FURTHER IMPLEMENTATION DETAILS
Details of Shaper and F (shaping reward)
Object
Description
Fixed feed forward NN that maps R + R
[512, ReLU, 512, ReLU, 512, m]
A
Discrete integer action set which is size of output of f,
i.e.,A2 of integers {1,..., m)
Fixed feed forward NN that maps Rd Rm
n2
[512, ReLU, 512, ReLU, 512, m)
Potential function @
((s, ( aa (0((:+1, ((+1) (ss ()),
F
0.95
d=Dimensionality of states; m E N tunable free parameter.
In all experiments used the above form of F as follows: state 8, is input the T2 network and the network outputs logits Pt. We softmax and sample from Pt to obtain the action a? This action is one-hot encoded. Then, the action of is multiplied with f f(s) to compute the second term of F. similar process used to compute the first term. In this way the policy of Shaper chooses the shaping reward.
10 SHAPER TERMINATION TIMES
There are various possibilities for the termination times {r2a} (recall that {T2*+1} are the times which the shaping reward is switched on using 02). One is for Shaper to determine the sequence. Another is to build construction of {72x} } that directly incorporates the information gain that a state
visit provides: let w Ω + {0. 1} be random variable with Pr(w 1) and Pr(w = 0) = -p where p EJ0, 1]. Then for any 1, 1,2.... and denote by AL can set:
L(s..) L( -1), then
(( if (wAL((rtt)) 1(s (1(72e)2); w S S.
To explain, since Ja2o are the times at which F is switched off then if F' deactivated at exactly ( < j and 1 (Staee1+t) now see that (2) terminates F when either the random variable w attains a O or when A (S(,+)))) S 0 which occurs when the exploration bonus in the current state lower than that of the previous state.
after time steps then (5 (( for any 0 <
(Sraee2) We
3

---

Under review as conference paper at ICLR 2022
EXPERIMENTAL DETAILS
11.1 ENVIRONMENTS PREPROCESSING DETAILS
The table below shows the provenance of environments used in our experiments.
Atari & Cartpole
httpss///gthuu..com//pssss/////
Maze
http://gggg.tuucoooo//tttttaaaa/ maze
Super Mario Brothers
Furthermore, we used preprocessing settings as indicated in the following table.
Setting
Value
Max frames per episode Observation concatenation
Atari Mario - 18000 Maze & Cartpole - 200 Preceding 4 observations
Observation preprocessing Observation scaling Reward (extrinsic and intrinsic) preprocessing
Standardization followed by clipping to [-5, 5]
Atari & Mario (84, 84, / Maze & Cartpole - None
Standardization followed by clipping to [-1, 1]
11.2 HYPERPARAMETER SETTINGS
In the table below we report all hyperparameters used in our experiments. Hyperparameter values in square brackets indicate ranges of values that were used for performance tuning.
Clip Gradient Norm E A
0.99
0.95
Learning rate Number of minibatches
1x10
4
Number of optimization epochs
Policy architecture
CNN (Mario/Atari) or MLP (Cartpole/Maze)
Number of parallel actors
2 (Cartpole/Maze) or 20 (Mario/Atari)
Optimization algorithm
Adam
Rollout length
128
Sticky action probability
0.25
Use Generalized Advantage Estimation
True
Coefficient of extrinsic reward
[]
Coefficient of intrinsic reward
[1, 2, 5, 10, 20, 50] 0.99
Y Probability of terminating option RND output size
[0.5. 0.75, 0.8, 0.9, 0.95] [2, 16, 32, 64, 128, 256]
4

---

Under review as conference paper at ICLR 2022
Durs
Control
Episode Return
"Origin
Optimal
Suboptimal
High Entropy
Standard Policy
Policy P1
50
150 Steps (x 1000)
200
250
(a) Ablating Switching Controls
(b) Responsiveness to Controller policies
Figure 5: Ablation Experiments
12 ABLATION STUDIES
Our reward-shhae shaping method features a mechanism to selectively pick states to which intrinsic rewards added. It also adapts its shaping rewards according Controller's learning process. In this section, we present the results of experiments in which we ablated each of these components. In partieular, we test the performance of our method in comparison switching mechanism removed. We then present the result of an experiment in which we investigated the ability our method to adapt to different behaviour Controller.
version our method with the
ABLATION STUDY 1: SWITCHING CONTROLS
Switching controls enable our method to be selective of states to which intrinsic rewards are added. This improves learnability (specifically, by reducing the computational complexity) of the learning task for Shaper as there are fewer states where it must learn the optimal intrinsic reward to add to Controller objective.
To test the effect of this feature on the performance of our method, we compared our method to modified version which Shaper must add intrinsic rewards all states. That is, for this version of our method we remove the presence of the switching control mechanism for Shaper. Figure (a) shows learning curves on the Maze environment used in the "Optimality of shaping reward" experiments in Section 6. As expected, the agent with the version of our method with switching controls learns significantly faster than the agent that uses the version our method sans the switching control mechanism. For example, it takes the agent that has switching control mechanism almost 50,000 more steps to attain an average episode return of 0.5 as compared against the agent that uses the version of our algorithm with switching controls.
This illustrates a key benefit of switching controls which is to reduce the computational burden on Shaper (as it does not need model the effects of adding intrinsic rewards in all states) which in turn leads to both faster computation of solutions and improved performance by Controller. Moreover, Maze is a relatively simple environment, expectedly the importance of the switching control is amplified in more complex environments.
ABLATION STUDY 2: ADAPTION OF OUR METHOD TO DIFFERENT CONTROL.LER POLICIES
We claimed Shaper design reward-shaping scheme that adapt its shaping reward guidance of Controller (to achieve the optimal policy) according to Controller's (RL) policy.
To test this claim, tested two versions of our agent in corridor Maze. The maze features two goal states that are equidistant from the origin, one is a suboptimal goal with a reward of 0.5 and the other is optimal goal which has reward There is also a fixed cost for each non-terminal transition. We tested this scenario with two versions of our controller: one with a standard RL Controller policy and another version in which the actions of Controller determined by high

---

Under review as conference paper at ICLR 2022
entropy policy, we call this version of Controller the high entropy controller." 6 The high entropy policy induces actions that may randomly push Controller towards the suboptimal goal. Therefore, in order to guide Controller to the optimal goal state, we expect Shaper to strongly shape the rewards of Controller guide Controller away from the suboptimal goal (and towards the optimal goal).
Figure (b) shows heatmaps of the added intrinsic reward (darker colours indicate higher intrinsic rewards) for the two versions of Controller. With the standard policy controller, the intrinsic reward is maximal in the state to the right of the origin indicating that Shaper determines that these shaping rewards are sufficient to guide Controller towards the optimal goal state. For the high entropy controller, Shaper introduces high intrinsic rewards to the origin state as well as states beneath the origin. These rewards serve to counteract the random actions taken by the high-entropy policy that lead Controller towards the suboptimal goal state. It can therefore be seen that Shaper adapts the shaping rewards according to the type of Controller seeks to guide.
Too generate this policy, artificially increased the entropy by adjusting the temperature of softmax function the policy logits.

---

Under review as conference paper at ICLR 2022
13 FLEXIBILITY OF ROSA TO ACCOMMODATE DIFFERENT EXPLORATION BONUS TERMS L
To demonstrate the robustness of our method to different choices of exploration bonus terms in Shaper's objective, we conducted an Ablation study on the L-term (c.f. Equation 1) where we replaced the RND L term with a basic count-based exploration bonus. To exemplify the high degree of flexibility, we replaced the RND with a simple exploration bonus term L(s) Countss>- for any given state E S where Count(s) refers to a simple count of the number of times the state 8 has been visited. We conducted the Ablation study in the environment in Experiment presented in Sec. We note that despite the simplicity of the count-based measure, generally the performance of both versions of ROSA is comparable and in fact the count-based variant is slightly superior to the RND version.
1.0
RCSA RND)
ROSA based)
0.8
0.6
0.4
0.2
0.0
Steps 10000)
Figure 6: Performance of ROSA compared with the exploration bonus replaced by count-base based method.

---

Under review as conference paper at ICLR 2022
14 ROBUSTNESS TO CHOICES OF & PARAMETERS
To demonstrate the robustness of different choices of weight parameters, we conducted a study with sets of randomly sampled values of weight parameters for the feed forward NN that constructs the ø function (c.f. Sec. 9).
As is shown in Fig. 7, the performance across all 3 values is very comparable demonstrating the robustness of ROSA to different values of weight parameters for the ø function.
1.0
Run
Run
0.8
Run
0.6
0.4
0.2
0.0
10000)
Figure 7: Performance of ROSA compared with different values of & parameters.
8

---

Under review as conference paper at ICLR 2022
15 NOTATION & ASSUMPTIONS
We assume that S is defined a probability space IPP and any s E S is measurable with respect to the Borel o-algebra associated with R". We denote the o-algebra of events generated by {se) by Fe C F. In what follows, we denote by (V, IIIl) any finite normed vector space and by H the set of all measurable functions.
The results of the paper are built under the following assumptions which are standard within RL and stochastic approximation methods:
Assumption The stochastic process governing the system dynamics is ergodic, that is the process is stationary and every invariant random variable of (8 is equal to constant with probability 1.
Assumption The constituent functions of the players' objectives R. F and
L2.
Assumption 3 For any positive scalar there exists scalar μe such that for all s E S and for any t N have: E [1 + |[se||]|s
S Me(1 + ||s|[]).
Assumption 4 There exists scalars C1 and ei such that for any function J satisfying [(()] S C2(1 + [||||[a) for some sealars 02 and C2 we have that: E [J+)))o = 8) B(o)) S CiC2(1 + [sx]111e2))
Assumption There exists scalars e and C such that for any s S we have that: [J(z, )) S C(1 [=]l9) for J {R, LJ.
also make the following finiteness assumption on set of switching control policies for Shaper:
Assumption 6 For any policy Be. the total number of interventions is given by K < co.
We lastly make the following assumption on which can be made true by construction:
Assumption Let n²s) be the state visitation count for given state s E S. For any E A, the function L(s, a) for any n(s) 2 .M where 0 < M S oc.
16 PROOF OF TECHNICAL RESULTS
We begin the analysis with some preliminary lemmata and definitions which are useful for proving the main results.
Definition A.1 An operator T: + V is said to be contraction w.r. norm || || there exists a constant E [0, 1[ such that for any V1, V2 V we have that:
[[V] TV2 s c - V21l-
(3)
Definition 2 A.2 An operator T V + V is non-expansive if'Vi, V/2 E V we have:
[TV] - TV S IIV V2ll-
(4)
Lemma For any f:V R. g: V - R2 we have that:
max
f(a) max g(a) NEV
S max (lf(a) - g(a)]l
(5)
aev
aEV
Proof 1 We restate the proof given in [23]:
f(a) S (a) g())l + g(a)
(6)
max AEV
f(a) max (a) - s(a))l + g(a)) I max [1/(a) g(a)ll + max g(a).
(7)
aEV
a
from Deducting wEv
from both sides of (7) yields:
max - maxg(a) < max (Iʃ(a) - g(a)] aEV
(
VEV
aeV
After reversing the roles of f and g and redoing steps (6) (7), we deduce the desired result since the RHS of (8) is unchanged.

---

Under review as conference paper at ICLR 2022
Lemma A.4 The probability transition kernel is non-expansive, that is:
PVV - PV & 1 V2ll.
Proof The result is well-known e.g. [40]. We give a proof using the Tonelli-Fubee theorem and the iterated law of expectations, we have that:
||] E [(P]) = ( [Mssssl])))) - E [ [J([s|s0]])]]] = = [1][s [>Poss| = ||
where we have used Jensen's 's inequality to generate the inequality. This completes the proof.
PROOF OF PROPOSITION
Proof 3 (Proof of Prop 1) To prove (i) of the proposition it suffices to prove that the term Ei F(e,, (tt) converges to 0 the limit as - oc. As classic potential-base reward shaping [27], central to this observation is the telescoping sum that emerges by construction of F.
First recall .. Jo). any (s, To) ES x (0.1) is given by:
20
0i ua
(s, 1o) EE
Σ
Ri(s;, + F(s ai -- di oz d
(10)
E -
3 (R(()) az) +
y a(
(11)
E =
7 ('R,(Se,
+ + Σ 7
(12)
Hence it suffices to prove that B Lie o af 8--,, of = 0.
Recall there number of time steps that elapse between Ty and Th+1, now
(s1, 02; (1)
y 10(8 - -2) + 677
t1
1'0(s,, -
T3k
-1 n ( : +..+
1+|
(+ (81+11, - 7 Mor. af) 7
7
tm
TaK-1
+..+ +
Σ
No - + 7 ran 16(5m
2 +..
(=
20
Tak-1
2 1114441,, "5, a²) - Σ
Σ
Σ
++
Fax - 0i (1 2
1=1=-
k=1
10

---

Under review as conference paper at ICLR 2022
x
SraN
(
Σ
7
7mn-- T2k-1
6( 88
k=1
th 0 r2x 0)
Φ (1 11 0,
k=1
k=1
where have used the fact that by construction of whenever T1, T2,.... and by construction ((s,0) 0) = 0 for any 8.
With this we readily deduce that U. 3. (s) Eg Ei=o? (s az)l which is measure of environment rewards only from which statement (i) cun be readily deduced.
For part (ii) we note first that it easy see that vi (su, Iu) is bounded above, indeed using the key result in the proof of part (i) and the properlies of e. we have that
20
T (80, To) =
-
76
R+
Σ
Ce (1110000 In((s))
(13)
R21
E ,x,
R+
clL,, -1 (n((s)
+ Σ f
(14)
< E x
8' (R Ln(st))
(15)
< E 2
(R (s)))
(16)
< E ET,7'
Σ
||R Lall
(17)
7/t (|| + 11
(18)
t=0
[|] + I|III),
(19)
using the triangle inequality, the definition of it and the 5). We now note that by the dominated convergence theorem we have that V(so To) ES 10,1)
of L and R (Assumption
}
x
lim 0/ 5. (so. Io)
lim E n-000
Σ
R
Σ clTe, 11-1)8 In((i)
(20)
n-000
x lim
E2
Σ xt
R+
c(Te, 1o-11))) 1o-1) + Imn(se)
(21)
700
EE,
R
c(I,, I 11
(22)
1=1
K + vi (50),
R+
cll,,
1t-
(23)
T-
121
again using the key result in the proof of (i) and Assumption 6 in the last step, after which we deduce (ii).
11

---

Under review as conference paper at ICLR 2022
Note that by (ii) we heron may consider the quantity for the Shaper expected return:
It- 1--10 12k -)
D Σ
(80, Fo) = En
R
Σ A21
clr,
(24)
PROOF OF THEOREM
Proof 4 Theorem is proved by firstly showing that when the players jointly maximise the same objective there exists fixed point equilibrium of the game when all players use Markov policies and Shaper uses switching control. The proof then proceeds by showing that the MG G admits dual representation as an MG which jointly maximise the same objective which has a stable point that can be computed by solving MDP. Thereafter, we use both results to prove the existence of a fixed point for the game as a limit point of a sequence generated by successively applying the Bellman operator test function.
Therefore, the scheme of the proof is summarised with the following steps:
1) Prove that the solution Markov Team games (that games in which both players maximise identical objectives) in which one of the players uses switching control is the limit point of sequence of Bellman operators (acting on some test function).
II) Prove that for the MG G that is there exists function B : {0, 13 - IR such that"
(z) = B=. (z) Ba' s² (z), Vz = (s, E x {0, 1), V.vi E (1,2)-
III) Prove that the MG G has dual representation as Markov Team Game which admits representation as an MDP.
PROOF PART
Our first result proves that the operator T is contraction operator. First let us recall that the switching time Tk is defined recursively Ty = inf(t > Tk-1ls; E A, Ty E Fi} where = {s e S.m E Ml (m) > 0}. To this end, we show that the following bounds holds:
Lemma 3 The Bellman operator T is a contraction, that is the following bound holds:
TT - TW'll S v v/
Proof Recall we define the Bellman operator Ty of 9 acting on a function A S N + by
TyA(s ((Tk) = max M A(S I(TH)), (1ST, 7max P sn, A [(Tx))
aEA
S'ES
(25)
what follows and for the remainder of the script, we employ the following shorthands:
Pa
Σ P(s';u,s), JES
P
[alss) (²)=)
Σ
(a.ls)) ar Og, 0z-1)
aEAA
a.EA
To prove that T is contraction, consider the three cases produced by (25), that is to say prove the following statements:
O ((2,a, 0z, a2_1) ymax Ps
(((z) at + ymax Do
Po,, (5
aEA
aEA
7 11 1l'l
ii)
- wl < 11 +
(and hence M is a contraction).
Thhis property is analogous the condition in Markov potential games [19, 26]
12

---

Under review as conference paper at ICLR 2022
| 3
(((:a) + ymax payy aed
ii)
S 7 116 - - where 21 = (00, It) S x
{0, 1}.
We begin by proving i).
Indeed, for any A and V2 E x 00, ES we have that
ai (zu a a ai-1) + tPp (s' a, + ymax P P (s',
S max lyP: (b(, Pp n. (s's (s'
aEA
S r P| - P
S 1| WlI,
again using the fact that P is non-expansive and Lemma 1.
We now prove ii) For any T E F, define by T' = inf 7/80 E A, F.). Now using the definition of M we have that for any 8, ES
(M v MT v (8,, [(T)
a2, + c(I,, II) tppss, ("ob(s,
de a2,02,0 1xxx2
-0 + c(TT.. 1--1) + tPp ( [(r')))
=7 Pr pd ((r) [(7')) ... (s,
S7 |Pb PI
S/ 11b 1l1,.
using the fact that P is non-expansive. The result can then be deduced easily by applying max on both sides.
We now prove fi). We split the proof of the statement into two cases:
Case 1:
M (88 M [(T)
(0 ymax Po s (6t,)((),(()))) <0.
(26)
We now observe the following:
M (s I(T)) (r, az o2 max P ('(s'I((T))
S max { ar, a a PPJ d'a pa [(T)), .. M (0 [(7))
ar, o
O(z,, 0² -² + max Pa I(T)
aeA
< max
7P ss is' [(T][(])))))))))) M m² ((5),
max {
07. 02 + max aEA
s. v' [(T)), Mf ((rr
+ max (0(2,, 02 max Pa V'(s ((s),[(T)) [(T)) (( ((st. aEA
- O 02 yax Pa (((()I((T)) aeA
13

---

Under review as conference paper at ICLR 2022
< max 0 af G3 a2- +yaxx Po V(', ((T), , 100 [1)1]
aEd
max { 0 02. o2 + ymax ps I()s M ((S, aEA
+ max 0 a,, ymax Ps ('(' ((0..1(1))) aeA
0(2,, 0r, (- ymax Pere v (s' aEd
I ymax aEA
[P7 PS I(T)) -P Pa
+ max 0. O.M (s. - (0(2)) a + yma Po,,
Vs (()))((TT)) }
$ P1 P
S 5711y-10 +/
where we have used the fact that for any scalars a, b, we have that |max b} max/b, s la- cl and the non-expansiveness of P.
Case 2:
MT. (bs., (7 ymax Po, v''sss ((6) 2
aEA
For this case, first recall that any E FF, -c(l,, ffr some X >0.
== ((8 ((T)) (0(z), ar, 02, + ymax Pa
aed s v (d(
S== wi (()) (0 ( a
ymax P v''s, ((5,(()))) - ((T,1--)) aed
< 0 ar a + c( 1, + yp5 pd I('')
0 c(T,, - + max Po P ('', ((T))( aEA
S Amax [P5 pa (W(5', ((7)) - -
S <7/a(s', I(7')) - ('ss,
S> 11b 4
again using the fact that non-expunsive. Hence we have succeeded showing that for any A E To we have that
M A max (+(,a) a)( +PPaA s>1AA- A (27)
aeA
Gathering the results of the three cases gives the desired result.
PROOF PART II
To prove Part II we prove the following result:
Proposition For any n TI and for any Shaper policy n²? there exists a function Ba
(0. 1) - RR such that
3 (2)
1/ 9'. .1
(2) -x Bdd B= (2), =s, E (0,1)
(28)
14

---

Under review as conference paper at ICLR 2022
where in particular the function B is given by:
)
Bal (80, Tn) Egg,n
Σ
7h
R Σ
ch.
Jt-1 )0 10aam))))
(29)
1=0
A21
for any (so, To) ESEXXX 13.
Proof Note that by the deduction of (ii) in Prop 1, immediately observe that
2/2 3 2
(50+ Iu) B= (8o, Io), V(5o, Io) E 8 {0,13.
(30)
We therefore immediately deduce fhat any two Shaper policies x² and x² the following expression
holds v( Io) E S x {0, 1):
07 (so, Io) ",, (so: Io) = BF.." (so: Io) - BT. (so:
(31)
Our aim now is to show that the following expression holds ((5 Iu) E x 10,
01 n,, (Ja, -0) x', x² (Jo, 80) BT (Jo, - (To, 80), Vi E
For the finite horizon case, the result is proven by induction the number of time steps until the end of the game. Unlike the infinite horizon case, for the finite horizon case the value function and policy have an explicit time dependence.
We consider the case of the proposition at time T - 1 that is we evaluate the value functions at the penultimate time step. In this case, have that:
E EST do (1--,,))
BIoa" m" (Ir-1,ST-I)
Σ
x(ar-1;8T-1)
R(sT-1
Σ Σ
(
k20
Σ
n
TT (Tr,
e7ES AT-EA
Σ IEA
(d11-1181-1)
R(sT-1.dT-1) +
Σ
o[l,, -11
k20j=T-1
x' Pl ( 07) bT)
Σ
Σ
ETES d'r-1Ed
Esy pldd
Σ 1
a7-1Ed
Σ x(d7=-18)-))
d'T-IEA
(32)
+
Σ
Tlor-isT-- (IT
FPES aT-IEA
Σ
dldr-issT-i)lleerdd. (IT
SPES d'T-
We observe that for any II and for any T² have that BTd sT) E ( ((T) ((r34)) ((sT,,o))
Ex Ex - moreover we have that for any
15

---

Under review as conference paper at ICLR 2022
π E and for any x²
TT)
R(st.ar) + >Σ clj.
ATEA
k20j=T
20
Σ <aTioT)
((ST, + EE Σ
d1j.1j-166
d'rEA
k20j=T
=E
Taa ST R
Σ
3T
LOTEA
a'TEA
+ E
naaT; ST)
ΣΣ
d1j,)j-1) - Σ
x'('TT3T))
ΣΣ
d1j
RrEA
k20j=T
a'TEA
k20j=T
Hence we find that
E E [ (TT-,,1118 - BT (Ir-1,
Σ
AT IEA
(33)
Σ d'T-1EA
f(dr=iirr--)Royysndd
Σ Σ Σ rrfee-isssslPPoorrrrottsssssttrs aT)
(34)
F7 EEAaaEE
Σ
Σ ΣE 100
(35)
87 ETI
Σ
(36)
-reSar-i EA arr E22
33333 T.SSTTTTEATTTAA2222
(37)
Now
Σ3
E Esy redg
(0 (38)
er 1EAaTEAR20
Σ 3
E
(39)
STES O'T A'A j-0
Eey 1dd
Σ3
Rdaraissnni1PPP5ssnnnhaaaha k200=
(40)
EE
E Σ
c (11.11-1)6
(41)
SPES a' O'T-1EAA''Te d'E
k20j=T
Egy snvdy
Σ3Σ
clT, 1 10
k20
(42)
16

---

Under review as conference paper at ICLR 2022
E Σ
c (T 1 18%
(43)
*TES R' ----IEA
k20j=T
-s
Σ
Σ
(44)
Σ EE Σ T'dd' plor--ssTw-/Porrddrrr(rrrs
(45)
STES T
=K Σ t(aT)
Σ x'(d'T) =0 0.
(46)
TTEA
d'TEA
Hence, we find that
BT SI--1, -B B (I-)1
E Esg-irdo
Σ
LTT-IEA
(47)
Σ
d'r-1EA
+7 Σ Σ
(48)
SPES aa- ErrrEAd
Σ PTSSaT TEA
(49)
= =By--indy
-
(50)
Hence, we have succeeded in proving that the expression (28) holds for T k when k
Our next goal is to prove that the expression holds for any 0 < k T.
Note that for any T O, we can write B as
BT (1o, s0) = En (T
+ Σ Σ
(51)
k20j=T-j
+y Σ
(tr (4 ST (T-(tt))
(52)
Now we consider the case when we evaluate the expression (28) for any 0 < k S T. Our inductive hypothesis is the the expression holds for some 0 < k < T, that is for any 0 < k < T we have that:
Σ
Σ
7.5" 11 8T
x(aT
ST 4T- (T
Σ
Σ
=o0--sseiiisseempoooooooooooa1a1 n² - ST (53)
ST-EES a' TT(-IIIEEA
Σ >E
Σ
(54)
ST-1ESeT-
(:0 (TT- (55)
T
17

---

Under review as conference paper at ICLR 2022
It remains to show that the expression holds for k + 1 time steps prior to the end of the horizon. The result can be obtained using the dynamic programming principle and the base case (k 11 result, indeed we have that
B (4--
(4) ( or-
E -Br--ati
Σ
T( ol
Σ
d'T aADEA
+7 Σ
oro.. 0² ST-K)
ST &ES OT (EID)EA
Σ
Σ
x'd'T Poo (IT (IT
= E (e
Σ
T(0--
((0T +
o[l 10
(T-((++)EE
Σ
Σ
+1 7
ST -T
Σ
x(dTT
+ Σ Σ
((oT-(AH), + スン0コ=T-1
a'TT-It-IEE
+7 Σ
Σ
de0 x² (T=xI (
8T ST-SESa'T-
E -
Σ
O(T-(K+))EA
Σ
Σ
+7
SSS -(+1EE)
Σ
Σ
o4 -
(56)
E Ear-
Σ
ar (MDDE
Σ
n' KoGr
a' (2T-(2
+7 Σ
Σ
ooo x, (I kk
STT HES EA
Σ
Σ
ا ( sT+)
(57)
18

---

Under review as conference paper at ICLR 2022
a, ("i,T-(++1) ( 8I-(4+)) (-++1) (o041))T--(41111 (1 (58)
d'
=Bor- (2t1)(
using the inductive hypothesis and where we have used the fact that
-xy- (k- ro
Σ Σ
Σ
T(OT-(++1): Prto-aanih.....oookoo.o.ooooooa.
ST #T (k++) EA R
(59)
Σ
n' ((T-- r-(tn)) (a' 8: ) 66
8T-KES ((+ EAd' T- =20
(60)
K Σ <(T
E 2'(d'-1))
(61)
RT-REA
d'T-LEA
via similar reasoning as before and after which which we deduce the result in the finite case.
For the infinite horizon case, must prove that there exists measurable function B 11 x 8 - R such that the following holds for any i E N and V'z ,/ E II, Vπ-;n' E IT_;; and V8 E S:
Es-P T. - -1,
(
: (z) - Eanp (B BBt/ (x)
(62)
The result is proven by contradiction.
To this end, let firstly assume 3c + O such that
EgpP (17770 ,.,
(=) Ba-p (B. B B (z)
Let us now define the following quantities for any E S and for each ागे E II and n, E II:; and E N:
T
TT (2)
((s)))((b s0) so)
II
1 Re(2).
j j=0
and
T"d
1-1
BTp (2) = Σ
((so) ( (a 80)
Σ j= 1ES
II
P(o)41885,4)
0z),
so that the quantity (s) measures the expected cumulative return until the point oc. Hence, we deduce that
(2) = (2)
T'
(2) + ())))
II
Σ
(,,5")),,)) (ST.).
1=0 8541ES
Next we observe that:
( ( - 1 ) (2) EgnP
a - B='ix²) (2)
c= EgpP
(
=, x' 3
(BT BF' (8)
= =Esup
(z) - Esnp
1
T'
+ +TT' EsprnP ((5o) (())))((a)) T s0) II Σ ((ssH))) (1,
(0. (2T:) BT BxTx((TT))
5=0 SS+TES
19

---

Under review as conference paper at ICLR 2022
T'1
- (0)))))(((0.5)))))) 50)m so) 1=0 B3-1ES
II
E P( (
(1f (ZTi) B mn? (2TT))
Considering the last expectation and coefficient and denoting the product by 8, using the fact that by the Cauchy-Schwars inequality have || BY| ||A|||| + || moreover whenever A, B are non-expansive we have that ||AX BY S + |Y hence we observe the following K S ||=i|| Σ 2y (1lvell + [[]. Since we can choose T' freety and y EJO, 16 we can choose T' to be sufficiently large so that 7 (1/vil + [[ < 1l.. This then implies that
- xxx== -
(2) (BTT² -BT
1
E EgNP
UTT
(2)
>
2
which is contradiction since we have proven that for any finite T it is the case that
EsnP 1
U. -V. (0:
5d ,=2 (z) (2)- (B7p - BT B (x2
(z) 0,
and hence we deduce the result the infinite horizon case.
PROOF OF PART III
We begin by recalling that Markov strategy is policy n² S A, - [0, which requires input only the current system state (and not the game history or the other player's 's action or strategy [22]). With this, we give formal description of the stable points of G in Markov strategies.
Definition A policy profile ft- = = E is Markov perfect equilibrium (MPE) if the (#' (a',5))
following holds Vi + j E {1,2), VR E II. (f'+*) (80. Io) 2 S {0, 1).
vi ( Io), V(so, Io) E
The MPE describes configuration policies in which no player can increase their payoff by changing (unilaterally) their policy. Crucially, it defines the stable points to which independent learners converge (if they converge all).
PROOF OF PROPOSITION
7 We do the proof by contradiction. Let (π. E arg sug B='s i (s) for any S. Let us r'Ellaa
now therefore assume that a & EGG), hence there exists some other strutegy profile = (g.
for which Controller has a profitable deviation where πे i.e. Ui x' ,x² (8) > v. _.. (8) (using the preservation of signs of integration). Prop. however implies that B x² (s)-BBa BF. (s) > which is contradiction since (Tt, g)) is maximum of B. The proof can be straightforwardly adapted to cover the case in which the deviating player is Shaper after which we deduce the desired result.
The last result completes the proof of Theorem I.
PROOF OF PROPOSITION
Proof (Proof of Prop. 2) The proof is given by establishing a contradiction. Therefore suppose and suppose that the intervention time -i > Ti is opti- mal intervention time. Construct the Player n²2 E 11 and 7² policy switching times by (To T(....,) and n²2 E II? policy by (Th TI....) respectively. Define by = inf(t > 0; = (s 1o) = (st,, To)} and sup(t;t 7(). By construction we have that
that = (/ (Tx)) <
To)
02
E R(so, aQ) +E ... 1-'B R(sm-1, am11) + - R(5 ar3-1) yM== x xta=² (s',((((()))))
20

---

Under review as conference paper at ICLR 2022
E
R( ao) +
x 1 'E R(on-1, + TM''' Fn x' [............++
U2 (8n, [m))]]
We use the following observation E' R( -1 a, + TMM 25 (sr, (8)1
I <max
{ M a2 ,²²
122 ((r)) on Ed
max
R((Tr + Exees p )n (e,
Using this we deduce that
2/2 x'
10) SE IE
Ris0, 0o) +
+ 1 E R( 11 A1 + max M= M3 x',"" 1/ "5'""" (87, ((T)), (T)))
max
R(s7,, arc) + Σ
a 8n,
10 3" (5'," (s',
on EA
e'ES
- R ao) E +'...'-''1 (() + + Top ,*2 (K [+i)]]]]]]]] = x (s,
where the first inequality is true by assumption on M. This a contradiction since x/2 is an optimal policy for Player 2. Using analogous reasoning. we deduce the same result for < after which deduce the result. Moreover, by invoking the same reasoning, we can conclude that must be the case that (To, -1,-.. Tk Tke Th++. ....).... are the optimal switching times.
PROOF OF THEOREM 2
To prove the theorem, we make use of the following result:
Theorem (Theorem 1, pg 4 in [18]) Let Es(s) be a random process that takes values in R" and given by the following:
(s) (1 -1- (()))(()))
(63)
then Es(s) converges to 0 with probability 1 under the following conditions:
i) 0 $ 1, 1, a. oc and Σ. 04 < 00
i) [ < 7 || with < 1;
tii Var L, Fi] < c(1 ||=,| for some O.
Proof 9 To prove the result, we show (i) (iii) hold. Condition (i) holds by choice of learning rate. It therefore remains to prove (ii) - (iii). We first prove (ii). For this, we consider our variant of the Q-learning update rule:
Q1t Qc(s,, a.)
a1 Te, at) max {M Qwons a) + 7max Q(5', [m, Qe(sn, 1000 a'EA
After subtracting (sts It, at) from both sides and some manipulation obtain that:
Est1(St, at)
= (1 ar(3 L,, (r)
+ te Ie, az)) max (MSS"
;( + Q(s O(s',Tn, [n) Q¹ Q0,,,, [1, In,, M
Q(STa:
d'EA
where E,(st, Jt, ax) = Qs( Ie, ar) - Q' az)
Let define by
(8 a) max Mant Q(8 Ir. Ma
0(87, a) 7max Q( [n) Qs,,s,,
21

---

Under review as conference paper at ICLR 2022
Then
Es41 11,01) = (1 ar(s,, L, (s))
4, + a0(s,, a)) (L((), a]].
(64)
We now observe that
[Te Tru a)) = Σ P(s';a, s5,) max { _MxrT(((ss Q(Suu (),,, a) ymax Q(s', Tnn
Q'(
a'EA
8'ES
[8, (n) (s, u.)
(65)
Now; using the fixed point property that implies Q" = =TOQ", , we wend that
E [L T , a) = (8Q
T (8, I Tw.
- Q1 Q=
11 1el1Q:-Q'll... llx 1
(66)
using the contraction property Tf established in Lemma 3. This proves (ii). We now prove iii), that is
Var [L|FF]] S c(1+ + 13,11))
(67)
Now by (65) we huve that
Var [i] =
Var max M Q(STL: Ines ((sT,,
a) + +max Q(s a'EA o') (
E
max MM Q( Ixx ((522 a) + rmxx Q(s', Ire
d'EA
- Q" (s, (ra ) T,, a')
a)
ToQi(s (T) 27
E
max Mr. Q( T a), 26 (8 s + ymax Q(s',
a'EA
Var max (M Q(8 a), a)
ymax Q(s' Q(S'.Tru a') ToQi(s, (a)
a'EA
c(1 + ||E,
for some where the last line follows due to the boundedness of Q (which follows from Assumptions 2 and 4). This concludes the proof of the Theorem.
PROOF OF CONVERGENCE WITH LINEAR FUNCTION APPROXIMATION
First let recall the statement of the theorem:
Theorem ROSA converges limit point r* which the unique solution to the equation:
(T((r=*) xbr*
a.e.
(68)
where we recall that for any test function A E V, the operator & is defined by 3A = θ P MA,
Moreover, r* satisfies the following:
Q'1 S c =IIIII - Q+
(69)
The theorem is proven using a set of results that we now establish. To this end, we first wish to prove the following bound:
22

---

Under review as conference paper at ICLR 2022
Lemma For any Q E V we have that
| - - - -
(70)
so that the operator 8 is a contraction.
Proof 10 Recall, for any test function v projection operator II acting A is defined by the following
IIA
arg min AE(brIrER*)
||A A
Now, we first note that in the proof of Lemma 3, we deduced that for any A E L2 we have that
|MA ((:aa) + ymax PnA|
5 AlI.
(c.f. Lemma 3).
Setting A Q and vp O, it can be straightforwardly deduced that for any Q E L2 [MQ (1Q-QQ)
- S Q @1. Hence, using the contraction property of M, we readily deduce
the following bound:
- lilee-@llllmee--mq s 5- =61
max
(71)
We now observe that 8 is a contraction. Indeed, since for any Q Q' E Lo we have that:
||QQ - SQ'1l = ||0 + 7P Q} - (0 + >P [MQ' 2'
= > || max[MQQ Q} - P mmx(
S y ||max{MQ, Q} - max(MQ) Q'1ll
S y |lmax|[MQ - MM', Q MQ', MQ', Q',Q
S 7 max MM'Il 10''I,110 11Q - MQ'II IMQ - 1211,
> IIQ - Q'Il.
using (71) and again using the non- non-expansiveness of
We next show that the following two bounds hold:
Lemma
For any Q V we have that
i)
[IQQ n s s 11Q @l|.
ii) 1 VIーz IIQQ* - Q*
Proof 11
The first result is straightforward since TI is a projection it is non-expansive and hence:
[B3Q n || $Q < < |
using the contraction property of 3. This proves i). For ii), we note that by the orthogonality property of projections we have that (dr- 11Q" 2r* - -1QQ"), hence we observe that:
|0r Q+11² = ||+r* - IIQ" 1| + |r 11
|| - I| 2 - |r IIQ" 1
< 1| Q*11² + |r> -1Q*11
= 13br* - 3Q'12 + | - 11Q"11
S Sn² ||r 2-1 + | -TQ
after which readily deduce the desired result.
23

---

Under review as conference paper at ICLR 2022
[MQ(z), MM()=) > 2r*, [Q(z),
Lemma 6 Define the operator H by the following: HQ(2)
otherwise,
and &s by: TQ == θ +H.H
For any Q, Q L2 have that
iQ अQ 1 -Q]
(72)
and hence & is a contraction mapping.
Proof 12 Using (71), we now observe that
3Q - 3Q = 1 -
7 HQ- - HQQ1
$ max {MQ .MQ.Q NM2.QQQ.M - -000--0.M-Q..MG. -Q1
max {lllQ -M@l
- - wwm 111.11-@--0 Q
ymax {-|1Q- @11
- Q11 1 Q11
7 11-2-11
again using the non-expansive property of P.
Lemma Define by Q == θ + Po where
* (2) == e (STL, a) + +yaax
Σ
P(s':a, Sr, (rr (I(()))
(73)
aEA
s'ES
then Q is a fixed point of 3Q, that is TQ = Q
Proof 13 We begin by observing that
HQ(=)) H (0(=) + 7Po²)
[MQ(2), (fMQ(=) > tr*
(Q(2). otherwise,
(MQ(=), ifM)(=) > Tr* (0(2) +7Pb", otherwise, (2)..
Hence,
- # = Q
(74)
which proves the result.
Lemma The following bound holds:
1 (20) - [200] 2
(20)
(1-10 -Q'I-
(75)
Proof 14 By definitions u* * and x (c.f (73)) and using Jensen's 's inequality and the stationarity property we have that,
E 1 (20)
- E | (zo)
= E P (20) - E P (zu)
$ E Pr * (20)
- E P (zo)]
< p * p $
(76)
Now recall that Q = θ - P and Q* = + 7 P using these expressions (76) we find that
_ 2 2-0rl1
* (zo)
E 1 (=n)
7
24

---

Under review as conference paper at ICLR 2022
Moreover, by the triangle inequality and using the fact that (((r") = -((rr)) and that 3Q = Q" and $Q = Q (c.f. (75)) we have that
0 - @
0 3(
+ 0 3( )
+ + 0|0- Φr
s 2 1 //
+ Q- @11
which gives the following bound:
Q 1 s <(1-))
1 4/
from which, using Lemma 5, we deduce that after which by (77), we we finally obtain
0 -0- 2 (1 7) 7) - -2)
E [zo)] - EE 1 (20) <2 (1- 10 Q-
as required.
Let us rewrite the update in the following way:
T++1 + ((),
where the function =: 2d x RP + IP is given by:
E(w,r) < (0(z) + 7 max (()) ((r)))))
- (#r)
for any w (z,2') E (N x 2)² where st E N x S and x' (t,s') E N x S and for any
r E R Let us also define the function E R + R by the following:
(rr) == Ewo [ww r) wi == (20, z1).
Lemma The following statements hold for all E (0,1) x S:
i) (r=r*)=x(r)) <0
Vr *r
i) Bx(r)==
Proof 15 To prove the statement, we first note that each component of [x(r) admits representation as an inner product, indeed:
Ex(r) = E (2) (2)) + max (4)(()) ((r))())) (2))(
E [ox (20) (O(2)) + >E [max (fr(2)). [20] (2r)
= E [ox (2 (9(2))
+ 7 mmxx ((br (2o) - (#r)
(dk, h Tr))
using the iterated law of expectations and the definitions of P and T. We now are in position to prove i). Indeed, we now observe the following:
(r-r))E(()) Σ (r(1) - (1) (dr, F0r - -br)
1=1
(or tr* Brr :br)
(or Φr (1 Tr + 11 $r)
(or xr* 113 Φr),
where in the last step we used the orthogonality of (1 II). We now recall that 18br tr* since tD* is a fixed point 1I3. Additionally, using Lemma 5 we observe that |[ 0r*11= S
r/l fo Trr With this now find that
(br tr 1g TD))
25

---

Under review as conference paper at ICLR 2022
= (or Dr", (Tg - 0r**) )- + DD - -br)
S (r Trr IT Tr || 1rll
S (7 - 1) | 2rll2
which is negative since y which completes the proof of part The proof of part ii) is straightforward since we readily observe that
Ex(r*) = (dr, 30r - -br) = (Ør, 1134r" - -r) = 0,
as required and from which we deduce the result.
To prove the theorem, we make use of a special case of the following result:
Theorem (Th. 17, p. 239 in [3]) Consider a stochastic process Ti RR x foo] x 1 + R which
takes initial value and evolves according the following:
T++1 + a3(st,
(77)
for some function 122d x IR E* and where the following statements hold:
1. {s,ft 0, ...) is stationary, ergodic Markov process taking values in 12dd
2. For any positive scalar 9. there exists scalar My such that E [1 + || spl 1
Mg (1+1) [|+1))
3. The step size sequence satisfies the Robbins-Monro conditions, that is Σt= do and
Ei= ot < oo
4. There exists scalars e and q such that [|3(w, r) S c1 + ( (1 + ||rl])
5. There exists scalars and q such that E
IE E Wt, r 200 2] E ((wo, S
c c(1 + [|=]]9) (1 [r]]]
6. There exists a scalar e > 0 such that ||E|E (wo, r)] - E| f)ll| S c||r Fl
7. There exists
scalars
c
0 and 4
>
such that
Er || [[w,, (wo w] E [ (wo. F)]ll cllr
Fll (1 ||w||9)
8. There exists some r" IR such that (r --) < 0 for all # r* and 3(r*) = O.
Then Ti converges to r* almost surely.
In order to apply the Theorem 4, we show that conditions are satisfied.
Proof 16 Conditions 1-2 are true by assumption while condition 3 can be made true by choice of the learning rates. Therefore remains verify conditions 4-7 are met.
To prove 4, we observe that
[5 r)ll = [1Ø(z) (0(z) + max (()))) (+r)
< (11) +M [[0(z)] |r||
< [|)())] (100=))) (=))I)) [|((=)] (<=((()))| + [++())))) ||]]]-
Now using the definition of M, we readily observe that | [| < ||l|| +?|1+ 인1| < ||||| T| using the non-expansiveness of P.
Hence, we lastly deduce that
[[(w, r)ll < [[)(=)) (I[(())I + [|0(=) (102))))++ ||]] $ [|)(2)|| (I((2))I >>|@||++ [[(())] + [I)()) [rll
then easily deduce the resudt using the boundedness &. O and vb.
26

---

Under review as conference paper at ICLR 2022
Now we observe the following Lipschitz condition on E:
[[ r) [ww, F)
(=)(2) (y max ((r)(22).
max ((t)))
((fr)()) +r(2))
I < [[((=)] ||max (o'( M (z')) - max ((0 (0)) > =
||ő(=)]] (Ilo(=)] ( (x' o'(='Il) ||r
$ -e|rr-fl,
using Schwhy-Schwarz inequality and that for any scalars a,b we have that Imax(a, b) - ma c}1
la c.
Using Assumptions and 4, we therefore deduce that
[B r) E(w, wWwo w| -E E(w,, r) -((w, F)ll S ||r Fll (1 + [| (78)
t=0
Part 2 is assured by Lemma 5 while Part 4 is assured by Lemma 8 and lastly Part 8 is assured by Lemma 9.
27

---

(the function Under review as conference paper at ICLR 2022
1.0
ROSA (L RND)
ROSA (L Count-based)
0.8
0.6
Return
0.4
0.2
0.0
2
4
8
10
Steps (x 10000)
Figure 8: ROSA is robust to the component used to generate exploration bonus L. ROSA works equally well when RND Count-based method forL.
Rebuttal
17 ADDITIONAL EXPERIMENT 1 REPLACING RND FOR BONUS REWARD
In this experiment we sought to ascertain if ROSA is robust the component used to generate exploration bonus L. We ran two versions of ROSA, one where L is computed using RND and one where L is computed using simple count-based measure Count(s) where
Count(s) simply tallies the number of times state has been visited). Figure 8 shows performance of these two versions of ROSA on the Maze environment shown in Figure 1. ROSA performs equally well with both components, indicating that it is not dependent on fine-tuned exploration bonus. The additional machinery switching controls and choices of intrinsic rewards add mean that ROSA can work with basic exploration bonuses. Note that we generally use RND since it is simple to implement and works equally well on discrete and continuous state spaces.
18 ADDITIONAL EXPERIMENT 2 ROBUSTNESS TO INITIALISATION OF Ó
Some reviewers raised important questions about the requirement of a carefully initialised phu function. Here, we show performance of individual runs of ROSA on the Maze shown in Figure 1. In each run, ó is randomly initialised using Xavier initialisation, and as a consequence ROSA works with different ó function in each run. As can be seen in Figure 9, despite the randomness in the performance of ROSA does not vary significantly over the runs. This suggests that ROSA can adapt to the function it is presented with, and still come up with good reward shaping.
28

---

Under review as conference paper at ICLR 2022
1.0
Run
Run
0.8
Run 2
0.6
Return
0.4
0.2
0.0
2
4
8
10
Steps (x 10000)
Figure 9: ROSA is robust to the component used to generate exploration bonus L. ROSA works equally well when RND Count-based method forL.
29


Reviews:
[{"review_id": "RX6Cge3Ly7L", "reviewer": "Reviewer_g7fZ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "This paper aims to tackle an important problem in RL and does a good job of conducting some experiments to show what the method learns. However, there are some significant concerns with the paper. The first is a lack of clarity in the presentation of the method and problem setup. The second is that it is unclear where or if any benefit is coming from the proposed method. The issues are expanded below. \n\n\n\nClarity: \nThe paper’s clarity can be improved by being more precise in writing and avoiding redundant arguments. \n\nThe first thing to fix is to make sure every term and symbol has a definition before it is used. In section, when an expression for F is given, phi is used, but it is unclear what phi is required to be. This creates confusion later Section 3 third paragraph, where F hat uses some phi hat, and \\theta^\\star is supposed to make \\hat \\phi equal to \\phi. \\theta^\\star is often used to indicate optimal weights, but it is not clear what optimal is because phi is undefined. It is said that \\theta^* is supposed to yield a useful shaping reward, but it is unclear what that means. Without proper definitions, it is not easy to understand the proper motivation and reason about whether the method accomplishes the stated goals. \n\nThere are also many redundant arguments made throughout the paper. For example, at the start of the third paragraph in Section 3, an argument is given that was discussed several times above. \n\n\nAt the start of Section 4, further discussion is given about the goal/objective for each learner, but they are both not provided until later. This lack of specificity is frustrating as a reader because all statements given so far have been vague and the exact relationship of the two algorithms continues to go misunderstood. Also, for both objective functions, it is specified that each learner needs to maximize a value function at some given state, but this is not a proper objective function because a distribution or weighting over states is not given. \n\nMethod benefits:\nThe stated objective is to tackle the problem of sparse and uninformative rewards through autonomously learning a reward function. Additionally, it is said that the “…shaping rewards supplement the environment reward and promote effective learning, our framework therefore addresses the key challenges in RS”. One issue with this claim is that learning of the shaping rewards cannot be more efficient than just learning about the reward function of the environment, i.e., what makes a good reward function can only be learned once the agent has already learned what the good behavior is. Thus, it seems unlikely that this method could be doing anything more effective than encouraging exploration. This brings up another issue, in that it is unclear what components of the method are necessary or helpful in solving sparse reward problems. The experiments demonstrate some learned behavior, but they do not clearly show how each component helps the algorithm change the learning dynamics, so sparse reward problems are manageable. These experiments are an essential step in proposing new methods so other researchers can build off the knowledge generated in a paper to solve new and different problems. \n", "summary_of_the_paper": "This paper introduces a new algorithm to solve the sparse reward settings. The algorithm tries to find an optimal policy by leveraging two learners: a controller and a shaper. The controller learns to maximize the environment reward signal plus the signal provided by the shaper. The shaper learns a potential-based reward shaping function by maximizing the controller's objective plus a cost penalty for providing reward feedback and an exploration bonus. The shapers reward function is created using a randomly generated state function and a dot product based on the shaper's \"action.\" Some theoretical analysis is provided along with experiments demonstrate to demonstrate that this algorithm is helping solve sparse reward problems. \n", "summary_of_the_review": "This paper lacks proper justification for the design choices of the presented method and is thus not ready for acceptance. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "PiGwIkeGFN5", "reviewer": "Reviewer_sEbz", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The idea of jointly training an agent to assist the controller is relevant to the RL community and new (to my knowledge). In my mind, the primary insight is to connect reward shaping to Markov games. The theoretical results built off [25] appear to support the methodology and experiments suggest ROSA works well and is robust (up to the points below). I appreciate that the authors attempted to show the method performs well in various task contexts, e.g., for subgoal discovery. \n\nOn the downside, there are several aspects of the work which are unclear to me and several claims are not well established by the theory nor the experiments:\n\n- the paper claims that ROSA's concurrent learning leads to \"a faster, more efficient procedure\" compared to [15,34]. Can the authors provide additional theoretical or experimental justification for this claim? \n- Sec 4.1. on the switching controls can be better explained; I don't understand the definition for the switch being $I_{\\tau_{k+1}} = 1 - I_{\\tau_k}$; the switch is flipped after each step? This seems at odds with the later explanations about the switching behavior. Looking at the main events, the switch is decided upon at each step?  \n- Sec 4.2. The role of the bonus reward L remains rather opaque to me. Perhaps I missed it but I didn't see any experiments studying its effect. Perhaps the authors can clarify?\n- Sec 5. It is unclear what $v_1^{\\pi, \\pi^2}$ means. In Sec. 4, it is defined as the objective for controller, incorporating both the extrinsic and intrinsic rewards. However, in Proposition 3, it appears to denote extrinsic expected return. Likewise, the corresponding proof (Proof 7) doesn’t explicitly write out $v_1^{\\pi, \\pi^2}$. \n- Sec 6. Key details on the experimental settings are missing, especially the number of runs. It is well-known that RL performance can vary significantly between random initializations. How does the incorporation of Shaper affect this variance? I appreciate space is tight so perhaps this can be put in the supplementary. \n- Sec 3. \"Red-herrings\"; I'm puzzled as to how Shaper learns to do this since there is a bonus for exploration (L). The mechanism by which the exploration/exploitation trade-off is resolved is not apparent to me from reading the paper. \n\n## Minor comments \n- Sec 4: \"RIGA\" should be \"ROSA\"\n- Sec 5: \"The result is established by a careful adaptation of the policy invariance result in [25] ....\" is repeated after Corollary 1. \n", "summary_of_the_paper": "The key idea in this paper is to jointly train a pair of agents, namely a Controller that performs the RL task and a Shaper agent that shapes the Controller's reward function to better its performance. Rather than shape all states, Shaper learns \"switching controls\" to determine states on which to place its modeling effort on, and ablation experiments suggest this works well compared to the straightforward approach of shaping all states. A natural concern is whether this Markov game approach results in stable training and convergence. To address this issue, the authors provide theoretical convergence results which show ROSA convergences to a Nash Equilibrium (NE) with weakly higher total return. Experiments on several domains suggest the method works well relative to alternative reward shaping approaches (e.g., those based on curiosity or bi-level optimization). ", "summary_of_the_review": "The paper makes interesting contributions, but the clarity could be improved. At this point, my score is a reflection of my uncertainty about the above issues. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "O_MIDZOobdS", "reviewer": "Reviewer_uREp", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "# Strengths\n\nThis paper proposes an interesting and (as far as I know) novel approach to learning how to shape rewards. The idea of training an agent to output actions that modulate a potential-based reward is quite interesting, since this Shaper agent can use heuristic metrics (e.g. the RND bonus) to guide exploration while preserving the Controller agent’s final performance thanks to the extended policy invariance results. As the paper notes, this multi-agent approach could lead to interesting new solutions for RL. The experiments in the paper compare against appropriate baselines and demonstrate promising results. The visualizations are useful, and overall the paper is easy to follow.\n\n# Weaknesses\n\nOne concern with the paper is that it is the combination of many heuristic components (e.g. how L is chosen, how c is chosen, how I is chosen, and how phi is chosen). This runs a bit counter to the author’s motivation to avoid manually engineering components. I understand that part of the paper is demonstrating that despite these heuristics, the Controller policy is still optimizing the correct objective, but these additional design choices may result in a method that is overall rather brittle and sensitive to the design choices, even if the Controller is *theoretically* optimizing the right objective. Demonstrating that the method still performs well when L, c, I, and/or phi is altered would provide evidence for the generality of this approach.\n\nThe other main weaknesses of the paper come in the writing and experiments, which I detail below.\n\n## Writing:\nOne major concern is that the main paper does not describe how phi is chosen. This decision is critical to the success of the paper, and I could not find much in the paper other than a hypothetical description (“φ can be, for example, a neural network with fixed weights with input (s, a2)”).\n\nThe authors claim that there are two advantages over past work: (1) learning the reward shaping term concurrently as opposed to iteratively and (2) avoiding the computational cost of computing the reward at every state. The second concern seems rather minor. For the first claim, the authors do not provide evidence that, “ROSA performs these operations concurrently leading to a faster, more efficient procedure.” It would help to evaluate these methods as a comparison. Without this comparison, the difference between updating the other networks concurrently vs iteratively seems superficial (e.g., can’t you just run the prior methods with a faster iteration loop)?\n\nThere are also other claims that seem unsubstantiated. For example:\n\n“it ensures that the information-gain from Shaper encouraging Controller to explore a given set of states is sufficiently high to merit activating the stream of rewards”\nIs there evidence or proof of information being maximized by the Shaper?\n\n“Controller’s rewards only at states that are important for guiding Controller to its optimal policy.\nThis enables Shaper to quickly determine its policy π2 and how to choose the values of F unlike Controller whose policy must learned for all states”\nWhy does this enable the Shaper to quickly determine its policy? Is there evidence of this?\n\n\n## Experiments\nOne limitation of the experiments is that the method is only applied to a relatively easy robot environment and a limited number of video game domains. In particular, on Solaris and Super Mario, most of the learning happens within the first few time steps, suggesting that exploration is not a big challenge in these domains. Although the authors do demonstrate that the other methods have some instability issues, it would be great to test the environment on more domains where the bottleneck is clearly exploration.\n\nIt would be great to compare to [3,4] since, as the authors say, these are “closest to our work”. Although I understand that [3] requires a shaping reward to begin with, ROSA also assumes access to a bonus (through L(s)), and so comparing to [3] with the same RND bonus seems like a fair comparison.\n\n\n## Minor comments\n\nThe statement “Unlike [15] which requires a useful shaping reward to begin with” seems unfair since the whole point of [15] is that you can learn when to ignore a non-useful shaping reward.\n\n“ Moreover, in [15,34], the agent’s policy and shaping rewards are learned with consecutive updates. In contrast, ROSA performs these operations concurrently leading to a faster, more efficient procedure.”\nAs written, the difference sounds rather superficial because it’s relatively simple to run [15, 34] concurrently. Do the authors mean to highlight the difference between a bi-level optimization and having a separate Shaper policy that can generate on-the-fly actions?\n\nIn Figure 1, why does your method start off better at steps=0 than RND and count-Based ICM? Shouldn’t they start at the same performance?\nCould the authors report normalized returns, which I believe is more standard for Atari?\n\n“Another issue is that using an optimisation procedure to find θ directly does not make use of information generated by intermediate state-action-reward tuples of the RL problem which can help to guide the optimisation”\nI’m not sure what problem is being highlighted here. Are you saying that trying to optimzie theta without using any samples is a bad idea? While I agree, it’s unclear why anyone would do this.\n\n“Now the problem is to find θ...such that F(st+1, st) = \\hat F(st+1, st; θ)”\nWhat is F? Is it just any “useful shaping-reward function F” or is it a specific F?\n\n“these methods provide no performance guarantees nor do they ensure the optimal policy (of the underlying MDP) is preserved”\nSome curiosity-based reward shaping methods provide guarantees (though “curiosity” is a bit ambiguous of a category). See [1,2] \n\n\n## typos/low-level:\n- during training. [16].\n- Moreover, they naively reward exploration to unvisited states without consideration of the environment reward\n- when Shaper influences Controller) \n- Figure legends and axes labels are very small and hard to read\n[1] Hazan, Elad, et al. \"Provably efficient maximum entropy exploration.\" International Conference on Machine Learning. PMLR, 2019.\n[2] Misra, Dipendra, et al. \"Kinematic state abstraction and provably efficient rich-observation reinforcement learning.\" International conference on machine learning. PMLR, 2020.\n[3]  Yujing Hu et al. “Learning to Utilize Shaping Rewards: A New Approach of Reward Shaping”. In: Advances in Neural Information Processing Systems 33 (2020).\n[4] Bradly Stadie, Lunjun Zhang, and Jimmy Ba. “Learning Intrinsic Rewards as a Bi-Level\nOptimization Problem”. In: Conference on Uncertainty in Artificial Intelligence. PMLR. 2020,\npp. 111–120.", "summary_of_the_paper": "The authors propose ROSA, a reward shaping method that trains a separate “Shaper” policy to learn how to generate reward bonuses. The problem is formulated as a two-player Markov game, in which the environment dynamics are only affected by the primary, “Controller” policy, but the Shaper and Controller policies each optimize their own rewards. The Controller’s reward is the normal reward plus a potential-based reward that depends on the previous two states and the previous two Shaper actions. The shapers’ reward is a combination of the Controller’s reward, a penalty for switching often, and a count-based exploration bonus. The shaper’s rewards are also automatically gated by a switching function, which is hard-coded to switch with higher probability whenever a curiosity-metric increases (in this case using the RND exploration metric). The authors extend the standard reward shaping result to show that including the actions of the Shaper in the potential-based reward shaping term maintains policy invariance. Then, the authors empirically demonstrate on a grid-world environment that ROSA provides useful reward shaping that guides the agent towards the goal and ignores irrelevant parts of the state space. The authors also compare to and find that ROSA outperforms ICM, RND, PPO, and LIRPG on Gravitar, and gets similar performance on Solaris and Super Mario as some of these prior works.", "summary_of_the_review": "The paper presents an interesting idea and has some promising results. However, there are a number of clarity issues (including lack of details on an important design), claims that seem unsupported, and limitations in the experiment (in particular, not comparing to certain baselines and evaluating on tasks that may not be challenging enough) that make me currently believe that the paper is not ready.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NrgD5ykt70P", "reviewer": "Reviewer_XHiG", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths\n------------\n-Framing reward shaping within the Markov game (MG) framework is novel\n\n-Some theoretical guarantees are provided, in particular Proposition 1\n\nWeaknesses\n------------------\n-The presentation and clarity of the paper is lacking\n\n-Many low level choices are brushed upon and hardly motivated\n\n-Empirical improvements are quite limited and the code is not provided\n\n\nDetails\n---------\nPresenting a solution to the potential function in PBRS is an important contribution as it is still to this day an open problem. Moreover, most of the research on PBRS has not used neural networks and therefore can be seen as limited. As such, framing the method as a Markov game is an interesting avenue. That being said, the paper does a poor job at presenting clearly the ideas, motivations, limitations as well as some related work. For example, the idea of introducing switching controls can by itself be an interesting idea, but is completely orthogonal to framing the method as a two player MG. Yet the method that the authors present ties the two concepts together. Around the idea of switching is the claim that since the method only learns to shape rewards at relevant states, it is more computational efficient. First, is the proposed method, in practice, really learning what are the relevant states? Second, wouldn't be the computational cost be equivalent if one first has to learn on what states to perform reward shaping? I would argue that the computational cost even greater since both elements need to work together (reward shaping and switching controls), unless a more trivial solution is proposed, as in the paper. Given these considerations, I would be much more careful about the kind of claims being made.\n\nThe idea of two player MG can be an interesting avenue, but I am wondering if the fact that only the Controller affects the dynamics, is it really relevant to talk a two player game? In the end, the Controller is a network that is simply using reward shaping, while the Shaper is separate network that learns how to shape the rewards. What does framing the setup as a two player game bring in terms of insights/methods/solutions? This kind of questions is not really addressed in the paper.\n\nThe presentation of the method has a structure that doesn't help clarity where many of the details are only later presented and are not really motivated. The presentation itself is interleaved with claims that hinders clarity and bring more questions, such as first paragraph of 4.2 where claims about the effect of the switching cost are made. The idea of termination times is presented quickly but most of the details are in the appendix, which again hinders a nice and clean presentation. The final algorithm makes choices such as adding an exploration bonus to the Shaper or using a fixed network f(s) for the potential function. Especially with respect to the latter point, why would it make any sense to have a random network output the value for reward shaping? The algorithm also mentions that $a^2_{\\tau_k} =0 \\forall k$, but then it also mentions that when $g(s_t)=1$ we sample from the Shaper's policy? Why are such choices being made? Is it to make sure that the theoretical derivation work out, such as in Proposition 1? How does it help in practice? \n\nFinally, related work is missing.The paper claims that \"In RS the question of which φ to insert has not been addressed.\" This is simply false. There is recent and relevant work on this such as (Klissarov et al. 2020), as well as more classic work such as (Brys et al., 2015, Grzes and Kudenko 2010). These references should be included in the paper given their close conenction and the claims adjusted. Moreover, there is many landmark papers on curiosity that are missing, such as  (Schmidhuber 2010,  Oudeyer et al. 2007)\n\nJ. Schmidhuber. Formal theory of creativity, fun, and intrinsic motivation (1990–2010)\n\nBrys et al. 2015, Reinforcement learning from demonstration through shaping\n\nGrzes and Kudenko 2010,  Online learning of shaping rewards in reinforcement learning\n\nKlissarov et al. 2020, Reward propagation using graph convolutional networks\n\nOudeyer et al. 2007, What is intrinsic motivation? A typology of computational approaches\n\n", "summary_of_the_paper": "The paper proposes to frame the reward shaping method as a Markov game between two players. In this setting the first player is learning to act in the environment while the second player is learning to provide reward shaping to the first player. Additionally, the authors propose to use a switching scheme that indicates whether or not to perform reward shaping for the first player. The authors provide some theoretical guarantees under a large set of assumptions. The authors perform experiments on a set of toy tasks and a few more complex domains.", "summary_of_the_review": "The paper proposes an original way to frame reward shaping. However, the presentation is lacking clarity and many of the choices/details are not well motivated. Despite my negative review I think there is potential in the approach, but I believe that a major rewriting is necessary as well as more qualitative empirical analysis. The quantitive empirical results are not especially favourable either.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper tackled the reward shaping problem under the framework of Markov games. The authors proposed reward shaping algorithms for RL with mild theoretical guarantees. The AC agrees with the reviewers that the empirical performance is ambiguous. The paper should be substantially improved before being accepted.
Decision: Reject