Year: 2021

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 Optimising 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 shapingreward 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.

heading: 1 INTRODUCTION
text: 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 a variety domains [8, 31, 35, 24], enabling RL algorithms to learn successfully in numerous real-world tasks remains a challenge [41]. A key obstacle to the success of RL algorithms is the requirement of a 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 of 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 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 no 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) is a tool to introduce intrinsic rewards known as shaping rewards that supplement environment reward signals. These rewards can encourage exploration 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 domainspecific shaping functions whose construction is 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 an 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 to solve its task. This generates tailored shaping rewards without the
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 a 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-reward function while Controller learns its optimal policy, Shaper learns to adaptively facilitate Controller’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 a 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 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 a 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 an 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 a 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 problem. This ensures Shaper learns a shaping-reward function that improves Controller’s performance and that Controller learns the optimal value function for the task.

heading: 2 RELATED WORK
text: 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 a shaping function of the form F (st+1, st) = γφ(st+1) − φ(st) 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-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 an RS method that adds a shaping-reward function prior which fits a distribution from data 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 is being learned the reward can be corrupted by inappropriate signals that hinder learning. 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 to use state visitation counts [29]. More elaborate approaches such as [6] introduce a measure of state novelty using the prediction error of features of the visited states from a random network. [30] use the prediction error of the next state from a learned dynamics model and [15] maximise the information gain about the agent’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 a useful shaping reward to begin with, ROSA constructs
a shaping reward function from scratch leading to a fully autonomous method. Moreover, in [16, 36], 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. 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 shapingreward function F , uses a similar form as PBRS. However in ROSA, F is augmented to include the actions of another RL agent to learn the shaping rewards online. Lastly, unlike curiosity-based methods e.g., [6, 30], our method preserves the agent’s optimal policy for the task (see Experiment 3, §6) and introduces intrinsic rewards that promote complex learning behaviour (see Experiment 1, §6) .

heading: 3 PRELIMINARIES & NOTATIONS
text: 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 : S ×A×S → [0, 1] is a transition probability function describing the system’s dynamics, R : S ×A → R is the reward function measuring the agent’s performance, and the factor γ ∈ [0, 1) specifies the degree to which the agent’s rewards are discounted over time [39]. At time t the system is in state st ∈ S and the agent must choose an action at ∈ A which transitions the system to a new state st+1 ∼ P (·|st, at) and produces a reward R(st, at). A policy π : S × A → [0, 1] is a probability distribution over state-action pairs where π(a|s) represents the probability of selecting action a ∈ A in state s ∈ S. The goal of an RL agent is to find a policy π? ∈ Π that maximises its expected returns given by the value function: vπ(s) = E[ ∑∞ t=0 γ
tR(st, at)|at ∼ π(·|st)] where Π is the agent’s policy set. We denote this MDP by M.
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 rewards and the system dynamics are now influenced by the actions of both agents. Therefore, each agent i ∈ {1, 2} has its reward function Ri : S ×A1 ×A2 → R and action set Ai and its goal is to maximise its own expected returns. The system dynamics, now influenced by both agents, are described by a transition probability P : S × A1 × A2 × 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 θ ∈ Rm: F̂ (st+1, st;θ) := γφ̂(st+1,θ)− φ̂(st,θ). Now the problem is to find θ? ∈ Rm for φ(s) = φ̂(s,θ?) such that F (st+1, st) = F̂ (st+1, st;θ?), i.e., we aim to find θ? that yields a useful shaping-reward function. Determining this function is a 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 θ? 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.

heading: 4 OUR FRAMEWORK
text: We now describe the problem setting, details of our framework, and how it learns the shaping-reward function. We then describe Controller’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-reward at each state. Simultaneously, Controller performs actions to maximise its rewards using its own policy. Crucially, the two agents tackle distinct but complementary set problems. The problem for Controller is to learn to solve the
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:
vπ,π 2
1 (s) = E [ ∞∑ t=0 γt ( R(st, at) + F̂ (st, a 2 t , st−1, a 2 t−1) ) ∣∣∣s = s0] , where a ∼ π is Controller’s action, F̂ is the shaping-reward function which is given by F̂ (·) ≡ φ(st, a 2 t ) − γ−1φ(st−1, a2t−1) for any st, st−1 ∈ S and a2t ∼ π2 is chosen by Shaper (and a2t ≡ 0,∀t < 0) using the policy π2 : S × A2 → [0, 1] where A2 ⊂ Rp is the action set for Shaper. The function φ : S ×A2 → R is a continuous map that satisfies the condition φ(s, 0) ≡ 0 for any s ∈ S (φ can be, for example, a neural network with fixed weights with input (s, a2),A2 can be for example a set of integers {1, . . . ,K}). Therefore, Shaper determines the output of F̂ (which it does through its choice of a2t ). With this, Shaper constructs a shaping-reward function which is tailored for the specific setting. The transition probability P : S×A×S → [0, 1] takes the state and only Controller’s actions as inputs. Formally, the MG is defined by a tuple G = 〈N ,S,A,A2, P, R̂1, R̂2, γ〉 where the new elements are N = {1, 2} which is the set of agents, R̂1 := R + F̂ is the new Controller reward function which now contains a shaping reward F̂ , the function R̂2 : S × A × A2 → R is the one-step reward for Shaper (we give the details of this function later) and lastly the transition probability P : S ×A× 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 a2 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 an policy invariance result (Prop. 1) analogous to that in [27] and show RIGA preserves the optimal policy for M.

heading: 4.1 SWITCHING CONTROLS
text: 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, we now replace the policy space for Shaper with a 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 rewards only at states that are important for guiding Controller to its optimal policy. This 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.
Now at each state Shaper first makes a binary decision to decide to switch on its shaping reward F for Controller affecting a switch It which takes values in {0, 1}. This leads to an MG in which, unlike classical MGs, Shaper now uses switching controls to perform its actions.
The new Controller objective is: vπ,π 2
1 (s0, I0) = E [∑∞ t=0 γ t { R(st, at) + F̂ (st, a 2 t ; st−1, a 2 t−1)It }] , where Iτk+1 = 1 − Iτk , which is the switch for the shaping rewards which is 0 or 1 (and It ≡ 0,∀t ≤ 0) and {τk} are times that a switch takes place for example if the switch is first turned on at state s5 then turned off at s7, then τ1 = 5 and τ2 = 7 (we will shortly describe these in detail). The switch It is managed by Shaper, therefore by switching It between 0 or 1, Shaper activates or deactivates the shaping reward.
We now describe how at each state both the decision to activate a shaping reward and their magnitudes are determined. Recall that a2t ∼ π2 determines the shaping reward through F . At any st, the decision to turn on It and shape rewards is decided by a (categorical) policy g2 : S → {0, 1}. Therefore, g2 determines whether a (or no) Shaper policy π2 should be used to execute an action a2t ∼ π2. It can now be seen the sequence of times τk = inf{t > τk−1|st ∈ S, g2(st) = 1} are rules that depend on the state. Hence, by learning an optimal g2, Shaper learns the best states to activate F .

heading: Summary of events:
text: At a time t ∈ 0, 1 . . .
• Both players make an observation of the state st ∈ S. • Controller takes an action at sampled from its policy π. • Shaper decides whether or not to activate the shaping reward using g2 : S → {0, 1} • If g2(st) = 0:
X◦ The switch is not activated (It = 0). Controller receives a reward r ∼ R(st, at) and the system transitions to the next state st+1.
• If g2(st) = 1: X◦ Shaper takes an action a2t sampled from its policy π2. X◦ The switch is activated (It = 1), Controller receives a reward R(st, at) + F̂ (st, a 2 t ; st−1, a 2 t−1)× 1 and the system transitions to the next state st+1.
We set τk ≡ 0∀k ≤ 0 and a2τk ≡ 0,∀k ∈ N (a 2 τk+1 , . . . , a2τk+1−1 remain non-zero) and a 2 k ≡ 0 ∀k ≤ 0 and use the shorthand I(t) ≡ It .

heading: 4.2 THE SHAPER’S OBJECTIVE
text: The goal of Shaper is 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 (probabilistic) rule. To induce Shaper to selectively choose when to switch on the shaping reward, each switch activation incurs a fixed cost for Shaper. The cost has two effects: first it reduces the complexity of Shaper problem since its decision space is to determine which subregions of S it should activate the shaping rewards (and their magnitudes). Second, 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. Given these remarks the objective for Shaper is given by
vπ,π 2
2 (s0, I0) = Eπ,π2  ∞∑ t=0 γt R̂1(st, It, at, a2t , a2t−1) + ∞∑ k≥1 c(It, It−1)δ t τ2k−1 + L(st)  . (1) The objective encodes Shaper agenda, namely to maximise the expected return.1 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 c : {0, 1}2 → R<0 is a strictly negative cost function which imposes a cost for each switch and is modulated by the Kronecker-delta function δtτ2k−1 which is 1 whenever t = τ2k−1 and 0 otherwise (this restricts the costs to only the points at which the shaping reward is activated). Lastly, the term L : S → R is a 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 a shaping-reward function that supports Controller’s learning which is tailored for the specific setting. This avoids inserting hand-designed exploration heuristics into Controller’s objective as in curiosity-based methods [6, 30] and classical reward shaping [27]. We later prove that with this objective, Shaper’s optimal policy maximises Controller’s (extrinsic) return (Prop. 1). Additionally, we show that the framework preserves the optimal policy of M.
There are various possibilities for the termination times {τ2k} (recall that {τ2k+1} are the times which the shaping reward F is switched on using g2). One is for Shaper to determine the sequence. Another is to build a construction of {τ2k} that directly incorporates the information gain that a state visit provides — we defer the details of this arrangement to Sec. 10 of the Appendix.

heading: 4.3 THE OVERALL LEARNING PROCEDURE
text: 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 a switch and the shaping reward magnitudes. In our implementation, we used proximal policy optimization (PPO) [32] as the learning algorithm
1Note that we can now see that R̂2 ≡ R(st, at) + F̂ (st, a2t ; st−1, a2t−1)It + ∑∞ k≥1 c(It, It−1)δ t τ2k−1 .
for all policies: Controller’s policy, switching control policy, and the reward magnitude policy. For Shaper L term we used L(st) := ‖ĥ(st)− h(st)‖22 as in RND [6] where h is a 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 : Rd 7→ Rm and a one-hot encoding of the action of Shaper. Specifically, φ̂(st, a2t ) := f(st) · i(a2t ) where i(a2t ) is a one-hot encoding of the action a2t picked by Shaper. Thus, F̂ (st, a2t ; st−1, a2t−1) = f(st) · i(a2t )− γ−1f(st−1) · i(a2t−1). The action set of Shaper is thus A2 := {0, 1, ...,m} where each element is an element of N, and π2 is a MLP π2 : Rd 7→ Rm. Precise details are in the Supplementary Materials Section 8.
Algorithm 1: Reinforcement Learning Optimising Shaping Algorithm (ROSA) Input: Initial Controller policy π0, Shaper policies g20 , π20 , RL learning algorithm ∆ Output: Optimised Controller policy π∗
1 for t = 1, T do 2 Given environment state st, sample at from π(st) and obtain st+1, rt+1 by applying at to environment 3 Evaluate g2(st) according to Prop. 2 4 if g2(st) = 1 then 5 Shaper samples an action a2t+1 ∼ π2(·|st+1) 6 Shaper computes rit+1 = F̂ (st, a 2 t , st+1, a 2 t+1), 7 Set shaped reward r = rt+1 + rit+1 8 else 9 Set r = rt+1
10 Update π, g2, π2 using (st, at, r, st+1) and ∆ // Learn the individual policies

heading: 5 CONVERGENCE AND OPTIMALITY OF OUR METHOD
text: The ROSA framework enables Shaper to learn a 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 M directly. To do this, we first study the stable point solutions of G. Unlike MDPs, the existence of a stable point solution in Markov policies is not guaranteed for MGs [5] and is rarely computable.2 MGs also often have multiple stable points that can be inefficient [25]; in G the outcome of such stable point profiles would be a poor performing Controller policy. To ensure the framework is useful, we must verify that the solution of G corresponds to M. We solve these challenges with the following scheme: [A] The method preserves the optimal policy of M. [B] A stable point of the game G in Markov policies exists and is the convergence point of ROSA. [C] The convergence point of ROSA yields a payoff that is (weakly) greater than that from solving M directly. [D] ROSA converges to the stable point solution of G. We now prove [A] which shows the solution to M is preserved under the influence of Shaper:
Proposition 1 The following statements hold:
i) max π∈Π
vπ,π 2
1 (s) = max π∈Π
vπ1 (s), ∀s ∈ S,∀π2 ∈ Π2, where vπ1 (s) = E [ ∑∞ t=0 γ tR(st, at)].
ii) The Shaper’s optimal policy maximises vπ1 (s) for any s ∈ S.
Result (i) says that the Controller’s problem is preserved under the influence of the Shaper. Moreover the (expected) total return received by the agents is that from the environment (extrinsic rewards). Result (ii) establishes that Shaper’s optimal policy induces Shaper to maximise its (Controller’s) extrinsic total return. The result is established by a 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. 1, we deduce the following result:
2Special exceptions are team MGs where agents share an objective and zero-sum MGs [34].
Corollary 1 ROSA preserves the MDP M. In particular, let (π̂1, π̂2) be a stable point policy profile3 of the MG induced by ROSA G then π̂1 is a solution to the MDP, M.
Therefore, the introduction of Shaper does not alter the fundamentals of the problem.
We now show that G belongs to a special class of MGs which possess a 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 π ∈ Π and π2 ∈ Π2, given a function V π,π2 : S × N → R, we define the intervention operator Mπ,π2 by Mπ,π2V π,π2(sτk , I(τk)) := R̂1(sτk , I(τk), aτk , a2τk , ·) + c(Ik, Ik−1) + γ ∑ s′∈S P (s ′; aτk , s)V π,π2(s′, I(τk+1)) for any sτk ∈ S and ∀τk where aτk ∼ π(·|sτk) and where a2τk ∼ π 2(·|sτk). We define the Bellman operator T of the game G by TV π,π 2 (sτk , I(τk)) :=
max { Mπ,π2Λ(sτk , I(τk)), R(sτk , a) + γmax
a∈A
∑ s′∈S P (s ′; a, sτk)Λ(s ′, I(τk)) } . Given a value
function {Vi}i∈{1,2}, the quantityMVi measures the expected future stream of rewards for agent i after an immediate switch minus the cost of switching.
We now show that a stable point of G can be computed using dynamic programming:
Theorem 1 Let V : S×N→ R then the game G has a stable point which is a given by lim k→∞ T kV π =
sup π̂∈Π
V π̂ = V π ? , where π̂ is a stable policy profile for the MG, G.
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, it proves the that the stable point of G is the limit point of the sequence T 1V, T 2V, . . . ,. Crucially, (by Corollary 1) the limit point corresponds to the solution of the MDPM. Theorem 1 is proven by firstly proving that G has a dual representation as an MDP whose solution corresponds to the stable point of the MG. Theorem 1 enables a distributed Q-learning method [4] to tractably solve the MG.
Having constructed a procedure to find the optimal Controller policy, our next result characterises Shaper policy g2 and the optimal times to activate F .
Proposition 2 The policy g2 is given by the following expression: g2(st) = H(Mπ,π 2 V π,π 2 − V π,π 2
)(st, It), ∀(st, It) ∈ S ×{0, 1}, where V is the solution in Theorem 1 and H is the Heaviside function, moreover Shaper’s switching times are τk = inf{τ > τk−1|Mπ,π 2 V π,π 2 = V π,π 2}.
Hence, Prop. 2 also characterises the (categorical) distribution g2. Moreover, given the function V , the times {τk} can be determined by evaluating ifMV = V holds. In general, introducing shaping rewards may undermine learning and worsen overall performance. We now prove that the ROSA framework introduces an shaping rewards that yield higher total (environment) returns for Controller as compared to solving M directly ([C]).
Proposition 3 Controller’s (extrinsic) expected return vπ,π 2
1 whilst playing G is (weakly) higher than vπ1 , the (extrinsic) expected return for M i.e. v π,π2
1 (s, ·) ≥ vπ1 (s), ∀s ∈ 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 a reduction to the total (environment) return for Controller as compared to its total return without F . Note that by Prop. 1, Theorem 3 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 Π on a function Λ by: ΠΛ := arg min
Λ̄∈{Ψr|r∈Rp} ∥∥Λ̄− Λ∥∥. Theorem 2 ROSA converges to the stable point of G, moreover, given a set of linearly independent basis functions Ψ = {ψ1, . . . , ψp} with ψk ∈ L2,∀k, ROSA converges to a limit point r? ∈ Rp which
3By stable point profile we mean a configuration in which no agent can increase their expected return by deviating unilaterally from their policy given the other agents’ policies, i.e. a Markov perfect equilibrium [12].
is the unique solution to ΠF(Ψr?) = Ψr? where F is defined by: FΛ := R̂1 + γP max{MΛ,Λ} where r? satisfies: ‖Ψr? −Q?‖ ≤ (1− γ2)−1/2 ‖ΠQ? −Q?‖. Theorem 2 establishes the solution to G can be computed using ROSA. This means that Shaper converges to a shaping-reward 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.

heading: 6 EXPERIMENTS
text: We performed a series of experiments to test if ROSA (1) learns a beneficial shaping-reward function (2) decomposes complex tasks into sub-goals, and (3) tailors shaping rewards to encourage Controller to capture environment rewards (as opposed to merely pursuing novelty). In these tasks, we compared 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 (BiPaRS-IMGL) [16]4 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 a shapingreward function that leads to improved Controller performance. In particular, it is able to learn to shape rewards that encourage the RL agent to avoid suboptimal – but easy to learn – policies in favour of policies that attain the maximal return. To demonstrate this, we designed a Maze environment with two terminal states: a suboptimal goal state that yields a reward of 0.5 and an optimal goal state which yields a reward of 1. In this maze design, the sub-optimal goal is more easily
reached. A good shaping-reward function discourages the agent from visiting the sub-optimal goal. As shown in Fig. 15 our method achieves this by learning to place high shaping rewards (dark green) on the path that leads to the optimal goal.
2. Subgoal discovery. We used the Subgoal Maze introduced in [21] to test if ROSA can discover subgoals. The environment has two rooms separated by a gateway. To solve this, the agent has to discover the subgoal of reaching the gateway before it can reach the goal. Rewards are −0.01 everywhere except at 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 importance to reaching the gateway, depicted by the heatmap of added shaped rewards.
3. Ignoring non-beneficial 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 or novelty metrics would place high shaping reward. To verify this claim, we use a modified Maze environment called Red-Herring Maze which features a large part of the state space that has no environment reward, but with the goal (and accompanying real reward) in a different part
4BiPaRS-IMGL requires a manually crafted shapingreward (only available in Cartpole).
5The sum of curves for each method may be less that 1 if the agent fails to arrive at either goal.
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. 3 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 to ignore them.
Learning Performance. We compared our method with the baselines in four challenging sparse rewards environments: Cartpole, Gravitar, Solaris, and Super Mario. These environments vary in state representation, transition dynamics and reward sparsity. In Cartpole, a penalty of −1 is received only when the pole collapses; in Super Mario Brothers the agent can go for 100s of steps without encountering a reward. Fig. 4 shows learning curves. In terms of performance, ROSA either markedly outperforms the best competing baseline (Cartpole, Gravitar) or is on par with them (Solaris, Super Mario) showing that it is robust to the nature of the environment 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.

heading: 7 CONCLUSION
text: In this paper, we presented a novel solution method to solve the problem of reward shaping. Our Markov game framework of a primary Controller and a secondary reward shaping agent is guaranteed 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 a theoretically sound and empirically robust approach to solving the reward shaping problem, our method opens up the applicability of RL to a range of real-world control problems. The most significant contribution of this paper, however, is the novel construction that marries RL, multi-agent RL and game theory which leads to new solution method in RL. We believe this powerful approach can be adopted to solve other open challenges in RL.

heading: Appendix

heading: Table of Contents

heading: 8 Algorithm 2

heading: 9 Further Implementation Details 3

heading: 10 Shaper Termination Times 3

heading: 11 Experimental Details 4
text: 11.1 Environments & Preprocessing Details . . . . . . . . . . . . . . . . . . . . . . 4 11.2 Hyperparameter Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4

heading: 12 Ablation Studies 5

heading: 13 Flexibility of ROSA to Accommodate different Exploration Bonus Terms L 7

heading: 14 Robustness to choices of φ Parameters 8

heading: 15 Notation & Assumptions 9

heading: 16 Proof of Technical Results 9

heading: 17 Additional Experiment 1 - Replacing RND for Bonus Reward 28
text: 18 Additional Experiment 2 - Robustness to initialisation of φ 28

heading: 8 ALGORITHM
text: Algorithm 2: Reinforcement Learning Optimising Shaping Algorithm ROSA Input: Environment E
Initial Controller policy π0 with parameters θπ0 Initial Shaper switch policy g20 with parameters θg20 Initial Shaper action policy π20 with parameters θπ20 Randomly initialised fixed neural network φ(·, ·) Neural networks h (fixed) and ĥ for RND with parameter θĥ Buffer B Number of rollouts Nr, rollout length T Number of mini-batch updates Nu Switch cost c(·), Discount factor γ, learning rate α
Output: Optimised Controller policy π∗ 1 π, π2, g2 ← π0, π20 , g20 2 for n = 1, Nr do 3 // Collect rollouts 4 for t = 1, T do 5 Get environment states st from E 6 Sample at from π(st) 7 Apply action at to environment E, and get reward rt and next state st+1 8 Sample gt from g2(st) // Switching control 9 if gt = 1 then 10 Sample a2t from π 2(st) 11 Sample a2t+1 from π 2(st+1) 12 rit = γφ(st+1, a 2 t+1)− φ(st, a2t ) // Calculate F (st, at, st+1, at+1) 13 else 14 a2t , r i t = 0, 0 // Dummy values
15 Append (st, at, gt, a2t , rt, r i t, st+1) to B
16 for u = 1, Nu do 17 Sample data (st, at, gt, a2t , rt, r i t, st+1) from B 18 if gt = 1 then 19 Set shaped reward to rst = rt + r i t 20 else 21 Set shaped reward to rst = rt 22 // Update RND 23 LossRND = ||h(st)− ĥ(st)||2 24 θĥ ← θĥ − α∇LossRND 25 // Update Shaper 26 lt = ||h(st)− ĥ(st)||2 // Compute L(st) 27 ct = c(·)gt 28 Compute Lossπ2 using (st, at, gt, ct, rt, rit, lt, st+1) using PPO loss // Section 4.2 29 Compute Lossg2 using (st, at, gt, ct, rt, r i t, lt, st+1) using PPO loss // Section 4.2 30 θπ2 ← θπ2 − α∇Lossπ2 31 θg2 ← θg2 − α∇Lossg2 32 // Update Controller 33 Compute Lossπ using (st, at, rst , st+1) using PPO loss // Section 4 34 θπ ← θπ − α∇Lossπ

heading: 9 FURTHER IMPLEMENTATION DETAILS
text: Details of Shaper and F (shaping reward) Object Description f Fixed feed forward NN that maps Rd 7→ Rm
[512, ReLU, 512, ReLU, 512, m] A2 Discrete integer action set which is size of output of f , i.e.,A2 is set of integers {1, ...,m} π2 Fixed feed forward NN that maps Rd 7→ Rm
[512, ReLU, 512, ReLU, 512, m] Potential function φ φ(s, a2) = f(s) · a2
F γφ(st+1, a 2 t+1) - φ(st, a 2 t ), γ = 0.95
d=Dimensionality of states; m ∈ N - tunable free parameter. In all experiments we used the above form of F as follows: a state st is input to the π2 network and the network outputs logits pt. We softmax and sample from pt to obtain the action a2t . This action is one-hot encoded. Then, the action a2t is multiplied with f(st) to compute the second term of F . A similar process is used to compute the first term. In this way the policy of Shaper chooses the shaping reward.

heading: 10 SHAPER TERMINATION TIMES
text: There are various possibilities for the termination times {τ2k} (recall that {τ2k+1} are the times which the shaping reward F is switched on using g2). One is for Shaper to determine the sequence. Another is to build a construction of {τ2k} that directly incorporates the information gain that a state visit provides: let w : Ω→ {0, 1} be a random variable with Pr(w = 1) = p and Pr(w = 0) = 1−p where p ∈]0, 1]. Then for any k = 1, 2, . . . , and denote by ∆L(sτk) := L(sτk)−L(sτk−1), then we can set:
I(sτ2k+1+j) = { I(sτ2k+1), if w∆L(sτk+j) > 0, I(sτ2k+2), w∆L(sτk+j) ≤ 0.
(2)
To explain, since {τ2k}k≥0 are the times at which F is switched off then if F is deactivated at exactly after j time steps then I(sτ2k+1+l) = I(sτ2k+1) for any 0 ≤ l < j and I(sτ2k+1+j) = I(sτ2k+2) . We now see that (2) terminates F when either the random variable w attains a 0 or when ∆L(sτk+j) ≤ 0 which occurs when the exploration bonus in the current state is lower than that of the previous state.

heading: 11 EXPERIMENTAL DETAILS

heading: 11.1 ENVIRONMENTS & PREPROCESSING DETAILS
text: The table below shows the provenance of environments used in our experiments.
Atari & Cartpole https://github.com/openai/gym Maze https://github.com/MattChanTK/gym-maze
Super Mario Brothers https://github.com/Kautenja/gym-super-mario-bros
Furthermore, we used preprocessing settings as indicated in the following table.
Setting Value
Max frames per episode Atari & Mario→ 18000 / Maze & Cartpole→ 200 Observation concatenation Preceding 4 observations Observation preprocessing Standardization followed by clipping to [-5, 5]
Observation scaling Atari & Mario→ (84, 84, 1) / Maze & Cartpole→ None Reward (extrinsic and intrinsic) preprocessing Standardization followed by clipping to [-1, 1]

heading: 11.2 HYPERPARAMETER SETTINGS
text: 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 1 γE 0.99 λ 0.95
Learning rate 1x10−4 Number of minibatches 4
Number of optimization epochs 4 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 [1, 5] Coefficient of intrinsic reward [1, 2, 5, 10, 20, 50]
γI 0.99 Probability of terminating option [0.5, 0.75, 0.8, 0.9, 0.95]
RND output size [2, 4, 8, 16, 32, 64, 128, 256]

heading: 12 ABLATION STUDIES
text: Our reward-shaping method features a mechanism to selectively pick states to which intrinsic rewards are added. It also adapts its shaping rewards according to Controller’s learning process. In this section, we present the results of experiments in which we ablated each of these components. In particular, we test the performance of our method in comparison to a version of our method with the switching mechanism removed. We then present the result of an experiment in which we investigated the ability of our method to adapt to different behaviour of Controller.

heading: ABLATION STUDY 1: SWITCHING CONTROLS
text: 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 a modified version in which Shaper must add intrinsic rewards to all states. That is, for this version of our method we remove the presence of the switching control mechanism for Shaper. Figure 5 (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 of our method sans the switching control mechanism. For example, it takes the agent that has no 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 to 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.

heading: ABLATION STUDY 2: ADAPTION OF OUR METHOD TO DIFFERENT CONTROLLER POLICIES
text: We claimed Shaper can design a reward-shaping scheme that can adapt its shaping reward guidance of Controller (to achieve the optimal policy) according to Controller’s (RL) policy.
To test this claim, we tested two versions of our agent in a 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 an optimal goal which has a reward 1. 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 are determined by a high
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 to guide Controller away from the suboptimal goal (and towards the optimal goal).
Figure 5 (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 it seeks to guide.
6To generate this policy, we artificially increased the entropy by adjusting the temperature of a softmax function on the policy logits.

heading: 13 FLEXIBILITY OF ROSA TO ACCOMMODATE DIFFERENT EXPLORATION BONUS TERMS L
text: 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) = 1Count(s)+1 for any given state s ∈ S where Count(s) refers to a simple count of the number of times the state s has been visited. We conducted the Ablation study in the environment in Experiment 1 presented in Sec. 6. 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.
14 ROBUSTNESS TO CHOICES OF φ PARAMETERS
To demonstrate the robustness of φ to different choices of weight parameters, we conducted a study with 3 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.

heading: 15 NOTATION & ASSUMPTIONS
text: We assume that S is defined on a probability space (Ω,F ,P) and any s ∈ S is measurable with respect to the Borel σ-algebra associated with Rp. We denote the σ-algebra of events generated by {st}t≥0 by Ft ⊂ F . In what follows, we denote by (V, ‖‖) any finite normed vector space and byH 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 1 The stochastic process governing the system dynamics is ergodic, that is the process is stationary and every invariant random variable of {st}t≥0 is equal to a constant with probability 1. Assumption 2 The constituent functions of the players’ objectives R, F and L are in L2.
Assumption 3 For any positive scalar c, there exists a scalar µc such that for all s ∈ S and for any t ∈ N we have: E [1 + ‖st‖c|s0 = s] ≤ µc(1 + ‖s‖c). Assumption 4 There exists scalars C1 and c1 such that for any function J satisfying |J(s)| ≤ C2(1 + ‖s‖c2) for some scalars c2 and C2 we have that: ∑∞ t=0 |E [J(st)|s0 = s]− E[J(s0)]| ≤ C1C2(1 + ‖st‖c1c2). Assumption 5 There exists scalars c and C such that for any s ∈ S we have that: |J(z, ·)| ≤ C(1 + ‖z‖c) for J ∈ {R,F, L}. We also make the following finiteness assumption on set of switching control policies for Shaper:
Assumption 6 For any policy gc, the total number of interventions is given by K <∞. We lastly make the following assumption on L which can be made true by construction:
Assumption 7 Let n(s) be the state visitation count for a given state s ∈ S. For any a ∈ A, the function L(s, a) = 0 for any n(s) ≥M where 0 < M ≤ ∞.

heading: 16 PROOF OF TECHNICAL RESULTS
text: We begin the analysis with some preliminary lemmata and definitions which are useful for proving the main results.
Definition 1 A.1 An operator T : V → V is said to be a contraction w.r.t a norm ‖ · ‖ if there exists a constant c ∈ [0, 1[ such that for any V1, V2 ∈ V we have that:
‖TV1 − TV2‖ ≤ c‖V1 − V2‖. (3)
Definition 2 A.2 An operator T : V → V is non-expansive if ∀V1, V2 ∈ V we have:
‖TV1 − TV2‖ ≤ ‖V1 − V2‖. (4)
Lemma 1 For any f : V → R, g : V → R, we have that:∥∥∥∥maxa∈V f(a)−maxa∈V g(a) ∥∥∥∥ ≤ maxa∈V ‖f(a)− g(a)‖ . (5)
Proof 1 We restate the proof given in [23]:
f(a) ≤ ‖f(a)− g(a)‖+ g(a) (6) =⇒ max
a∈V f(a) ≤ max a∈V {‖f(a)− g(a)‖+ g(a)} ≤ max a∈V ‖f(a)− g(a)‖+ max a∈V g(a). (7)
Deducting max a∈V g(a) from both sides of (7) yields:
max a∈V f(a)−max a∈V g(a) ≤ max a∈V ‖f(a)− g(a)‖ . (8)
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.
Lemma 2 A.4 The probability transition kernel P is non-expansive, that is: ‖PV1 − PV2‖ ≤ ‖V1 − V2‖. (9)
Proof 2 The result is well-known e.g. [40]. We give a proof using the Tonelli-Fubini theorem and the iterated law of expectations, we have that:
‖PJ‖2 = E [ (PJ)2[s0] ] = E ( [E [J [s1]|s0])2 ] ≤ E [ E [ J2[s1]|s0 ]] = E [ J2[s1] ] = ‖J‖2,
where we have used Jensen’s inequality to generate the inequality. This completes the proof.

heading: PROOF OF PROPOSITION 1
text: Proof 3 (Proof of Prop 1) To prove (i) of the proposition it suffices to prove that the term∑T t=0 γ
tF (θt, θt−1)I(t) converges to 0 in the limit as T → ∞. As in classic potential-based reward shaping [27], central to this observation is the telescoping sum that emerges by construction of F .
First recall vπ,π 2
1 (s, I0), for any (s, I0) ∈ S × {0, 1} is given by:
vπ,π 2
1 (s, I0) = Eπ,π2 [ ∞∑ t=0 γt { Ri(st, at) + F̂ (st, a 2 t ; st−1, a 2 t−1)It }] (10)
= Eπ,π2 [ ∞∑ t=0 γtRi(st, at) + ∞∑ t=0 γtF̂ (st, a 2 t ; st−1, a 2 t−1)It ] (11)
= Eπ,π2 [ ∞∑ t=0 γtRi(st, at) ] + Eπ,π2 [ ∞∑ t=0 γtF̂ (st, a 2 t ; st−1, a 2 t−1))It ] . (12)
Hence it suffices to prove that Eπ,π2 [∑∞ t=0 γ tF̂ (st, a 2 t ; st−1, a 2 t−1))It ] = 0.
Recall there a number of time steps that elapse between τk and τk+1, now
∞∑ t=0 γtF̂ (st, a 2 t ; st−1, a 2 t−1))I(t)
= τ2∑ t=τ1+1 γtφ(st, a 2 t )− γt−1φ(st−1, a2t−1) + γτ1φ(sτ1 , a2τ1)
+ τ4∑ t=τ3+1 γtφ(st, a 2 t )− γt−1φ(st−1, a2t−1) + γτ3φ(sτ3 , a2τ3)
+ . . .+ τ2k∑ t=τ(2k−1)+1 γtφ(st, a 2 t )− γt−1φ(st−1, a2t−1) + γτ1φ(sτ2k+1 , a2τ2k+1) + . . .+
= τ2−1∑ t=τ1 γt+1φ(st+1, a 2 t+1)− γtφ(st, a2t ) + γτ1φ(sτ1 , a2τ1)
+ τ4−1∑ t=τ3 γt+1φ(st+1, a 2 t+1)− γtφ(st, a2t ) + γτ3φ(sτ3 , a2τ3)
+ . . .+ τ2K−1∑ t=τ(2k−1) γtφ(st, a 2 t )− γt−1φ(st−1, a2t−1) + γτ2k−1φ(sτ2k−1 , a2τ2k−1) + . . .+
= ∞∑ k=1 τ2K−1∑ t=τ2k−1 γt+1φ(st+1, a 2 t+1)− γtφ(st, a2t )− ∞∑ k=1 γτ2k−1φ(sτ2k−1 , a 2 τ2k−1 )
= ∞∑ k=1 γτ2kφ(sτ2k , a 2 τ2k )− ∞∑ k=1 γτ2k−1φ(sτ2k−1 , a 2 τ2k−1 )
= ∞∑ k=1 γτ2kφ(sτ2k , 0)− ∞∑ k=1 γτ2k−1φ(sτ2k−1 , 0) = 0,
where we have used the fact that by construction a2t ≡ 0 whenever t = τ1, τ2, . . . and by construction φ(s, 0) ≡ 0 for any s.
With this we readily deduce that vπ,π 2 i (s) = Eπ,π2 [ ∑∞ t=0 γ
tRi(st, at)] which is a measure of environment rewards only from which statement (i) can be readily deduced.
For part (ii) we note first that it is easy to see that vπ,π 2
2 (s0, I0) is bounded above, indeed using the key result in the proof of part (i) and the properties of c we have that
vπ,π 2
2 (s0, I0) = Eπ,π2  ∞∑ t=0 γt R̂+∑ k≥1 c(It, It−1)δ t τ2k−1 + Ln(st)  (13) = Eπ,π2  ∞∑ t=0 γt R+∑ k≥1 c(It, It−1)δ t τ2k−1 + Ln(st) + ∞∑ t=0 γtF̂ It
 (14) ≤ Eπ,π2
[ ∞∑ t=0 γt (R+ Ln(st)) ] (15)
≤ ∣∣∣∣∣Eπ,π2 [ ∞∑ t=0 γt (R+ Ln(st)) ]∣∣∣∣∣ (16) ≤ Eπ,π2
[ ∞∑ t=0 γt ‖R+ Ln‖ ] (17)
≤ ∞∑ t=0 γt (‖R‖+ ‖Ln‖) (18)
= 1
1− γ (‖R‖+ ‖L‖) , (19)
using the triangle inequality, the definition of R̂ and the (upper-)boundedness of L andR (Assumption 5). We now note that by the dominated convergence theorem we have that ∀(s0, I0) ∈ S × {0, 1}
lim n→∞
vπ,π 2
2 (s0, I0) = limn→∞ Eπ,π2  ∞∑ t=0 γt R̂+∑ k≥1 c(It, It−1)δ t τ2k−1 + Ln(st)  (20) = Eπ,π2 lim
n→∞  ∞∑ t=0 γt R̂+∑ k≥1 c(It, It−1)δ t τ2k−1 + Ln(st)  (21) = Eπ,π2  ∞∑ t=0 γt R̂+∑ k≥1 c(It, It−1)δ t τ2k−1
 (22) = Eπ,π2  ∞∑ t=0 γt R+∑ k≥1 c(It, It−1)δ t τ2k−1  = K 1− γ + vπ1 (s0), (23)
again using the key result in the proof of (i) and Assumption 6 in the last step, after which we deduce (ii).
Note that by (ii) we heron may consider the quantity for the Shaper expected return:
v̂π,π 2
2 (s0, I0) = Eπ,π2  ∞∑ t=0 γt R+∑ k≥1 c(It, It−1)δ t τ2k−1  . (24)

heading: PROOF OF THEOREM 1
text: Proof 4 Theorem 1 is proved by firstly showing that when the players jointly maximise the same objective there exists a 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 a dual representation as an MG in which jointly maximise the same objective which has a stable point that can be computed by solving an 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 to a test function.
Therefore, the scheme of the proof is summarised with the following steps:
I) Prove that the solution to Markov Team games (that is games in which both players maximise identical objectives) in which one of the players uses switching control is the limit point of a sequence of Bellman operators (acting on some test function).
II) Prove that for the MG G that is there exists a function Bπ,π2 : S × {0, 1} → R such that7
vπ,π 2 i (z)− v π′,π2 i (z) = B π,π2(z)−Bπ′,π2(z), ∀z ≡ (s, I0) ∈ S × {0, 1},∀i ∈ {1, 2}.
III) Prove that the MG G has a dual representation as a Markov Team Game which admits a representation as an MDP.

heading: PROOF OF PART I
text: Our first result proves that the operator T is a contraction operator. First let us recall that the switching time τk is defined recursively τk = inf{t > τk−1|st ∈ A, τk ∈ Ft} where A = {s ∈ S,m ∈M |g2(m|st) > 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:
‖Tψ − Tψ′‖ ≤ γ ‖ψ − ψ′‖ .
Proof 5 Recall we define the Bellman operator Tψ of G acting on a function Λ : S × N→ R by
TψΛ(sτk , I(τk)) := max
{ Mπ,π 2
Λ(sτk , I(τk)), [ ψ(sτk , a) + γmax
a∈A ∑ s′∈S P (s′; a, sτk)Λ(s ′, I(τk)) ]} (25)
In what follows and for the remainder of the script, we employ the following shorthands: Pass′ =: ∑ s′∈S P (s′; a, s), Pπss′ =: ∑ a∈A π(a|s)Pass′ , Rπ(zt) := ∑ at∈A π(at|s)R̂(zt, at, θt, θt−1)
To prove that T is a contraction, we consider the three cases produced by (25), that is to say we prove the following statements:
i) ∣∣∣∣Θ(zt, a, a2t , a2t−1) + γmaxa∈A Pas′stψ(s′, ·)− ( Θ(zt, a, a 2 t , a 2 t−1) + γmax a∈A Pas′stψ ′(s′, ·) )∣∣∣∣ ≤ γ ‖ψ − ψ′‖
ii) ∥∥∥Mπ,π2ψ −Mπ,π2ψ′∥∥∥ ≤ γ ‖ψ − ψ′‖ , (and henceM is a contraction).
7This property is analogous to the condition in Markov potential games [19, 26]
iii) ∥∥∥∥Mπ,π2ψ − [Θ(·, a) + γmaxa∈A Paψ′ ]∥∥∥∥ ≤ γ ‖ψ − ψ′‖ . where zt ≡ (st, It) ∈ S × {0, 1}. We begin by proving i).
Indeed, for any a ∈ A and ∀zt ∈ S × {0, 1},∀θt, θt−1 ∈ Θ,∀s′ ∈ S we have that∣∣∣∣Θ(zt, a, a2t , a2t−1) + γPπs′stψ(s′, ·)− [Θ(zt, a, a2t , a2t−1) + γmaxa∈A Pas′stψ′(s′, ·) ]∣∣∣∣
≤ max a∈A ∣∣γPas′stψ(s′, ·)− γPas′stψ′(s′, ·)∣∣ ≤ γ ‖Pψ − Pψ′‖ ≤ γ ‖ψ − ψ′‖ ,
again using the fact that P is non-expansive and Lemma 1.
We now prove ii).
For any τ ∈ F , define by τ ′ = inf{t > τ |st ∈ A, τ ∈ Ft}. Now using the definition ofM we have that for any sτ ∈ S∣∣∣(Mπ,π2ψ −Mπ,π2ψ′)(sτ , I(τ))∣∣∣
≤ max aτ ,a2τ ,a 2 τ−1∈A×Θ2 ∣∣∣∣∣Θ(zτ , aτ , a2τ , a2τ−1) + c(Iτ , Iτ−1) + γPπs′sτPaψ(sτ , I(τ ′)) − ( Θ(zτ , aτ , a 2 τ , a 2 τ−1) + c(Iτ , Iτ−1) + γPπs′sτP aψ′(sτ , I(τ ′)) ) ∣∣∣∣∣
= γ ∣∣Pπs′sτPaψ(sτ , I(τ ′))− Pπs′sτPaψ′(sτ , I(τ ′))∣∣ ≤ γ ‖Pψ − Pψ′‖ ≤ γ ‖ψ − ψ′‖ ,
using the fact that P is non-expansive. The result can then be deduced easily by applying max on both sides.
We now prove iii). We split the proof of the statement into two cases:
Case 1:
Mπ,π 2 ψ(sτ , I(τ))− ( Θ(zτ , aτ , a 2 τ , a 2 τ−1) + γmax
a∈A Pas′sτψ ′(s′, I(τ))
) < 0. (26)
We now observe the following:
Mπ,π 2
ψ(sτ , I(τ))−Θ(zτ , aτ , a2τ , a2τ−1) + γmax a∈A Pas′sτψ ′(s′, I(τ)) ≤ max {
Θ(zτ , aτ , a 2 τ , a 2 τ−1) + γPπs′sτP
aψ(s′, I(τ)),Mπ,π 2 ψ(sτ , I(τ)) }
−Θ(zτ , aτ , a2τ , a2τ−1) + γmax a∈A Pas′sτψ ′(s′, I(τ))
≤ ∣∣∣∣∣max{Θ(zτ , aτ , a2τ , a2τ−1) + γPπs′sτPaψ(s′, I(τ)),Mπ,π2ψ(sτ , I(τ))} −max { Θ(zτ , aτ , a 2 τ , a 2 τ−1) + γmax
a∈A Pas′sτψ
′(s′, I(τ)),Mπ,π 2
ψ(sτ , I(τ)) } + max { Θ(zτ , aτ , a 2 τ , a 2 τ−1) + γmax
a∈A Pas′sτψ
′(s′, I(τ)),Mπ,π 2
ψ(sτ , I(τ)) } −Θ(zτ , aτ , a2τ , a2τ−1) + γmax
a∈A Pas′sτψ ′(s′, I(τ)) ∣∣∣∣∣
≤ ∣∣∣∣∣max { Θ(zτ , aτ , a 2 τ , a 2 τ−1) + γmax a∈A Pas′sτψ(s ′, I(τ)),Mπ,π 2 ψ(sτ , I(τ)) }
−max {
Θ(zτ , aτ , a 2 τ , a 2 τ−1) + γmax a∈A Pas′sτψ
′(s′, I(τ)),Mπ,π 2
ψ(sτ , I(τ)) } ∣∣∣∣∣ + ∣∣∣∣∣max { Θ(zτ , aτ , a 2 τ , a 2 τ−1) + γmax a∈A Pas′sτψ ′(s′, I(τ)),Mπ,π 2 ψ(sτ , I(τ)) }
−Θ(zτ , aτ , a2τ , a2τ−1) + γmax a∈A Pas′sτψ ′(s′, I(τ)) ∣∣∣∣∣ ≤ γmax
a∈A ∣∣Pπs′sτPaψ(s′, I(τ))− Pπs′sτPaψ′(s′, I(τ))∣∣ + ∣∣∣∣max{0,Mπ,π2ψ(sτ , I(τ))− (Θ(zτ , aτ , a2τ , a2τ−1) + γmaxa∈A Pas′sτψ′(s′, I(τ)) )}∣∣∣∣
≤ γ ‖Pψ − Pψ′‖ ≤ γ‖ψ − ψ′‖,
where we have used the fact that for any scalars a, b, c we have that |max{a, b} −max{b, c}| ≤ |a− c| and the non-expansiveness of P . Case 2:
Mπ,π 2 ψ(sτ , I(τ))− ( Θ(zτ , aτ , a 2 τ , a 2 τ−1) + γmax
a∈A Pas′sτψ ′(s′, I(τ))
) ≥ 0.
For this case, first recall that for any τ ∈ F , −c(Iτ , Iτ−1) > λ for some λ > 0.
Mπ,π 2 ψ(sτ , I(τ))− ( Θ(zτ , aτ , a 2 τ , a 2 τ−1) + γmax
a∈A Pas′sτψ ′(s′, I(τ)) ) ≤Mπ,π 2 ψ(sτ , I(τ))− ( Θ(zτ , aτ , a 2 τ , a 2 τ−1) + γmax
a∈A Pas′sτψ ′(s′, I(τ))
) − c(Iτ , Iτ−1)
≤ Θ(zτ , aτ , a2τ , a2τ−1) + c(Iτ , Iτ−1) + γPπs′sτP aψ(s′, I(τ ′)) − (
Θ(zτ , aτ , a 2 τ , a 2 τ−1) + c(Iτ , Iτ−1) + γmax a∈A Pas′sτψ ′(s′, I(τ)) ) ≤ γmax
a∈A ∣∣Pπs′sτPa (ψ(s′, I(τ ′))− ψ′(s′, I(τ)))∣∣ ≤ γ |ψ(s′, I(τ ′))− ψ′(s′, I(τ))| ≤ γ ‖ψ − ψ′‖ ,
again using the fact that P is non-expansive. Hence we have succeeded in showing that for any Λ ∈ L2 we have that ∥∥∥∥Mπ,π2Λ−maxa∈A [ψ(·, a) + γPaΛ′] ∥∥∥∥ ≤ γ ‖Λ− Λ′‖ . (27) Gathering the results of the three cases gives the desired result.

heading: PROOF OF PART II
text: To prove Part II, we prove the following result:
Proposition 4 For any π ∈ Π and for any Shaper policy π2, there exists a function Bπ,π2 : S × {0, 1} → R such that
vπ,π 2 i (z)− v π′,π2 i (z) = B π,π2(z)−Bπ ′,π2(z), ∀z ≡ (s, I0) ∈ S × {0, 1} (28)
where in particular the function B is given by:
Bπ,π 2
(s0, I0) = Eπ,π2  ∞∑ t=0 γt R+∑ k≥1 c(It, It−1)δ t τ2k−1  , (29) for any (s0, I0) ∈ S × {0, 1}.
Proof 6 Note that by the deduction of (ii) in Prop 1, we immediately observe that
v̂π,π 2 2 (s0, I0) = B π,π2(s0, I0), ∀(s0, I0) ∈ S × {0, 1}. (30)
We therefore immediately deduce that for any two Shaper policies π2 and π′2 the following expression holds ∀(s0, I0) ∈ S × {0, 1}:
v̂π,π 2 2 (s0, I0)− v̂ π,π′2 2 (s0, I0) = B π,π2(s0, I0)−Bπ,π ′2 (s0, I0). (31)
Our aim now is to show that the following expression holds ∀(s0, I0) ∈ S × {0, 1}:
vπ,π 2 1 (I0, s0)− v π′,π2 1 (I0, s0) = B π,π2(I0, s0)−Bπ ′,π2(I0, s0), ∀i ∈ N
For the finite horizon case, the result is proven by induction on 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, we have that:
EsT−1∼dθ [ Bπ,π 2 T−1(IT−1, sT−1)−B π′,π2 T−1 (IT−1, sT−1) ]
= EsT−1∼dθ [ ∑ aT−1∈A π(aT−1; sT−1) R(sT−1, aT−1) +∑ k≥0 ∞∑ j=T−1 c(Ij , Ij−1)δ j τk  + γ
∑ sT∈S ∑ aT−1∈A π(aT−1; sT−1)P (sT ; aT−1)B π,π2 T (IT , sT )
− ( ∑ a′T−1∈A π′(a′T−1; sT−1) R(sT−1, a′T−1) +∑ k≥0 ∞∑ j=T−1 c(Ij , Ij−1)δ j τk  + γ
∑ sT∈S ∑ a′T−1∈A π′(a′T−1; sT−1)P (sT ; a ′ T−1)B π′,π2 T (IT , sT )
)]
= EsT−1∼dθ [ ∑ aT−1∈A π(aT−1; sT−1)R(sT−1, aT−1)
− ∑
a′T−1∈A π′(a′T−1; sT−1)R(sT−1, a ′ T−1)
+ γ [ ∑ sT∈S ∑ aT−1∈A π(aT−1; sT−1)P (sT ; aT−1)B π,π2 T (IT , sT )
− ∑ sT∈S ∑ a′T−1∈A π′(a′T−1; sT−1)P (sT ; a ′ T−1)B π′,π2 T (IT , sT )
]] .
(32)
We now observe that for any π ∈ Π and for any π2 we have that Bπ,π 2
T (IT , sT ) = E [∑ aT∈A π(aT ; sT ) [ R(sT , aT ) + ∑ k≥0 ∑∞ j=T c(Ij , Ij−1)δ j τk ]] , moreover we have that for any
π ∈ Π and for any π2
E [ ∑ aT∈A π(aT ; sT ) R(sT , aT ) +∑ k≥0 ∞∑ j=T c(Ij , Ij−1)δ j τk  − ∑ a′T∈A π′(aT ; sT ) R(sT , a′T ) +∑ k≥0 ∞∑ j=T c(Ij , Ij−1)δ j τk ]
=E [ ∑ aT∈A π(aT ; sT )R(sT , aT )− ∑ a′T∈A π′(a′T ; sT )R(sT , aT ) ]
+ E  ∑ aT∈A π(aT ; sT ) ∑ k≥0 ∞∑ j=T c(Ij , Ij−1)δ j τk − ∑ a′T∈A π′(a′T ; sT ) ∑ k≥0 ∞∑ j=T c(Ij , Ij−1)δ j τk  . Hence we find that
EsT−1∼dθ [ Bπ,π 2 T−1(IT−1, sT−1)−B π′,π2 T−1 (IT−1, sT−1) ]
= EsT−1∼dθ [ ∑ aT−1∈A π(aT−1; sT−1)R(sT−1, aT−1)
− ∑
a′T−1∈A π′(a′T−1; sT−1)R(sT−1, a ′ T−1)
(33)
+ γ ( ∑ sT∈S ∑ aT−1∈A ∑ aT∈A π(aT−1; sT−1)P (sT ; aT−1)π(aT ; sT )R(sT , aT ) (34)
− ∑ sT∈S ∑ a′T−1∈A ∑ a′T∈A π′(a′T−1; sT−1)P (sT ; a ′ T−1)π ′(a′T ; sT )R(sT , aT ) (35)
+ ∑ sT∈S ∑ aT−1∈A ∑ aT∈A ∑ k≥0 ∞∑ j=T π(aT−1; sT−1)P (sT ; aT−1)π(aT ; sT )c(Ij , Ij−1)δ j τk
(36)
− ∑ sT∈S ∑ a′T−1∈A ∑ a′T∈A ∑ k≥0 ∞∑ j=T π′(a′T−1; sT−1)P (sT ; a ′ T−1)π ′(a′T ; sT )c(Ij , Ij−1)δ j τk
)] .
(37)
Now
EsT−1∼dθ [ ∑ sT∈S ∑ aT−1∈A ∑ aT∈A ∑ k≥0 ∞∑ j=T π(aT−1; sT−1)P (sT ; aT−1)π(aT ; sT )c(Ij , Ij−1)δ j τk (38)
− ∑ sT∈S ∑ a′T−1∈A ∑ a′T∈A ∑ k≥0 ∞∑ j=T π′(a′T−1; sT−1)P (sT ; a ′ T−1)π ′(a′T ; sT )c(Ij , Ij−1)δ j τk
] (39)
= EsT−1∼dθ [ ∑ sT∈S ∑ aT−1∈A ∑ aT∈A π(aT−1; sT−1)P (sT ; aT−1)π(aT ; sT ) ∑ k≥0 ∞∑ j=T c(Ij , Ij−1)δ j τk
(40)
− ∑ sT∈S ∑ a′T−1∈A ∑ a′T∈A π′(a′T−1; sT−1)P (sT ; a ′ T−1)π ′(a′T ; sT ) ∑ k≥0 ∞∑ j=T c(Ij , Ij−1)δ j τk
] (41)
= EsT−1∼dθ [ ∑ sT∈S ∑ aT−1∈A ∑ aT∈A π(aT−1; sT−1)P (sT ; aT−1)π(aT ; sT ) ∑ k≥0 ∞∑ j=T c(Ij , Ij−1)δ j τk
(42)
− ∑ sT∈S ∑ a′T−1∈A ∑ a′T∈A π′(a′T−1; sT−1)P (sT ; a ′ T−1)π ′(a′T ; sT ) ∑ k≥0 ∞∑ j=T c(Ij , Ij−1)δ j τk
] (43)
= KEsT−1∼dθ [ ∑ sT∈S ∑ aT−1∈A ∑ aT∈A π(aT−1; sT−1)P (sT ; aT−1)π(aT ; sT ) (44)
− ∑ sT∈S ∑ a′T−1∈A ∑ a′T∈A π′(a′T−1; sT−1)P (sT ; a ′ T−1)π ′(a′T ; sT )
] (45)
= K ( ∑ aT∈A π(aT )− ∑ a′T∈A π′(a′T ) ) = 0. (46)
Hence, we find that EsT−1∼dθ [ Bπ,π 2 T−1(IT−1, sT−1)−B π′,π2 T−1 (IT−1, sT−1) ]
= EsT−1∼dθ [ ∑ aT−1∈A π(aT−1; sT−1)R(sT−1, aT−1)
− ∑
a′T−1∈A π′(a′T−1; sT−1)R(sT−1, a ′ T−1)
(47)
+ γ ( ∑ sT∈S ∑ aT−1∈A ∑ aT∈A π(aT−1; sT−1)P (sT ; aT−1)π(aT ; sT )R(sT , aT ) (48)
− ∑ sT∈S ∑ a′T−1∈A ∑ a′T∈A π′(a′T−1; sT−1)P (sT ; a ′ T−1)π ′(a′T ; sT )R(sT , aT )
)] (49)
= EsT−1∼dθ [ vπ,π 2 i,T−1(sT−1)− v π′,π2 i,T−1(sT−1) ] . (50)
Hence, we have succeeded in proving that the expression (28) holds for T − k when k = 1. Our next goal is to prove that the expression holds for any 0 < k ≤ T .
Note that for any T ≥ k > 0, we can write Bπ,π 2
T−k as
Bπ,π 2
T−k(I0, s0) = Eπ [ R(sT−k, aT−k) + ∑ k≥0 ∞∑ j=T−j c(Ij , Ij−1)δ j τk
(51)
+ γ ∑
sk+1∈S P (s′; sT−k, aT−k)B
π,π2 T−(k+1)(IT−(k+1), sT−(k+1))
] .
(52)
Now we consider the case when we evaluate the expression (28) for any 0 < k ≤ T . Our inductive hypothesis is the the expression holds for some 0 < k ≤ T , that is for any 0 < k ≤ T we have that:∑
sT−k∈S ∑ aT−(k+1)∈A π(aT−(k+1); sT−(k+1))P (sT−k; aT−(k+1))v π,π2 i,T−k(IT−k, sT−k)
− ∑
sT−k∈S ∑ a′T−(k+1)∈A π′(a′T−(k+1); sT−(k+1))P (sT−k; a ′ T−(k+1))v π′,π2 i,T−k(IT−k, sT−k) (53)
= ∑
sT−k∈S ∑ aT−(k+1)∈A π(aT−(k+1); sT−(k+1))P (sT−k; aT−(k+1))B π,π2 T−k(IT−k, sT−k) (54)
− ∑
sT−k∈S ∑ a′T−(k+1)∈A π′(a′T−(k+1); sT−(k+1))P (sT−k; a ′ T−(k+1))B π′,π2 T−k (IT−k, sT−k). (55)
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 = 1) result, indeed we have that EsT−(k+1)∼dθ [ Bπ,π 2 T−(k+1)(IT−(k+1), sT−(k+1))−B π′,π2 T−(k+1)(IT−(k+1), sT−(k+1)) ]
= EsT−(k+1)∼dθ [ ∑ aT−(k+1)∈A π(aT−(k+1); sT−(k+1))φ(sT−(k+1), aT−(k+1))
− ∑
a′T−(k+1)∈A π′(a′T−(k+1); sT−(k+1))φ(sT−(k+1), a ′ T−(k+1))
+ γ ∑
sT−k∈S ∑ aT−(k+1)∈A π(aT−(k+1); sT−(k+1))P (sT−k; aT−(k+1))B π,π2 T−k(IT−k, sT−k)
− γ ∑
sT−k∈S ∑ a′T−(k+1)∈A π′(a′T−(k+1); sT−(k+1))P (sT−k; a ′ T−(k+1))B π′,π2 T−k (IT−k, sT−k)
]
= EsT−(k+1)∼dθ [ ∑ aT−(k+1)∈A π(aT−(k+1); sT−(k+1)) R(sT−(k+1), aT−(k+1)) +∑ k≥0 ∞∑ j=T−1 c(Ij , Ij−1)δ j τk  + γ
∑ sT−k∈S ∑ aT−(k+1)∈A π(aT−(k+1); sT−(k+1))P (sT−k; aT−(k+1))B π,π2 T−k(IT−k, sT−k)
− ( ∑ a′T−(k+1)∈A π′(a′T−(k+1); sT−(k+1)) R(sT−(k+1), a′T−(k+1)) +∑ k≥0 ∞∑ j=T−1 c(Ij , Ij−1)δ j τk  + γ
∑ sT−k∈S ∑ a′T−(k+1)∈A π′(a′T−(k+1); sT−(k+1))P (sT−k; a ′ T−(k+1))B π′,π2 T−k (IT−k, sT−k)
])
= EsT−(k+1)∼dθ [ ∑ aT−(k+1)∈A π(aT−(k+1); sT−(k+1))R(sT−(k+1), aT−(k+1))
− ∑
a′T−(k+1)∈A π′(a′T−(k+1); sT−(k+1))R(sT−(k+1), a ′ T−(k+1))
+ γ [ ∑ sT−k∈S ∑ aT−(k+1)∈A π(aT−(k+1); sT−(k+1))P (sT−k; aT−(k+1))B π,π2 T−k(IT−k, sT−k)
− ∑
sT−k∈S ∑ a′T−(k+1)∈A π′(a′T−(k+1); sT−(k+1))P (sT−k; a ′ T−(k+1))B π′,π2 T−k (IT−k, sT−k)
]] .
(56)
= EsT−(k+1)∼dθ [ ∑ aT−(k+1)∈A π(aT−(k+1); sT−(k+1))R(sT−(k+1), aT−(k+1))
− ∑
a′T−(k+1)∈A π′(a′T−(k+1); sT−(k+1))R(sT−(k+1), a ′ T−(k+1))
+ γ [ ∑ sT−k∈S ∑ aT−(k+1)∈A π(aT−(k+1); sT−(k+1))P (sT−k; aT−(k+1))v π,π2 i,T−k(IT−k, sT−k)
− ∑
sT−k∈S ∑ a′T−(k+1)∈A π′(a′T−(k+1); sT−(k+1))P (sT−k; a ′ T−(k+1))v π′,π2 i,T−k(IT−k, sT−k)
]] .
(57)
= EsT−(k+1)∼dθ [ vπ,π 2 i,T−(k+1)(IT−(k+1), sT−(k+1))− v π′,π2 T−(k+1)(IT−(k+1), si,T−(k+1)) ] , (58)
using the inductive hypothesis and where we have used the fact that
EsT−(k+1)∼dθ [ ∑ sT−k∈S ∑ aT−(k+1)∈A ∑ aT−k∈A ∑ k≥0 ∞∑ j=T π(aT−(k+1); sT−(k+1))P (sT−k; aT−(k+1))π(aT−k; sT−k)c(Ij , Ij−1)δ j τk
(59)
− ∑
sT−k∈S ∑ a′T−(k+1)∈A ∑ a′T−k∈A ∑ k≥0 ∞∑ j=T π′(a′T−(k+1); sT−(k+1))P (sT−k; a ′ T−(k+1))π ′(a′T−k; sT−k)c(Ij , Ij−1)δ j τk ] (60)
= K  ∑ aT−k∈A π(aT−k)− ∑ a′T−k∈A π′(a′T−k)  = 0, (61) via similar reasoning as before and after which which we deduce the result in the finite case.
For the infinite horizon case, we must prove that there exists a measurable function B : Π× S → R such that the following holds for any i ∈ N and ∀π, π′iπ′ ∈ Π,∀π−iπ′ ∈ Π−i and ∀s ∈ S:
Es∼P [( vπ,π 2 i − v π′,π2 i ) (z) ] = Es∼P [( Bπ,π 2 −Bπ ′,π2 ) (z) ] . (62)
The result is proven by contradiction.
To this end, let us firstly assume ∃c 6= 0 such that Es∼P [( vπ,π 2 i − v π′,π2 i ) (z) ] − Es∼P [( Bπ,π 2 i −B π′,π2 i ) (z) ] = c.
Let us now define the following quantities for any s ∈ S and for each ππ′ ∈ Π and π−iπ′ ∈ Π−i and ∀i ∈ N :
vπ,π 2
i,T ′ (z) := T ′∑ t=0 µ(s0)π(a i 0, s0)π−i(a −i 0 , s0) t−1∏ j=0 ∑ sj+1∈S γtP (sj+1; sj , aj)π(a i j |sj)π−i(a−ij |sj)Ri(zj , aj),
and
Bπ,π 2
T ′ (z) := T ′∑ t=0 µ(s0)π(a i 0, s0)π−i(a −i 0 , s0) t−1∏ j=0 ∑ sj+1∈S P (sj+1; sj , aj) · π(aij |sj)π−i(a−ij |sj)Θ(zj , aj),
so that the quantity vπi,T ′(s) measures the expected cumulative return until the point T ′ <∞.
Hence, we deduce that
vπi (z) ≡ vπi,∞(z)
= vπi,T ′(z) + γ T ′µ(s0)π(a i 0, s0)π−i(a −i 0 , s0) T ′−1∏ j=0 ∑ sj+1∈S γtP (sj+1; sj , aj)π(a i j |sj)π−i(a−ij |sj)v π i (sT ′).
Next we observe that:
c = Es∼P [( vπ,π 2 i − v π′,π2 i ) (z) ] − Es∼P [( Bπ,π 2 −Bπ ′,π2 ) (z) ]
= Es∼P [( vπ,π 2 i,T ′ − v π′,π2 i,T ′ ) (z) ] − Es∼P [( Bπ,π 2 T ′ −B π′,π2 T ′ ) (s) ]
+γT ′ EsT ′∼P [ µ(s0)π(a i 0, s0)π−i(a −i 0 , s0) T ′−1∏ j=0 ∑ sj+1∈S P (sj+1; sj , aj)π(a i j |sj)π−i(a−ij |sj) ( vπ,π 2 i (zT ′)−B π,π2(zT ′) )
− µ(s0)π′i(a′i0 , s0)π−i(a−i0 , s0) T ′−1∏ j=0 ∑ sj+1∈S P (sj+1; sj , a ′ j)π ′ i(a ′i j |sj)π−i(a−ij |sj) ( vπ ′,π2 i (zT ′)−B π′,π2(zT ′) )] .
Considering the last expectation and its coefficient and denoting the product by κ, using the fact that by the Cauchy-Schwarz inequality we have ‖AX − BY ‖ ≤ ‖A‖‖X‖ + ‖B‖‖Y ‖, moreover whenever A,B are non-expansive we have that ‖AX − BY ‖ ≤ ‖X‖ + ‖Y ‖, hence we observe the following κ ≤ ‖κ‖ ≤ 2γT ′ (‖vi‖+ ‖B‖). Since we can choose T ′ freely and γ ∈]0, 1[, we can choose T ′ to be sufficiently large so that γT
′ (‖vi‖+ ‖B‖) < 14 |c|. This then implies that∣∣∣∣∣Es∼P [( vπ,π 2 i,T ′ − v π′,π2 i,T ′ ) (z)− ( Bπ,π 2 T ′ −B π′,π2 T ′ ) (z) ]∣∣∣∣∣ > 12c, which is a contradiction since we have proven that for any finite T ′ it is the case that
Es∼P [( vπ,π 2 i,T ′ − v π′,π2 i,T ′ ) (z)− ( Bπ,π 2 T ′ −B π′,π2 T ′ ) (z) ] = 0,
and hence we deduce the result in the infinite horizon case.
PROOF OF PART III
We begin by recalling that a Markov strategy is a policy πi : S ×Ai → [0, 1] which requires as input only the current system state (and not the game history or the other player’s action or strategy [22]). With this, we give a formal description of the stable points of G in Markov strategies.
Definition 3 A policy profile π̂ = (π̂1, π̂2) ∈ Π is a Markov perfect equilibrium (MPE) if the following holds ∀i 6= j ∈ {1, 2}, ∀π̂′ ∈ Πi: v(π̂ i,π̂j) i (s0, I0) ≥ v (π̂′,π̂j) i (s0, I0),∀(s0, I0) ∈ S × {0, 1}. The MPE describes a configuration in 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 at all).

heading: PROOF OF PROPOSITION 3
text: Proof 7 We do the proof by contradiction. Let σ = (π, g) ∈ arg sup π′∈Π,g′
Bπ ′,g′(s) for any s ∈ S . Let us
now therefore assume that σ /∈ NE{G}, hence there exists some other strategy profile σ̃ = (g, π̃) for which Controller has a profitable deviation where π′ 6= π i.e. vπ ′,π2
1 (s) > v π,π2
1 (s) (using the preservation of signs of integration). Prop. 4 however implies that Bπ
′,π2(s)−Bπ,π2(s) > 0 which is a contradiction since σ = (π, g) is a 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 1.

heading: PROOF OF PROPOSITION 2
text: Proof 8 (Proof of Prop. 2) The proof is given by establishing a contradiction. Therefore suppose thatMπ,π2ψ(sτk , I(τk)) ≤ ψ(sτk , I(τk)) and suppose that the intervention time τ ′1 > τ1 is an optimal intervention time. Construct the Player 2 π′2 ∈ Π2 and π̃2 policy switching times by (τ ′0, τ ′1, . . . , ) and π′2 ∈ Π2 policy by (τ ′0, τ1, . . .) respectively. Define by l = inf{t > 0;Mπ,π 2
ψ(st, I0) = ψ(st, I0)} and m = sup{t; t < τ ′1}. By construction we have that
vπ 1,π′2
2 (s, I0) = E [ R(s0, a0) + E [ . . .+ γl−1E [ R(sτ1−1, aτ1−1) + . . .+ γ m−l−1E [ R(sτ ′1−1, aτ ′1−1) + γM π1,π′2vπ 1,π′2 2 (s ′, I(τ ′1)) ]]]]
< E [ R(s0, a0) + E [ . . .+ γl−1E [ R(sτ1−1, aτ1−1) + γMπ 1,π̃2vπ 1,π′2 2 (sτ1 , I(τ1)) ]]]
We now use the following observation E [ R(sτ1−1, aτ1−1) + γMπ 1,π̃2vπ 1,π′2 2 (sτ1 , I(τ1)) ]
≤ max { Mπ1,π̃2vπ 1,π′2
2 (sτ1 , I(τ1)), max aτ1∈A
[ R(sτk , aτk) + γ ∑ s′∈S P (s ′; aτ1 , sτ1)v π1,π2 2 (s ′, I(τ1)) ]} .
Using this we deduce that
vπ 1,π′2
2 (s, I0) ≤ E [ R(s0, a0) + E [ . . .
+ γl−1E [ R(sτ1−1, aτ1−1) + γmax { Mπ 1,π̃2vπ 1,π′2
2 (sτ1 , I(τ1)), max aτ1∈A
[ R(sτk , aτk) + γ ∑ s′∈S P (s′; aτ1 , sτ1)v π1,π2 2 (s ′, I(τ1)) ]}]]] = E [ R(s0, a0) + E [ . . .+ γl−1E [ R(sτ1−1, aτ1−1) + γ [ Tvπ 1,π̃2 2 ] (sτ1 , I(τ1)) ]]] = vπ 1,π̃2 2 (s, I0)),
where the first inequality is true by assumption onM. This is a contradiction since π′2 is an optimal policy for Player 2. Using analogous reasoning, we deduce the same result for τ ′k < τk after which deduce the result. Moreover, by invoking the same reasoning, we can conclude that it must be the case that (τ0, τ1, . . . , τk−1, τk, τk+1, . . . , ) are the optimal switching times.

heading: PROOF OF THEOREM 2
text: To prove the theorem, we make use of the following result:
Theorem 3 (Theorem 1, pg 4 in [18]) Let Ξt(s) be a random process that takes values in Rn and given by the following:
Ξt+1(s) = (1− αt(s)) Ξt(s)αt(s)Lt(s), (63)
then Ξt(s) converges to 0 with probability 1 under the following conditions: i) 0 ≤ αt ≤ 1, ∑ t αt =∞ and ∑ t αt <∞
ii) ‖E[Lt|Ft]‖ ≤ γ‖Ξt‖, with γ < 1;
iii) Var [Lt|Ft] ≤ c(1 + ‖Ξt‖2) for some c > 0.
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:
Qt+1(st, It, at) = Qt(st, It, at)
+ αt(st, It, at)
[ max { Mπ,π 2
Q(sτk , Iτk , a), φ(sτk , a) + γmax a′∈A
Q(s′, Iτk , a ′) } −Qt(st, It, at) ] .
After subtracting Q?(st, It, at) from both sides and some manipulation we obtain that:
Ξt+1(st, It, at)
= (1− αt(st, It, at))Ξt(st, It, at)
+ αt(st, It, at))
[ max { Mπ,π 2
Q(sτk , Iτk , a), φ(sτk , a) + γmax a′∈A
Q(s′, Iτk , a ′) } −Q?(st, It, at) ] ,
where Ξt(st, It, at) := Qt(st, It, at)−Q?(st, It, at). Let us now define by
Lt(sτk , Iτk , a) := max
{ Mπ,π 2
Q(sτk , Iτk , a), φ(sτk , a) + γmax a′∈A
Q(s′, Iτk , a ′) } −Q?(st, It, a).
Then
Ξt+1(st, It, at) = (1− αt(st, It, at))Ξt(st, It, at) + αt(st, It, at)) [Lt(sτk , a)] . (64)
We now observe that
E [Lt(sτk , Iτk , a)|Ft] = ∑ s′∈S P (s′; a, sτk) max { Mπ,π 2 Q(sτk , Iτk , a), φ(sτk , a) + γmax a′∈A Q(s′, Iτk , a ′) } −Q?(sτk , a)
= TφQt(s, Iτk , a)−Q?(s, Iτk , a). (65)
Now, using the fixed point property that implies Q? = TφQ?, we find that
E [Lt(sτk , Iτk , a)|Ft] = TφQt(s, Iτk , a)− TφQ?(s, Iτk , a) ≤ ‖TφQt − TφQ?‖ ≤ γ ‖Qt −Q?‖∞ = γ ‖Ξt‖∞ . (66)
using the contraction property of T established in Lemma 3. This proves (ii).
We now prove iii), that is
Var [Lt|Ft] ≤ c(1 + ‖Ξt‖2). (67)
Now by (65) we have that Var [Lt|Ft] = Var [ max { Mπ,π 2
Q(sτk , Iτk , a), φ(sτk , a) + γmax a′∈A
Q(s′, Iτk , a ′) } −Q?(st, It, a) ] = E [( max { Mπ,π 2
Q(sτk , Iτk , a), φ(sτk , a) + γmax a′∈A
Q(s′, Iτk , a ′)
}
−Q?(st, It, a)− (TΦQt(s, Iτk , a)−Q?(s, Iτk , a))
)2]
= E [( max { Mπ,π 2
Q(sτk , Iτk , a), φ(sτk , a) + γmax a′∈A
Q(s′, Iτk , a ′) } − TΦQt(s, Iτk , a) )2]
= Var [ max { Mπ,π 2
Q(sτk , Iτk , a), φ(sτk , a) + γmax a′∈A
Q(s′, Iτk , a ′) } − TΦQt(s, Iτk , a))2 ] ≤ c(1 + ‖Ξt‖2),
for some c > 0 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.

heading: PROOF OF CONVERGENCE WITH LINEAR FUNCTION APPROXIMATION
text: First let us recall the statement of the theorem:
Theorem 3 ROSA converges to a limit point r? which is the unique solution to the equation:
ΠF(Φr?) = Φr?, a.e. (68)
where we recall that for any test function Λ ∈ V , the operator F is defined by FΛ := Θ + γP max{MΛ,Λ}. Moreover, r? satisfies the following:
‖Φr? −Q?‖ ≤ c ‖ΠQ? −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:
Lemma 4 For any Q ∈ V we have that
‖FQ−Q′‖ ≤ γ ‖Q−Q′‖ , (70)
so that the operator F is a contraction.
Proof 10 Recall, for any test function ψ , a projection operator Π acting Λ is defined by the following
ΠΛ := arg min Λ̄∈{Φr|r∈Rp} ∥∥Λ̄− Λ∥∥ . Now, we first note that in the proof of Lemma 3, we deduced that for any Λ ∈ L2 we have that∥∥∥∥MΛ− [ψ(·, a) + γmaxa∈A PaΛ′
]∥∥∥∥ ≤ γ ‖Λ− Λ′‖ , (c.f. Lemma 3). Setting Λ = Q and ψ = Θ, it can be straightforwardly deduced that for any Q, Q̂ ∈ L2:∥∥∥MQ− Q̂∥∥∥ ≤ γ ∥∥∥Q− Q̂∥∥∥. Hence, using the contraction property of M, we readily deduce the following bound:
max {∥∥∥MQ− Q̂∥∥∥ ,∥∥∥MQ−MQ̂∥∥∥} ≤ γ ∥∥∥Q− Q̂∥∥∥ , (71)
We now observe that F is a contraction. Indeed, since for any Q,Q′ ∈ L2 we have that:
‖FQ− FQ′‖ = ‖Θ + γP max{MQ,Q} − (Θ + γP max{MQ′, Q′})‖ = γ ‖P max{MQ,Q} − P max{MQ′, Q′}‖ ≤ γ ‖max{MQ,Q} −max{MQ′, Q′}‖ ≤ γ ‖max{MQ−MQ′, Q−MQ′,MQ−Q′, Q−Q′}‖ ≤ γmax{‖MQ−MQ′‖ , ‖Q−MQ′‖ , ‖MQ−Q′‖ , ‖Q−Q′‖} = γ ‖Q−Q′‖ ,
using (71) and again using the non-expansiveness of P .
We next show that the following two bounds hold:
Lemma 5 For any Q ∈ V we have that i) ∥∥ΠFQ−ΠFQ̄∥∥ ≤ γ ∥∥Q− Q̄∥∥,
ii) ‖Φr? −Q?‖ ≤ 1√ 1−γ2 ‖ΠQ? −Q?‖.
Proof 11 The first result is straightforward since as Π is a projection it is non-expansive and hence:∥∥ΠFQ−ΠFQ̄∥∥ ≤ ∥∥FQ− FQ̄∥∥ ≤ γ ∥∥Q− Q̄∥∥ , using the contraction property of F. This proves i). For ii), we note that by the orthogonality property of projections we have that 〈Φr? −ΠQ?,Φr? −ΠQ?〉, hence we observe that:
‖Φr? −Q?‖2 = ‖Φr? −ΠQ?‖2 + ‖Φr? −ΠQ?‖2
= ‖ΠFΦr? −ΠQ?‖2 + ‖Φr? −ΠQ?‖2
≤ ‖FΦr? −Q?‖2 + ‖Φr? −ΠQ?‖2
= ‖FΦr? − FQ?‖2 + ‖Φr? −ΠQ?‖2
≤ γ2 ‖Φr? −Q?‖2 + ‖Φr? −ΠQ?‖2 ,
after which we readily deduce the desired result.
Lemma 6 Define the operator H by the following: HQ(z) = { MQ(z), ifMQ(z) > Φr?, Q(z), otherwise,
and F̃ by: F̃Q := Θ + γPHQ.
For any Q, Q̄ ∈ L2 we have that ∥∥∥F̃Q− F̃Q̄∥∥∥ ≤ γ ∥∥Q− Q̄∥∥ (72) and hence F̃ is a contraction mapping.
Proof 12 Using (71), we now observe that∥∥∥F̃Q− F̃Q̄∥∥∥ = ∥∥Θ + γPHQ− (Θ + γPHQ̄)∥∥ ≤ γ
∥∥HQ−HQ̄∥∥ ≤ γ
∥∥max{MQ−MQ̄,Q− Q̄,MQ− Q̄,MQ̄−Q}∥∥ ≤ γmax
{∥∥MQ−MQ̄∥∥ ,∥∥Q− Q̄∥∥ ,∥∥MQ− Q̄∥∥ ,∥∥MQ̄−Q∥∥} ≤ γmax { γ ∥∥Q− Q̄∥∥ ,∥∥Q− Q̄∥∥ ,∥∥MQ− Q̄∥∥ ,∥∥MQ̄−Q∥∥}
= γ ∥∥Q− Q̄∥∥ ,
again using the non-expansive property of P .
Lemma 7 Define by Q̃ := Θ + γPvπ̃ where
vπ̃(z) := Θ(sτk , a) + γmax a∈A ∑ s′∈S P (s′; a, sτk)Φr ?(s′, I(τk)), (73)
then Q̃ is a fixed point of F̃Q̃, that is F̃Q̃ = Q̃.
Proof 13 We begin by observing that HQ̃(z) = H ( Θ(z) + γPvπ̃ ) = { MQ(z), ifMQ(z) > Φr?, Q(z), otherwise,
= { MQ(z), ifMQ(z) > Φr?, Θ(z) + γPvπ̃, otherwise,
= vπ̃(z).
Hence,
F̃Q̃ = Θ + γPHQ̃ = Θ + γPvπ̃ = Q̃. (74)
which proves the result.
Lemma 8 The following bound holds:
E [ vπ̂(z0) ] − E [ vπ̃(z0) ] ≤ 2 [ (1− γ) √ (1− γ2) ]−1 ‖ΠQ? −Q?‖ . (75)
Proof 14 By definitions of vπ̂ and vπ̃ (c.f (73)) and using Jensen’s inequality and the stationarity property we have that,
E [ vπ̂(z0) ] − E [ vπ̃(z0) ] = E [ Pvπ̂(z0) ] − E [ Pvπ̃(z0) ] ≤ ∣∣E [Pvπ̂(z0)]− E [Pvπ̃(z0)]∣∣
≤ ∥∥Pvπ̂ − Pvπ̃∥∥ . (76)
Now recall that Q̃ := Θ + γPvπ̃ and Q? := Θ + γPvπ ?
, using these expressions in (76) we find that
E [ vπ̂(z0) ] − E [ vπ̃(z0) ] ≤ 1 γ ∥∥∥Q̃−Q?∥∥∥ .
Moreover, by the triangle inequality and using the fact that F(Φr?) = F̃(Φr?) and that FQ? = Q? and FQ̃ = Q̃ (c.f. (75)) we have that∥∥∥Q̃−Q?∥∥∥ ≤ ∥∥∥Q̃− F(Φr?)∥∥∥+ ∥∥∥Q? − F̃(Φr?)∥∥∥ ≤ γ
∥∥∥Q̃− Φr?∥∥∥+ γ ‖Q? − Φr?‖ ≤ 2γ
∥∥∥Q̃− Φr?∥∥∥+ γ ∥∥∥Q? − Q̃∥∥∥ , which gives the following bound:∥∥∥Q̃−Q?∥∥∥ ≤ 2 (1− γ)−1 ∥∥∥Q̃− Φr?∥∥∥ , from which, using Lemma 5, we deduce that
∥∥∥Q̃−Q?∥∥∥ ≤ 2 [(1− γ)√(1− γ2)]−1 ∥∥∥Q̃− Φr?∥∥∥, after which by (77), we finally obtain
E [ vπ̂(z0) ] − E [ vπ̃(z0) ] ≤ 2 [ (1− γ) √ (1− γ2) ]−1 ∥∥∥Q̃− Φr?∥∥∥ , as required.
Let us rewrite the update in the following way:
rt+1 = rt + γtΞ(wt, rt),
where the function Ξ : R2d × Rp → Rp is given by: Ξ(w, r) := φ(z) (Θ(z) + γmax {(Φr)(z′),M(Φr)(z′)} − (Φr)(z)) ,
for any w ≡ (z, z′) ∈ (N× S)2 where z = (t, s) ∈ N × S and z′ = (t, s′) ∈ N × S and for any r ∈ Rp. Let us also define the function Ξ : Rp → Rp by the following:
Ξ(r) := Ew0∼(P,P) [Ξ(w0, r)] ;w0 := (z0, z1).
Lemma 9 The following statements hold for all z ∈ {0, 1} × S:
i) (r − r?)Ξk(r) < 0, ∀r 6= r?,
ii) Ξk(r?) = 0.
Proof 15 To prove the statement, we first note that each component of Ξk(r) admits a representation as an inner product, indeed:
Ξk(r) = E [φk(z0)(Θ(z0) + γmax {Φr(z1),MΦ(z1)} − (Φr)(z0)] = E [φk(z0)(Θ(z0) + γE [max {Φr(z1),MΦ(z1)} |z0]− (Φr)(z0)] = E [φk(z0)(Θ(z0) + γP max {(Φr,MΦ)} (z0)− (Φr)(z0)] = 〈φk,FΦr − Φr〉 ,
using the iterated law of expectations and the definitions of P and F.
We now are in position to prove i). Indeed, we now observe the following: (r − r?) Ξk(r) = ∑ l=1 (r(l)− r?(l)) 〈φl,FΦr − Φr〉
= 〈Φr − Φr?,FΦr − Φr〉 = 〈Φr − Φr?, (1−Π)FΦr + ΠFΦr − Φr〉 = 〈Φr − Φr?,ΠFΦr − Φr〉 ,
where in the last step we used the orthogonality of (1 − Π). We now recall that ΠFΦr? = Φr? since Φr? is a fixed point of ΠF. Additionally, using Lemma 5 we observe that ‖ΠFΦr − Φr?‖ ≤ γ‖Φr − Φr?‖. With this we now find that
〈Φr − Φr?,ΠFΦr − Φr〉
= 〈Φr − Φr?, (ΠFΦr − Φr?) + Φr? − Φr〉 ≤ ‖Φr − Φr?‖ ‖ΠFΦr − Φr?‖ − ‖Φr? − Φr‖2
≤ (γ − 1) ‖Φr? − Φr‖2 ,
which is negative since γ < 1 which completes the proof of part i).
The proof of part ii) is straightforward since we readily observe that
Ξk(r ?) = 〈φl,FΦr? − Φr〉 = 〈φl,ΠFΦr? − Φ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 4 (Th. 17, p. 239 in [3]) Consider a stochastic process rt : R× {∞} × Ω→ Rk which takes an initial value r0 and evolves according to the following:
rt+1 = rt + αΞ(st, rt), (77)
for some function s : R2d × Rk → Rk and where the following statements hold:
1. {st|t = 0, 1, . . .} is a stationary, ergodic Markov process taking values in R2d
2. For any positive scalar q, there exists a scalar µq such that E [1 + ‖st‖q|s ≡ s0] ≤ µq (1 + ‖s‖q)
3. The step size sequence satisfies the Robbins-Monro conditions, that is ∑∞ t=0 αt =∞ and∑∞
t=0 α 2 t <∞
4. There exists scalars c and q such that ‖Ξ(w, r)‖ ≤ c (1 + ‖w‖q) (1 + ‖r‖) 5. There exists scalars c and q such that ∑∞ t=0 ‖E [Ξ(wt, r)|z0 ≡ z]− E [Ξ(w0, r)]‖ ≤
c (1 + ‖w‖q) (1 + ‖r‖)
6. There exists a scalar c > 0 such that ‖E[Ξ(w0, r)]− E[Ξ(w0, r̄)]‖ ≤ c‖r − r̄‖ 7. There exists scalars c > 0 and q > 0 such that∑∞ t=0 ‖E [Ξ(wt, r)|w0 ≡ w]− E [Ξ(w0, r̄)]‖ ≤ c‖r − r̄‖ (1 + ‖w‖q)
8. There exists some r? ∈ Rk such that Ξ(r)(r − r?) < 0 for all r 6= r? and s̄(r?) = 0.
Then rt converges to r? almost surely.
In order to apply the Theorem 4, we show that conditions 1 - 7 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 it remains to verify conditions 4-7 are met.
To prove 4, we observe that
‖Ξ(w, r)‖ = ‖φ(z) (Θ(z) + γmax {(Φr)(z′),MΦ(z′)} − (Φr)(z))‖ ≤ ‖φ(z)‖ ‖Θ(z) + γ (‖φ(z′)‖ ‖r‖+MΦ(z′))‖+ ‖φ(z)‖ ‖r‖ ≤ ‖φ(z)‖ (‖Θ(z)‖+ γ‖MΦ(z′)‖) + ‖φ(z)‖ (γ ‖φ(z′)‖+ ‖φ(z)‖) ‖r‖.
Now using the definition ofM, we readily observe that ‖MΦ(z′)‖ ≤ ‖Θ‖+ γ‖Pπs′stΦ‖ ≤ ‖Θ‖+ γ‖Φ‖ using the non-expansiveness of P . Hence, we lastly deduce that
‖Ξ(w, r)‖ ≤ ‖φ(z)‖ (‖Θ(z)‖+ γ‖MΦ(z′)‖) + ‖φ(z)‖ (γ ‖φ(z′)‖+ ‖φ(z)‖) ‖r‖ ≤ ‖φ(z)‖ (‖Θ(z)‖+ γ‖Θ‖+ γ‖ψ‖) + ‖φ(z)‖ (γ ‖φ(z′)‖+ ‖φ(z)‖) ‖r‖,
we then easily deduce the result using the boundedness of φ,Θ and ψ.
Now we observe the following Lipschitz condition on Ξ:
‖Ξ(w, r)− Ξ(w, r̄)‖ = ‖φ(z) (γmax {(Φr)(z′),MΦ(z′)} − γmax {(Φr̄)(z′),MΦ(z′)})− ((Φr)(z)− Φr̄(z))‖ ≤ γ ‖φ(z)‖ ‖max {φ′(z′)r,MΦ′(z′)} −max {(φ′(z′)r̄),MΦ′(z′)}‖+ ‖φ(z)‖ ‖φ′(z)r − φ(z)r̄‖ ≤ γ ‖φ(z)‖ ‖φ′(z′)r − φ′(z′)r̄‖+ ‖φ(z)‖ ‖φ′(z)r − φ′(z)r̄‖ ≤ ‖φ(z)‖ (‖φ(z)‖+ γ ‖φ(z)‖ ‖φ′(z′)− φ′(z′)‖) ‖r − r̄‖ ≤ c ‖r − r̄‖ ,
using Cauchy-Schwarz inequality and that for any scalars a, b, c we have that |max{a, b} −max{b, c}| ≤ |a− c|. Using Assumptions 3 and 4, we therefore deduce that ∞∑ t=0 ‖E [Ξ(w, r)− Ξ(w, r̄)|w0 = w]− E [Ξ(w0, r)− Ξ(w0, r̄)‖] ≤ c ‖r − r̄‖ (1 + ‖w‖l). (78)
Part 2 is assured by Lemma 5 while Part 4 is assured by Lemma 8 and lastly Part 8 is assured by Lemma 9.

heading: Rebuttal

heading: 17 ADDITIONAL EXPERIMENT 1 - REPLACING RND FOR BONUS REWARD
text: In this experiment we sought to ascertain if ROSA is robust to 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 a simple count-based measure 1Count(s) where s ∈ S (the function Count(s) simply tallies the number of times state s 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 a fine-tuned exploration bonus. The additional machinery of switching controls and choices of intrinsic rewards to 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 phi 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 a 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.

Review summaries:
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.

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.  

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). 

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.