summaries: This paper introduces a learned centralized exploration reward for multi-agent settings. The exploration reward is factorized into an on/off gate (dubbed ‘switching control’) and a scale function. Some mathematical derivations are included (sketched in the main text, with details in the appendices) to provide theoretical guarantees on how the exploration reward changes the solutions the training procedure might find. Evaluations on gridworld environments that target specific difficulties of multi-agent exploration show promising results. Some maps from the SMAC benchmark are also included, and again show good results.

summaries: This paper proposes a method, Learnable Intrinsic-reward Generation Selection (LIGS) to improve coordinated exploration. LIGS incorporates an extra agent, called Generator to learn what state to give what intrinsic reward for each agent. The intrinsic reward is potential-based, so it preserves the optimality. Experimental results on several domains show its advantages over several MARL methods.

summaries: The paper describes a novel reinforcement learning algorithm for multi-agent system (MARL) that employs a generator of intrinsic reward and a switching control system that helps to regulate intrinsic control. Crucially, the intrinsic reward is learned to better fit the particular task being learned. The paper claims that the proposed algorithm helps with exploration as well as preservation of known policies. The paper has a strong theoretical background with a section that illustrates the properties of convergence and optimality. The experimental results appear to justify the approach with superior performance with respect to the baselines. The paper deals with an emerging and interesting area of RL and proposes a new mechanism for co-ordinated RL agents.

summaries: The paper focuses on learning intrinsic rewards for multi-agent reinforcement learning, which is an important problem. Different from previous works on this topic, the authors propose to train an agent with a learnable gating function that incentives other agents. Theoretical analysis and empirical evaluation are provided to prove the effectiveness of the proposed method.

abstractText: Efficient exploration is important for reinforcement learners (RL) to achieve high rewards. In multi-agent systems, coordinated exploration and behaviour is critical for agents to jointly achieve optimal outcomes. In this paper, we introduce a new general framework for improving coordination and performance of multi-agent reinforcement learners (MARL). Our framework, named Learnable Intrinsic-Reward Generation Selection algorithm (LIGS) introduces an adaptive learner, Generator that observes the agents and learns to construct intrinsic rewards online that coordinate the agents’ joint exploration and joint behaviour. Using a novel combination of reinforcement learning (RL) and switching controls, LIGS determines the best states to learn to add intrinsic rewards which leads to a highly efficient learning process. LIGS can subdivide complex tasks making them easier to solve and enables systems of RL agents to quickly solve environments with sparse rewards. LIGS can seamlessly adopt existing multi-agent RL algorithms and our theory shows that it ensures convergence to joint policies that deliver higher system performance. We demonstrate the superior performance of the LIGS framework in challenging tasks in Foraging and StarCraft II.

authors:
E. Bayraktar
M. Egami

title: On the one-dimensional optimal switching problem

authors:
A. Benveniste
M. Métivier
P. Priouret

title: Adaptive algorithms and stochastic approxima

authors:
Y. 159–163. Burda
H. Edwards
A. Storkey
O. Klimov

title: Exploration by random network distillation

authors:
S. Devlin
D. Kudenko

title: Theoretical considerations of potential-based reward shaping

title: Plan-based reward shaping for multi-agent reinforcement learning

venue: Multiagent Systems,

authors:
S.M. Devlin
D. Kudenko

title: Dynamic potential-based reward shaping

authors:
A. Harutyunyan
S. Devlin
P. Vrancx
A. Nowé

title: Tirole: Game theory

venue: multi-agent policy gradients. Thirty-second AAAI conference on artificial intelligence. Fudenberg,

authors:
M. Hüttenrauch
A. Šošić
G. Neumann

title: Guided deep reinforcement learning for swarm

authors:
T. Jaakkola
M.I. Jordan
S.P. Singh

title: Convergence of stochastic iterative dynamic

authors:
A. Mahajan
T. Rashid
M. Samvelyan
S. Whiteson

title: Maven: Multi-agent variational

authors:
P. Mannion
S. Devlin
J. Duggan
E. Howley

title: Reward shaping for knowledge-based

authors:
P. Mannion
S. Devlin
K. Mason
J. Duggan
E. Howley

title: Policy invariance under reward

authors:
D. Mguni
J. Jennings
E. Sison
S. Valcarcel Macua
S. Ceppi
E. Munoz de Cote

title: Coordinating the crowd: Inducing desirable equilibria in non-cooperative systems

venue: Proceedings of the 18th international conference on autonomous agents and multiagent systems (pp. 386–394)

authors:
A.Y. Ng
D. Harada
S. Russell

title: Policy invariance under reward transformations: Theory and application to reward shaping

title: Stochastic differential equations. Stochastic differential equations (pp. 65–84)

authors:
G. Papoudakis
F. Christianos
L. Schäfer
S.V. Albrecht

title: Comparative evaluation of multi-agent deep reinforcement learning

authors:
D. Pathak
P. Agrawal
A.A. Efros
T. Darrell

title: Curiosity-driven exploration by selfsupervised prediction

venue: International conference on machine learning,

authors:
E. Pesce
G. Montana

title: Improving coordination in small-scale multi-agent deep reinforcement learning through memory-driven communication

venue: Machine Learning,

authors:
T. Rashid
M. Samvelyan
C. Schroeder
G. Farquhar
J. Foerster
S. Whiteson

title: Qmix: Monotonic value function factorisation for deep multi-agent reinforcement learning

venue: International Conference on Machine Learning,

authors:
T. Roughgarden
E. Tardos

title: Introduction to the inefficiency of equilibria

venue: Algorithmic game theory,

authors:
M. Sadeghlou
M.R. Akbarzadeh-T
M.B. Naghibi-S

title: Dynamic agent-based reward shaping for multi-agent systems

venue: Iranian Conference on Intelligent Systems (ICIS),

authors:
M. Samvelyan
T. Rashid
C.S. De Witt
G. Farquhar
N. Nardelli
T.G. Rudner
Hung
C.-M
P.H. Torr
J. Foerster
S. Whiteson

title: The starcraft multi-agent challenge

venue: arXiv preprint arXiv:1902.04043

authors:
J. Schulman
F. Wolski
P. Dhariwal
A. Radford
O. Klimov

title: Proximal policy optimization algorithms. CoRR, abs/1707.06347

authors:
Y. Shoham
K. Leyton-Brown

title: Multiagent systems: Algorithmic, game-theoretic, and logical foundations

authors:
K. Son
D. Kim
W.J. Kang
D.E. Hostallero
Y. Yi

title: Qtran: Learning to factorize with transformation for cooperative multi-agent reinforcement learning

authors:
P. Sunehag
G. Lever
A. Gruslys
W.M. Czarnecki
V. Zambaldi
M. Jaderberg
M. Lanctot
N. Sonnerat
J.Z. Leibo
K Tuyls

title: Value-decomposition networks for cooperative multi-agent learning. arXiv preprint arXiv:1706.05296

authors:
A.D. Tijsma
M.M. Drugan
M.A. Wiering

title: Comparing exploration strategies for q-learning in random stochastic mazes

venue: IEEE Symposium Series on Computational Intelligence (SSCI),

authors:
J.N. Tsitsiklis
B. Van Roy

title: Optimal stopping of markov processes: Hilbert space theory, approximation algorithms, and an application to pricing high-dimensional financial derivatives

venue: IEEE Transactions on Automatic Control,

authors:
A. Viseras
T. Wiedemann
C. Manss
L. Magel
J. Mueller
D. Shutin
L. Merino

title: Decentralized multi-agent exploration with online-learning of gaussian processes

venue: IEEE International Conference on Robotics and Automation (ICRA),

authors:
J. Wang
Z. Ren
B. Han
J. Ye
C. Zhang

title: Towards understanding linear value decomposition in cooperative multi-agent q-learning

venue: arXiv preprint arXiv:2006.00587

authors:
J. Wang
Z. Ren
T. Liu
Y. Yu
C. Zhang

title: Qplex: Duplex dueling multi-agent q-learning

venue: arXiv preprint arXiv:2008.01062

authors:
Y. Yang
J. Wang

title: An overview of multi-agent reinforcement learning from game theoretical perspective

venue: arXiv preprint arXiv:2011.00583

authors:
Y. Yang
Y. Wen
J. Wang
L. Chen
K. Shao
D. Mguni
W. Zhang

title: Multi-agent determinantal q-learning

authors:
C. Yu
A. Velu
E. Vinitsky
Y. Wang
A. Bayen
Y. Wu

title: The surprising effectiveness of mappo in cooperative, multi-agent games. arXiv preprint arXiv:2103.01955

authors:
Z. Zheng
J. Oh
S. Singh

title: On learning intrinsic rewards for policy gradient methods

venue: arXiv preprint arXiv:1804.06459

authors:
M. Zhou
Z. Liu
P. Sui
Y. Li
Y.Y. Chung

title: Learning implicit credit assignment for multi-agent actor-critic

venue: arXiv e-prints,

authors:
M. Zhou
J. Luo
J. Villella
Y. Yang
D. Rusu
J. Miao
W. Zhang
M. Alban
I. Fadakar
Z Chen

title: Smarts: Scalable multi-agent reinforcement learning training school for autonomous driving

venue: arXiv preprint arXiv:2010.09776

authors:
M. Zinkevich
A. Greenwald
M. Littman

title: Cyclic equilibria in markov games

venue: Advances in Neural Information Processing Systems,

venue: First recall v(s, I0),

heading: 1 INTRODUCTION

text:
Cooperative multi-agent reinforcement learning (MARL) has emerged as a powerful tool to enable autonomous agents to solve various tasks such as ride-sharing (Zhou, Luo, et al., 2020) and swarm robotics (Hüttenrauch et al., 2017; Mguni et al., 2018). In multi-agent systems (MAS), maximising system performance often requires agents to coordinate during exploration and learn coordinated joint actions (Matignon et al., 2012). However, in many MAS, the reward signal provided by the environment is not sufficient to guide the agents towards coordinated behaviour (Matignon et al., 2012). Consequently, relying on solely the individual rewards received by the agents may not lead to optimal outcomes (Mguni et al., 2019). This problem is worsened by the fact that MAS can have many stable points some of which lead to arbitrarily bad outcomes (Roughgarden & Tardos, 2007).
As in single agent RL, in MARL inefficient exploration can dramatically decrease sample efficiency. In MAS, a major challenge is how to overcome sample inefficiency from poorly coordinated exploration. Unlike single agent RL, in MARL, the collective of agents is typically required to coordinate its exploration to find their optimal joint policies1. A second issue is that in many MAS settings of interest, such as video games and physical tasks, rich informative signals of the agents’ joint performance are not readily available (Hosu & Rebedea, 2016). For example, in StarCraft Micromanagement (Samvelyan et al., 2019), the sparse reward alone (win, lose) gives insufficient information to guide agents toward their optimal joint policy. Consequently, MARL requires large numbers of samples producing a great need for MARL methods that can solve such problems efficiently.
To aid coordinated learning, algorithms such as QMIX (Rashid et al., 2018), MAVEN (Mahajan et al., 2019) and COMA (Foerster et al., 2018), so-called centralised critic and decentralised execution (CT-DE) methods use a centralised critic whose role is to estimate the agents’ expected returns. The critic makes use of all available information generated by the system, specifically the global state and the joint action. To enable effective CT-DE, it is critical that the joint greedy action
1In single agent RL exploration issues can be mitigated by adjusting exploration rates or the policy variance (Tijsma et al., 2016). However it has been shown that the same is not possible in MARL (Mahajan et al., 2019).
should be equivalent to the collection of individual greedy actions of agents, which is called the IGM (Individual-Global-Max) principle (Son et al., 2019). CT-DE methods are however, prone to convergence to suboptimal joint policies (Wang, Ren, Han, et al., 2020). In particular, existing value factorisations, e.g. QMIX and VDN (Sunehag et al., 2017), cannot ensure an exact guarantee of IGM consistency (Wang, Ren, Liu, et al., 2020). Moreover, CT-DE methods such as QMIX require a monotonicity condition which is violated in scenarios where multiple agents must coordinate but are penalised if only a subset of them do so (see Exp. 2, Sec. 6.1).
To tackle these issues, in this paper we introduce a new MARL framework, LIGS that constructs intrinsic rewards online which guide MARL learners towards their optimal joint policy. LIGS involves an adaptive intrinsic reward agent, Generator that selects intrinsic rewards to add according to the history of visited states and joint actions performed by the agents. Generator adaptively guides the agents’ exploration and behaviour towards coordination and maximal joint performance. A pivotal feature of LIGS is the novel combination of RL and switching controls (Bayraktar & Egami, 2010; Mguni, 2018) which enables it to determine the best set of states to learn to add intrinsic rewards while disregarding less useful states. This enables Generator to quickly learn how to set intrinsic rewards that guide the agents during their learning process. Moreover, the intrinsic rewards added by Generator can significantly deviate from the environment rewards. This enables LIGS to both promote complex joint exploration patterns and decompose difficult tasks. Despite this flexibility, special features within LIGS ensure the underlying optimal policies are preserved so that the agents learn to solve the task at hand.
Overall, LIGS has several advantages: • LIGS has the freedom to introduce rewards that vastly deviate from the environment rewards. With this, LIGS promotes coordinated exploration (i.e. visiting unplayed state-joint actions) among the agents enabling them to find joint policies that maximise the system rewards and generates intrinsic rewards to aid solving sparse reward MAS. • LIGS selects which best states to add intrinsic rewards adaptively in response to the agents’ behaviour while the agents learn leading to an efficient learning process. • LIGS’s intrinsic rewards preserve the agents’ optimal joint policy and ensure that the total environment return is (weakly) increased.
To enable the framework to perform successfully, we overcome several challenges: i) Firstly, constructing an intrinsic reward can change the underlying problem leading to the agents solving irrelevant tasks (Mannion et al., 2017). We resolve this by endowing the intrinsic reward function with special form which both allows a rich spread of intrinsic rewards while preserving the optimal policy. ii) Secondly, introducing intrinsic reward functions can worsen the agents’ performance (S. Devlin & Kudenko, 2011) and doing so while training can lead to convergence issues. We prove LIGS leads to better performing policies and that LIGS’s learning process converges and preserves the MARL learners’ convergence properties. iii) Lastly, adding an agent Generator with its own goal leads to a Markov game (MG) with N + 1 agents (Fudenberg & Tirole, 1991). Tractable methods for solving MGs are extremely rare with convergence only in special cases (Yang & Wang, 2020). Nevertheless, using a special set of features in LIGS’s design, we prove LIGS converges to a solution in which it learns an intrinsic reward function that improves the agents’ performance.

heading: 2 RELATED WORK

text:
Multi-agent exploration methods seek to promote coordinated exploration among MARL learners. Maven et. al (Mahajan et al., 2019) propose a hybridisation of value and policy-based methods that uses mutual information to learn a diverse set of behaviours between agents. Though this approach promotes coordinated exploration, it does not encourage exploration of novel states. Other approaches to promote exploration in MARL while assuming aspects of the environment are known in advance and agents can perform perfect communication between themselves (Viseras et al., 2016). Similarly, to promote coordinated exploration in partially observable settings, (Pesce & Montana, 2020) propose end-to-end learning of a communication protocol through a memory device. In general, exploration-based methods provide no performance guarantees nor do they ensure the optimal policy (of the underlying dec-MDP) is preserved. Moreover, many employ heuristics that naively reward exploration to unvisited states without consideration of the environment reward. This can lead to spurious objectives being maximised.
Reward shaping (Harutyunyan et al., 2015) (RS) is a technique which aims to alleviate the problem of sparse and uninformative rewards by supplementing the agent’s reward with a prefixed term F . In (Ng et al., 1999) it was established that adding a shaping reward function of the form F (st+1, st) = γφ(st+1)−φ(st) preserves the optimal policy and in some cases can aid learning. RS has been extended to MAS (S. Devlin & Kudenko, 2011, 2016; S. Devlin et al., 2011; S. M. Devlin & Kudenko, 2012; Mannion et al., 2018; Sadeghlou et al., 2014) in which it is used to promote convergence to efficient social welfare outcomes. Poor choices of F in a MAS can slow the learning process and can induce convergence to poor system performance (S. Devlin & Kudenko, 2011). In MARL, the question of which shaping function to use remains unaddressed. Typically, RS algorithms rely on hand-crafted shaping reward functions that are constructed using domain knowledge, contrary to the goal of autonomous learning (S. Devlin & Kudenko, 2011). As we later describe LIGS, which successfully learns an instrinsic reward function F , uses a similar form as PBRS however, F is now augmented to include the actions of another RL agent to learn the intrinsic rewards online. In (Du et al., 2019) an approach towards learning intrinsic rewards is proposed in which a parameterised intrinsic reward is learned using a bilevel approach through a centralised critic. Loosely related are single-agent methods (Dilokthanakul et al., 2019; Kulkarni et al., 2016; Pathak et al., 2017; Zheng et al., 2018) which, in general, introduce heuristic terms to generate intrinsic rewards.
Within these categories, closest to our work is the intrinsic reward approach in (Du et al., 2019). There, the agents’ policies and intrinsic rewards are learned with a bilevel approach. In contrast, LIGS performs these operations concurrently leading to a faster, more efficient procedure. A crucial point of distinction is that in LIGS, the intrinsic rewards are constructed by an RL agent (Generator) with its own reward function. Consequently, LIGS can generate complex patterns of intrinsic rewards, encourage joint exploration. Additionally, LIGS learns intrinsic rewards only at relevant states, this confers high computational efficiency. Lastly, unlike exploration-based methods e.g., (Mahajan et al., 2019), LIGS ensures preservation of the agents’ joint optimal policy for the task.

heading: 3 PRELIMINARIES

text:
A fully cooperative MAS is modelled by a decentralised-Markov decision process (dec-MDP) (Yang & Wang, 2020). A dec-MDP is an augmented MDP involving a set of N ≥ 2 agents denoted by N that independently decide actions to take which they do so simultaneously over many rounds. Formally, a dec-MDP is a tuple M = 〈N ,S, (Ai)i∈N , P,R, γ〉 where S is the finite set of states, Ai is an action set for agent i ∈ N and R : S ×A→ P(D) is the reward function that all agents jointly seek to maximise where D is a compact subset of R and lastly, P : S ×A×S → [0, 1] is the probability function describing the system dynamics where A := ×Ni=1Ai. Each agent i ∈ N uses a Markov policy πi : S ×Ai → [0, 1] to select its actions. At each time t ∈ 0, 1, . . . , the system is in state st ∈ S and each agent i ∈ N takes an action ait ∈ Ai. The joint action at = (a1t , . . . , aNt ) ∈ A produces an immediate reward ri ∼ R(st,at) for agent i ∈ N and influences the next-state transition which is chosen according to P . The goal of each agent i is to maximise its expected returns measured by its value function vπ i,π−i(s) = Eπi,π−i [ ∑∞ t=0 γ
tR(st,at)], where Πi is a compact Markov policy space and −i denotes the tuple of agents excluding agent i. Intrinsic rewards can strongly induce more efficient learning (and can promote convergence to higher performing policies) (S. Devlin & Kudenko, 2011). We tackle the problem of how to learn intrinsic rewards produced by a function F ? that leads to the agents learning policies that jointly maximise the system performance (through coordinated learning). Naturally, the problem of learning F ? can be approached by optimising the input θ ∈ Rm of a parameteric function: F̂ (s,a;θ); that is, finding θ? ∈ Rm for which F ?(s,a) = F̂ (s,a,θ?) given an intrinsic reward F̂ where s is the state and a is the agents’ joint action. Determining this function is a significant challenge since poor choices can hinder learning and the concurrency of multiple learning processes presents potential convergence issues in a system already populated by multiple learners (Zinkevich et al., 2006). Additionally, we require that the method preserves the optimal joint policy and the underlying dec-MDP. Note that using an optimisation procedure to find θ? directly does not make use of information generated by intermediate state-joint-action-reward tuples of the RL problem which can guide the optimisation.

heading: 4 THE LIGS FRAMEWORK

text:
We now describe the details of the LIGS framework and how it learns intrinsic rewards that improve learning and team performance. We then describe the agents’ objectives and their learning processes.
To tackle the challenges described above, we introduce Generator an adaptive agent with its own objective that determines the best intrinsic rewards to give to the agents at each state. Using observations of the joint actions played by the N agents, the goal of Generator is to construct intrinsic rewards (which the N MARL learners cannot generate themselves) to coordinate exploration and guide the agents towards learning joint policies that maximise their shared rewards. To do this, Generator learns how to choose the values of an intrinsic reward function F θ at each state. Simultaneously, the N agents perform actions to maximise their rewards using their individual policies. The objective for each agent i ∈ {1, . . . , N} is given by:
vπ i,π−i,g(s) = E [ ∞∑ t=0 γt ( R+ F θ ) ∣∣∣s0 = s] , where θ is determined by Generator using the policy g : S ×Θ→ [0, 1] and Θ ⊂ Rp is Generator’s action set. The intrinsic reward function is given by F θ(·) ≡ φ(st, θct )− γ−1φ(st−1, θct−1) for any st, st−1 ∈ S where θct ∼ g is the action chosen by Generator and θct ≡ 0,∀t < 0. The function φ : S ×Θ→ R is a continuous map that satisfies the condition φ(s, 0) ≡ 0, ∀s ∈ S (for example, φ can be a neural network with fixed weights with input (s, θc) and Θ can be a set of integers {1, . . . ,K}). Therefore, Generator determines the output of F θ (which it does through its choice of θc). With this, Generator constructs intrinsic rewards that are tailored for the specific setting.
As the agent i ∈ N policy can be learned using any MARL method, LIGS freely adopts any MARL algorithm for the N agents (see Sec. 9 in the Supp. Material). The transition probability P : S ×A × S → [0, 1] takes the state and only the actions of the N agents as inputs. Note that unlike reward-shaping methods e.g. (Ng et al., 1999), the function φ now contains an action term θc which is chosen by Generator which enables the intrinsic reward function to be learned online. The presence of the action θc term may spoil the policy invariance result in (Ng et al., 1999). We however prove a policy invariance result (Prop. 1) analogous to that in (Ng et al., 1999) which shows LIGS preserves the optimal policy of M. Generator is an RL agent whose objective takes into account the history of states and N agents’ joint actions. Define by Rθ(s,a) := R(s,a) + F θ Generator’s objective is:
vπ,gc (s) = Eπ,g [ ∞∑ t=0 γt ( Rθ(st,at) + L(st,at) ) ∣∣∣s0 = s] , ∀s ∈ S. (1) The objective encodes Generator’s agenda, namely to maximise the agents’ joint expected return. Therefore, using its intrinsic rewards, Generator seeks to guide the set of agents toward optimal joint trajectories (potentially away from suboptimal trajectories, c.f. Experiment 2) and enables the agents to learn faster (c.f. StarCraft experiments in Sec. 6). Lastly, L : S ×A → R rewards Generator when the agents jointly visit novel state-joint-action tuples and tends to 0 as the tuples are revisited. We later prove that with this objective, Generator’s optimal policy (for constructing the intrinsic rewards) maximises the expected team (extrinsic) return (Prop. 1).
Since Generator has its own (distinct) objective, the resulting setup is an MG, G = 〈N × {c},S, (Ai)i∈N ,Θ, P,Rθ, Rc, γ〉 where the new elements are {c}, Generator agent, Rθ := R+F θ , the new team reward function which contains the intrinsic reward F θ, Rc : S × A × Θ → R, the one-step reward for Generator (we give the details of this later). The transition probability P : S ×A× S → [0, 1] takes the state and only the N agents joint action as inputs.

heading: Switching Control Mechanism

text:
So far Generator’s problem involves learning to construct intrinsic rewards at every state which can be computationally expensive. We now introduce an important feature to the framework with which it only learns the best intrinsic reward in a subset of states in which intrinsic rewards are most useful. This is in contrast to the problem tackled by the N agents who must compute their optimal actions at all states. To achieve this, we now replace Generator’s policy space with a form of policies known as switching controls. These policies enable Generator to decide at which states to learn the value of
intrinsic rewards. This enables Generator to learn quickly both where to add intrinsic rewards and the magnitudes that improve performance since Generator’s magnitude optimisations are performed only at a subset of states. Crucially, with this Generator can learn its policy rapidly enabling it to guide the agents toward coordination and higher performing policies while they train.
At each state Generator first makes a binary decision to decide to switch on its F for agent i ∈ N using a switch It which takes values in {0, 1}. Crucially, now Generator is tasked with learning how to construct the N agents’ intrinsic rewards only at states that are important for guiding the agents to their joint optimal policy. Both the decision to activate the function F and its magnitudes is determined by Generator. With this, the agent i ∈ N objective becomes:
vπ,g(s0, I0) = E [ ∞∑ t=0 γt { R+ F θ · It }] , ∀(s0, I0) ∈ S × {0, 1}, (2)
where Iτk+1 = 1− Iτk , which is the switch for the function F which is 0 or 1 and {τk}k>0 are times that a switch takes place 2 so for example if the switch is first turned on at the state s5 then turned off at s7, then τ1 = 5 and τ2 = 7 (we will shortly describe these in more detail). At any state, the decision to turn on I is decided by a (categorical) policy gc : S → {0, 1} which acts according to Generator’s objective. In particular, first, Generator makes an observation of the state sk ∈ S and the joint action ak and using gc, Generator decides whether or not to activate the policy g to provide an intrinsic reward whose value is determined by θck ∼ g. With this it can be seen the sequence of times {τk} is τk = inf{t > τk−1|st ∈ S, gc(st) = 1} so the switching times. {τk} are rules that depend on the state. Therefore, by learning an optimal gc, Generator learns the useful states to switch on F .
As we later describe, the termination times occur according to some external (probabilistic) rule. To induce Generator to selectively choose when to switch on the additional rewards, each switch activation incurs a fixed cost for Generator. In this case, the objective for Generator is:
vπ,gc (s0, I0) = Eπ,g  ∞∑ t=0 γt Rθ(st,at) +∑ k≥1 c(It, It−1)δ t τ2k−1 + L(st,at)  , (3) where the new term c : {0, 1}2 → R<0 is a strictly negative cost function which imposes a cost for each switch activation and is modulated by the Kronecker-delta function δtτ2k−1 which is 1 whenever t = τ2k−1 and 0 otherwise. The cost has two effects: first, it reduces the computational complexity of Generator’s problem since Generator now determines subregions of S it should learn the values of F . Second, it ensures the information-gain from encouraging the agents to explore a given set of state-action tuples is sufficiently high to merit activating a stream of intrinsic rewards. We set τ0 ≡ 0, θτk ≡ 0,∀k ∈ N (θτk+1, . . . , θτk+1−1 remain non-zero), θck ≡ 0 ∀k ≤ 0 and denote by I(t) ≡ It. There are various possibilities for the termination times {τ2k} (recall that {τ2k+1} are the times which the intrinsic reward F is switched on) using gc. One is for the terminations to occur randomly. 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. 14 of the Appendix.

heading: Summary of Events

heading: At a time t ∈ 0, 1, . . .

text:
1. The N agents makes an observation of the state st ∈ S. 2. The N agents perform a joint action at = (a1t , . . . , a N t ) sampled from π = (π
1, . . . , πN ). 3. Generator makes an observation of st and at and draws samples from its polices (gc, g). 4. If gc(st) = 0:
X◦ Each agent i ∈ N receives a reward ri ∼ R(st,at) and the system transitions to the next state st+1 and steps 1 - 3 are repeated.
5. If gc(st) = 1: X◦ F θ is computed using st, at and the Generator action θc ∼ g. X◦ Each agent i ∈ N receives a reward ri + F θ and the system transitions to st+1. 6. At time t+1 if the intrinsic reward terminates then steps 1 - 3 are repeated or if the intrinsic reward has not terminated then step 5 is repeated.
2More precisely, {τk}k≥0 are stopping times (Øksendal, 2003).

heading: 4.1 THE LEARNING PROCEDURE

text: In Sec. 5, we provide the convergence properties of the algorithm, and give the full code of the algorithm in Sec. 8 of the Appendix. The algorithm consists of the following procedures: Generator updates its policy that determines the values θ at each state and the states to perform a switch while the agents {1, . . . , N} learn their individual policies {π1, . . . , πN}. In our implementation, we used proximal policy optimization (PPO) (Schulman et al., 2017) as the learning algorithm for both Generator’s intervention policy gc and Generator’s policy g. For the N agents we used MAPPO (Yu et al., 2021). For Generator L term we use3 L(st,at) := ‖ĥ − h‖22 where ĥ is a random initialised network which is the target network which is fixed and h is the prediction function that is consecutively updated during training. We constructed F̂ using a fixed neural network f : Rd 7→ Rm and a one-hot encoding of the action of Generator. Specifically, φ(st, θct ) := f(st) · i(θct ) where i(θct ) is a one-hot encoding of the action θ c t picked by Generator. Thus, F̂ (st, θct ; st−1, θct−1) = f(st) · i(θct )− γ−1f(st−1) · i(θct−1). The action set of Generator is Θ := {0, 1, ...,m} where each element is drawn from N, and g is an MLP g : Rd 7→ Rm. Extra details are Sec. 8 of the Appendix.

heading: 5 CONVERGENCE AND OPTIMALITY OF LIGS

text:
We now show that LIGS converges and that the solution ensures a higher performing agent policies than what would be achieved by solving M directly. The addition of Generator’s RL process which modifies N agents’ rewards during learning can produce convergence issues (Zinkevich et al., 2006). Also to ensure the framework is useful, we must verify that the solution of G corresponds to solving the MDP, M. To resolve these issues, we first study the stable point solutions of G. Unlike MDPs, the existence of a solution in Markov policies is not guaranteed for MGs (Blackwell & Ferguson, 1968) and is rarely computable (except for special cases such as team and zero-sum MGs (Shoham & Leyton-Brown, 2008)). MGs also often have multiple stable points that can be inefficient (Mguni et al., 2019); in G such stable points would lead to a poor performing agent joint policy. We resolve these challenges with the following scheme:
[I] LIGS preserves the optimal solution of M. [II] The MG induced by LIGS has a stable point which is the convergence point of MARL. [III] LIGS yields a team payoff that is (weakly) greater than that from solving M directly. [IV] LIGS converges to the solution with a linear function approximators.
In what follows, we denote by Π := ×i∈NΠi. The results are built under Assumptions 1 - 7 (Sec. 15 of the Appendix) which are standard in RL and stochastic approximation theory. We now prove the result [I] which shows the solution to M is preserved under the influence of LIGS:
Proposition 1 The following statements hold:
i) max π∈Π vπ,g(s, ·) = max π∈Π
vπ(s), ∀s ∈ S,∀i ∈ N ,∀g where vπ(s) = Eπ [ ∑∞ t=0 γ tR].
ii) The Generator’s optimal policy maximises vπ(s) = E [ ∑∞ t=0 γ tR(st,at)] for any s ∈ S.
Result (i) says that the agents’ problem is preserved under Generator’s influence. Moreover the agents’ (expected) total return is that from the environment (extrinsic rewards). Result (ii) establishes that Generator’s optimal policy induces it to maximise the agents’ joint (extrinsic) total return. The result is proven by a careful adaptation of the policy invariance result in (Ng et al., 1999) to our MARL switching control setting where the intrinsic-reward is not added at all states.
Building on Prop. 1, we deduce the following result:
Corollary 1 LIGS preserves the dec-MDP played by the agents. In particular, let (π̂, g) be a stable point policy profile4 of the MG induced by LIGS, G then π̂ is a solution to the dec-MDP, M.
Therefore, the introduction of Generator does not alter the fundamentals of the problem. Our next task is to prove the existence of a stable point of the MG induced by LIGS and show it is a limit point
3This is similar to random network distillation (Burda et al., 2018) however the input is over the spaceA×S . 4By stable point profile we mean a Markov perfect equilibrium (Fudenberg & Tirole, 1991).
of a sequence of Bellman operations. To do this we prove that a stable solution of G exists and that G has a special property that permits its stable point to be found using dynamic programming. We begin by defining key objects for the analysis:
Given a V π,g : S × N → R, ∀π ∈ Π and g, define by Mπ,gV π,g(sτk , Iτk) := R(sτk ,aτk) + F (θτk ,θτk−1 ) + c(Ik, Ik−1) + γ ∑ s′∈S P (s ′;aτk , s)V π,g(s′, I(τk+1)), ∀sτk ∈ S where aτk ∼ π(·|sτk), θτk ∼ g(·|sτk) and τk is a Generator switching time. We define the Bellman operator T of G by TV π,g(sτk , Iτk) := max { Mπ,gV π,g(sτk , Iτk), R(sτk ,aτk) +
γmax a∈A
∑ s′∈S P (s ′;a, sτk)V π,g(s′, Iτk) } .
The following result establishes that the solution of the MG G, can be computed using RL methods:
Theorem 1 Let V : S × A → R, then for any s ∈ S the game G has a stable point given by lim k→∞ T kV π = sup π̂∈Π V π̂ = V π ? where π? ∈ Π is a stable joint policy of G.
Theorem 1 proves that the MG G (which is the game that is induced when Generator plays with the N agents) 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 dec-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 us to tackle the problem of finding the solution to G using distributed learning methods i.e. MARL to solve G. Moreover, Prop. 1 indicates by computing the stable point of G leads to a solution of M. These results combined prove [II]. Our next result characterises Generator policy gc and the optimal times to activate F . The result yields a key aspect of our algorithm for executing Generator activations of intrinsic rewards:
Proposition 2 The policy gc is given by the following: gc(st, It) = H(Mπ,gV π,g − V π,g)(st, It), ∀(st, It) ∈ S × {0, 1}, where V π,g is the solution in Theorem 1 and H is the Heaviside function, moreover Generator’s switching times are τk = inf{τ > τk−1|Mπ,gV π,g = V π,g}.
In general, introducing intrinsic rewards or shaping rewards may undermine learning and worsen overall performance. We now prove that the LIGS framework introduces an intrinsic reward which yields better performance for the N agents as compared to solving M directly ([III]).
Theorem 2 Each agent’s expected return vπ,g whilst playing G is (weakly) higher than the expected return for M (without Generator) i.e. vπ,g(s, ·) ≥ vπ(s), ∀s ∈ S, ∀i ∈ N .
Theorem 2 shows that Generator’s influence leads to an improvement in the system performance for the N agents. Note that by Prop. 1, Theorem 2 compares the environment (extrinsic) rewards accrued by the agents so that the presence of Generator increases the total expected environment rewards. We complete our analysis by extending Theorem 1 to capture (linear) function approximators which proves [IV]. We first define a projection Π by: ΠΛ := arg min
Λ̄∈{Φr|r∈Rp} ∥∥Λ̄− Λ∥∥ for any function Λ. Theorem 3 LIGS converges to the stable point of G, moreover, given a set of linearly independent basis functions Φ = {φ1, . . . , φp} with φk ∈ L2,∀k. LIGS converges to a limit point r? ∈ Rp which is the unique solution to ΠF(Φr?) = Φr? where FΛ := R̂ + γP max{MΛ,Λ} . Moreover, r? satisfies: ‖Φr? −Q?‖ ≤ (1− γ2)−1/2 ‖ΠQ? −Q?‖.
The theorem establishes the convergence of LIGS to a stable point (of G) with the use of linear function approximators. The second statement bounds the proximity of the convergence point by the smallest approximation error that can be achieved given the choice of basis functions.

heading: 6 EXPERIMENTS

text:
We performed a series of experiments to test if LIGS: 1. learns to efficiently coordinate the agents’ joint exploration 2. Optimises convergence points by inducing coordination. 3. Handles sparse
rewards environments. In all tasks, we compared the performance of LIGS against leading MARL solvers MAPPO (Yu et al., 2021), QMIX (Rashid et al., 2018); intrinsic reward MARL algorithms LIIR (Du et al., 2019), LICA (Zhou, Liu, et al., 2020) and a leading MARL exploration algorithm MAVEN (Mahajan et al., 2019). We then compared LIGS against these baselines in Cooperative Foraging Tasks (Papoudakis et al., 2020) and StarCraft Micromanagement II (Samvelyan et al., 2019).

heading: 6.1 COOPERATIVE FORAGING TASKS

text:
Experiment 1: Coordinated exploration. We tested our first claim that LIGS promotes coordinated exploration among agents. To investigate this, we used a version of the level-based foraging environment (Papoudakis et al., 2020) as follows: there are n agents each with level ai. Moreover, there are 3 apples with level K such that ∑N i=1 ai = K. The only way to collect the reward is if all agents collectively enact the collect action when they are beside an apple. This is a challenging joint-exploration problem since to obtain the reward, the agents must collectively explore joint actions across the state space (rapidly) to discover that simultaneously executing collect near an apple produces rewards. To increase the difficulty, we added a penalty for the agents failing to coordinate in collecting the apples. For example, if only one agent uses the collect action near an apple, it gets a negative reward. This results in a non-monotonic reward structure. Fig. 1 shows the performance curves. Fig, 1 shows LIGS demonstrates superior performance over the baselines. Experiment 2: Optimal joint policies. We next tested our second claim that LIGS can promote convergence to joint policies that achieve higher system rewards. To do this, we constructed a challenging experiment in which the agents must avoid converging to suboptimal policies that deliver positive but low rewards. In this experiment, the grid is divided horizontally in three sections; top, middle and bottom. All grid locations in the top section give a small reward r/n to the agent visiting them where n is the number of tiles in the each section. The middle section does not give any rewards. The bottom section rewards the agents depending on their relative positions. If one agent is at the top and the other at the bottom, the agent at the bottom receives a reward −r/n each time the other agent receives a reward. If both agents are at the bottom, then one of the tiles in this section will give a
reward R, r/2 < R < r to both agents. The bottom section gives no reward otherwise. The agents start in the middle section and as soon as they cross to one section they cannot return to the middle. As is shown in Fig. 1, LIGS learns to acquire rewards rapidly in comparison to the baselines with MAPPO requiring around 400k episodes to match the rewards produced by LIGS. Experiment 3: Sparse rewards. We tested our claim that LIGS can promote learning in MAS with sparse rewards. We simulate a sparse reward setting using a competitive game between two teams of agents. One team is controlled by LIGS while the other actions of the agents belonging to the other team are determined by a fixed policy. The goal is to collect the apple faster than the opposing team. Collecting the apple results in a reward of 1, and rewards are 0 otherwise. This is a challenging sparse reward since informative reward signals occur only apple when the apple is collected. As is shown in Fig. 1 both LIGS and MAPPO perform well on the sparse rewards environment, whilst the other baselines are all unable to learn any behaviour on this environment.
We next investigated the workings of the LIGS framework. We studied the locations where Generator added intrinsic rewards in Experiments 1 and 2. As is shown in the heatmap visualisation in Fig. 2, for Experiment 2, we observe that Generator learns to add intrinsic rewards that guide the agents towards the optimal reward (bottom left) and away from the suboptimal rewards at the top (where some other baselines converge). This supports our claim that LIGS learns to guide the agents towards jointly optimal policies. Moreover, as Fig. 2 shows, LIGS’s switching mechanism means that Generator only adds intrinsic rewards as the most useful locations for guiding the agents towards their target. For Experiment 1, Fig. 2 shows that Generator learns to guide the agents towards the apple which delivers the high rewards. Crucially Fig. 2 (Right) demonstrates a striking benefit of the LIGS framework, namely it only activates the intrinsic rewards around the apple when both agents are at most 2 cells away from the apple. Since the agents receive positive rewards only when they arrive at the apple simultaneously, this ensures the agents are encouraged to coordinate their arrival and receive the maximal positive rewards and avoids encouraging arrivals at times that lead to penalties.

heading: 6.2 LEARNING PERFORMANCE IN STARCRAFT MULTI-AGENT CHALLENGE

text: To study the performance of LIGS in highly complex environments, we compared its performance with the aforementioned baselines on three StarCraft Multi-Agent Challenge (SMAC) maps (Samvelyan et al., 2019) 5m vs. 6m (hard), 6h vs. 8z, and Corridor. These maps vary in a range of MARL attributes such as number of units to control, environment reward density, unit action sets, and (partial)-observability. In Fig. 3, we report our results showing ‘Win Rate’ vs ‘Steps’. These curves are generated by computing the median win rate (vs the opponent) of the agent at regular intervals during learning. We ran 3 of each algorithm (further setup details are in the Supp. material Sec 13). LIGS outperforms the baselines in all maps. In 5m vs. 6m, the baselines do not approach the performance of LIGS. In Corridor MAPPO requires over an extra million steps to match the performance of LIGS. In 6h vs. 8z, LIGS slightly outperforms the baselines. In summary, LIGS shows performance gains over all baselines in SMAC maps which encompass diverse MAS attributes.

heading: 7 CONCLUSION

text: We introduced LIGS, a novel framework for generating intrinsic rewards which significantly boosts performance of MARL algorithms. Central to LIGS is a powerful adaptive learning mechanism that generates intrinsic rewards according to the task and the MARL learners’ joint behaviour. Our experiments show LIGS induces superior performance in MARL algorithms in a range of tasks.

heading: Appendix

heading: Table of Contents

heading: 8 Algorithm 14

heading: 9 Ablation study: Plug & Play 15

heading: 10 Results on Additional StarCraft Micromanagement II Maps 16

heading: 11 Flexibility of LIGS to Accommodate different Exploration Bonus Terms L 17

heading: 12 Further Experiment Demonstrating LIGS improved use of Exploration Bonuses. 18

heading: 13 Further Implementation Details 19

text:
13.1 Hyperparameter Settings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
14 Generator Termination Times 20

heading: 15 Notation & Assumptions 21

text: 16 Proof of Technical Results 22

heading: 8 ALGORITHM

text:
Algorithm 1: Learnable Intrinsic-Reward Generation Selection algorithm (LIGS) Input: Environment E
Initial agent policies π0 = (π10 , . . . π N 0 ) with parameters θπ10 , . . . θπ1N , Initial Generator
switch policy gc0 with parameters θgc0 , Initial Generator action policy g0 with parameters θg0 , Randomly initialised fixed neural network φ(·, ·), Neural networks h (fixed) and ĥ for Augmented 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 agent policies π? = (π?,1, . . . , π?,N )
1 π = (π1, . . . , πN ), g, gc ← π0, g0, gc0 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 = (a1t , . . . , a N t ) from (π 1(st), . . . , π N (st)) 7 Apply action at to environment E, get rewards rt = (r1t , . . . , r N t ) and next state st+1 8 Sample qt from gc(st) // Switching control 9 if qt = 1 then 10 Sample θct from g(st) 11 Sample θct+1 from g(st+1) 12 f it = γφ(st+1, θ c t+1)− φ(st, θct ) // Calculate F (st, θct , st+1, θct+1) 13 else 14 θct , f i t = 0, 0 // Dummy values
15 Append (st,at, gt, θct , rt, f i t , st+1) to B
16 for u = 1, Nu do 17 Sample data (st,at, gt, θct , rt, f i t , st+1) from B 18 if gt = 1 then 19 Set reward to rst = rt + f i t 20 else 21 Set reward to rst = rt 22 // Update Augmented RND 23 LossRND = ||h(st,at)− ĥ(st,at)||2 24 θĥ ← θĥ − α∇LossRND 25 // Update Generator 26 lt = ||h(st,at)− ĥ(st)||2 // Compute L(st,at) 27 ct = cgt 28 Compute Lossg using (st, at, gt, ct, rt, f it , lt, st+1) using PPO loss // Section 4.1 29 Compute Lossgc using (st, at, gt, ct, rt, f i t , lt, st+1) using PPO loss // Section 4.1 30 θg ← θg − α∇Lossg 31 θgc ← θgc − α∇Lossgc 32 // Update agent j, for each j ∈ 1, . . . , N 33 Compute Lossπj using (st,at, r j,s t := r j t + f i t , st+1) using PPO loss // Section 4.1 34 θπj ← θπj − α∇Lossπj

heading: 9 ABLATION STUDY: PLUG & PLAY

text:
In order to validate our claim that LIGS freely adopts RL learners, we tested the ability of LIGS to boost performance in a complex coordination task using independent Proximal policy optimization algorithm (IPPO) (Schulman et al., 2017) as the base learner. In this experiment, two agents are spawned at opposite sides of the grid. The red agent is spawned in the left hand side and the blue agent is spawned in the right hand side of the grid in Fig. 4. The goal of the agents is to arrive at their corresponding goal states (indicated by the coloured square, where the colour corresponds to the agent whose goal state it is) at the other side of the grid. Upon arriving at their goal state the agents receive their reward. However, the task is made difficult by the fact that only one agent can pass through the corridor at a time. Therefore, in this setup, the only way for the agents to complete the task is for the agents to successfully coordinate, i.e. one agent is required to allow the other agent to pass through before attempting to traverse the corridor.
It is known that independent learners in general, struggle to solve such tasks since their ability to coordinate systems of RL learners is lacking (Yang et al., 2020). This is demonstrated in Fig. 4 (right) which displays the performance curve of for IPPO which fails to score above 0. As claimed, when incorporated into the LIGS framework, the agents succeed in coordinating to solve the task. This is indicated by the performance of IPPO + LIGS (blue).

heading: 10 RESULTS ON ADDITIONAL STARCRAFT MICROMANAGEMENT II MAPS

text: Here we present results on two more maps: MMM2 and 3s5z vs 3s6z As can be seen in Fig. 5, LIGS outperforms the leading baseline MAPPO in all maps yielding a 50% improvement in win rate over MAPPO in MMM2.

heading: 11 FLEXIBILITY OF LIGS TO ACCOMMODATE DIFFERENT EXPLORATION BONUS TERMS L

text: To demonstrate the robustness of our method to different choices of exploration bonus terms in Generator’s objective, we conducted an Ablation study on the L-term (c.f. Equation 3) 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 on all three Foraging environments presented in Sec. 6.1. We note that despite the simplicity of the count-based measure, generally the performance of both versions of LIGS is comparable and in fact the count-based variant is superior to the RND version for the joint exploration environment.

heading: 12 FURTHER EXPERIMENT DEMONSTRATING LIGS IMPROVED USE OF EXPLORATION BONUSES.

text: As we have shown above, LIGS can accommodate a variety of exploration bonuses and perform well. Here, we did a experiment to further justify using LIGS against simpler exploration bonus methods. We compared LIGS against and MAPPO with an RND intrinsic reward in the agents’ objectives (MAPPO+RND) and vanilla MAPPO. Fig. 7 shows performance of these two methods on coordination environment shown in Fig. 4. We note that LIGS markedly outperforms both MAPPO+RND and vanilla MAPPO. Due to the added benefit of switching controls and intrinsic reward selection performed by Generator, we observe that LIGS is able to significantly augment the benefits of applying RND directly to the agents’ objectives.

heading: 13 FURTHER IMPLEMENTATION DETAILS

text:
Details of Generator and F (intrinsic-reward) Object Description f Fixed feed forward NN that maps Rd 7→ Rm
[512, ReLU, 512, ReLU, 512, m] Θ Discrete action set which is size of output of f , i.e., Θ is set of integers {1, ...,m} g Fixed feed forward NN that maps Rd 7→ Rm
[512, ReLU, 512, ReLU, 512, m] Intrinsic-reward function φ φ(s, θc) = f(s) · θc
F γφ(st+1, θ c t+1) - φ(st, θ c 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 g network and the network outputs logits pt. We softmax and sample from pt to obtain the action θct . This action is one-hot encoded. Then, the action θct 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 Generator chooses the intrinsic-reward.

heading: 13.1 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 optimisation epochs 4 Number of parallel actors 16 Optimisation 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]
Generator discount factor 0.99 Probability of terminating option [0.5, 0.75, 0.8, 0.9, 0.95]
L function output size [2, 4, 8, 16, 32, 64, 128, 256]
14 Generator TERMINATION TIMES
There are various possibilities for the termination times {τ2k} (recall that {τ2k+1} are the times which the F is switched on using gc). One is for Generator 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.
(4)
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 (4) 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: 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. Where it will not cause confusion (and with a minor abuse of notation) for a given function h we use the shorthand h(π
i,π−i)(s) = h(s, πi, π−i) ≡ Eπi,π−i [h(s, ai, a−i)]. 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 agents’ 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(s, ·)| ≤ C(1 + ‖s‖c) for J ∈ {ri, F, L}. We also make the following finiteness assumption on set of switching control policies for Generator:
Assumption 6 For any policy gc, the total number of interventions is 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‖. (5)
Definition 2 A.2 An operator T : V → V is non-expansive if ∀V1, V2 ∈ V we have:
‖TV1 − TV2‖ ≤ ‖V1 − V2‖. (6)
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)‖ . (7)
Proof 1 We restate the proof given in (Mguni, 2019):
f(a) ≤ ‖f(a)− g(a)‖+ g(a) (8) =⇒ 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). (9)
Deducting max a∈V g(a) from both sides of (9) yields:
max a∈V f(a)−max a∈V g(a) ≤ max a∈V ‖f(a)− g(a)‖ . (10)
After reversing the roles of f and g and redoing steps (8) - (9), we deduce the desired result since the RHS of (10) is unchanged.
Lemma 2 A.4 The probability transition kernel P is non-expansive, that is:
‖PV1 − PV2‖ ≤ ‖V1 − V2‖. (11)
Proof 2 The result is well-known e.g. (Tsitsiklis & Van Roy, 1999). 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 PROP. 1

text:
Proof 3 (Proof of Prop. 1) To prove 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 (Ng et al., 1999), central to this observation is the telescoping sum that emerges by construction of F .
First recall vπ,g(s, I0), for any (s, I0) ∈ S × {0, 1} is given by:
vπ,gi (s, I0) = Eπ,g [ ∞∑ t=0 γt { R(st,at) + F̂ (st, θ c t ; st−1, θ c t−1)It }] (12)
= Eπ,g [ ∞∑ t=0 γtR(st,at) + ∞∑ t=0 γtF̂ (st, θ c t ; st−1, θ c t−1)It ] (13)
= Eπ,g [ ∞∑ t=0 γtR(st,at) ] + Eπ,g [ ∞∑ t=0 γtF̂ (st, θ c t ; st−1, θ c t−1))It ] (14)
Hence it suffices to prove that Eπ,g [∑∞ t=0 γ tF̂ (st, θ c t ; st−1, θ c t−1))It ] = 0.
Recall there a number of time steps that elapse between τk and τk+1, now
∞∑ t=0 γtF̂ (st, θ c t ; st−1, θ c t−1))I(t)
= τ2∑ t=τ1 γtφ(st, θ c t )− γt−1φ(st−1, θct−1) + τ4∑ t=τ3 γtφ(st, θ c t )− γt−1φ(st−1, θct−1)
+ . . .+ τ2k∑ t=τ(2k−1) γtφ(st, θ c t )− γt−1φ(st−1, θct−1) + . . .+
= τ2∑ t=τ1+1 γtφ(st, θ c t )− γt−1φ(st−1, θct−1) + γτ1φ(sτ1 , θcτ1)
+ τ4∑ t=τ3+1 γtφ(st, θ c t )− γt−1φ(st−1, θct−1) + γτ3φ(sτ3 , θcτ3)
+ . . .+ τ2k∑ t=τ(2k−1)+1 γtφ(st, θ c t )− γt−1φ(st−1, θct−1) + γ2k+1φ(sτ2k+1 , θcτ2k+1) + . . .+
= τ2−1∑ t=τ1 γt+1φ(st+1, θ c t+1)− γtφ(st, θct ) + γτ1φ(sτ1 , θcτ1)
+ τ4−1∑ t=τ3 γt+1φ(st+1, θ c t+1)− γtφ(st, θct ) + γτ3φ(sτ3 , θcτ3)
+ . . .+ τ2K−1∑ t=τ(2k−1) γtφ(st, θ c t )− γt−1φ(st−1, θct−1) + γτ2k−1φ(sτ2k−1 , θcτ2k−1) + . . .+
= ∞∑ k=1 τ2K−1∑ t=τ2k−1 γt+1φ(st+1, θ c t+1)− γtφ(st, θct )− ∞∑ k=1 γτ2k−1φ(sτ2k−1 , θ c τ2k−1 )
= ∞∑ k=1 γτ2kφ(sτ2k , θ c τ2k )− ∞∑ k=1 γτ2k−1φ(sτ2k−1 , θ c τ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 θct ≡ 0 whenever t = τ1, τ2, . . . and by construction φ(s, 0) ≡ 0 for any s. With this we readily deduce that vπ,g(s) = Eπ,g [ ∑∞ t=0 γ
tR(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π,gc (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π,gc (s0, I0) = Eπ,g  ∞∑ t=0 γt Rθ +∑ k≥1 c(It, It−1)δ t τ2k−1 + Ln(st,at)  (15) = Eπ,g
 ∞∑ t=0 γt R+∑ k≥1 c(It, It−1)δ t τ2k−1 + Ln(st,at) + ∞∑ t=0 γtF θIt  (16)
≤ Eπ,g [ ∞∑ t=0 γt (R+ Ln(st,at)) ] (17)
≤ ∣∣∣∣∣Eπ,g [ ∞∑ t=0 γt (R+ Ln(st,at)) ]∣∣∣∣∣ (18) ≤ Eπ,g
[ ∞∑ t=0 γt ‖R+ Ln‖ ] (19)
≤ ∞∑ t=0 γt (‖R‖+ ‖Ln‖) (20)
= 1
1− γ (‖R‖+ ‖Ln‖) (21)
using the triangle inequality, the definition of Rθ and the (upper-)boundedness of L and R (Assumption 5). We now note that by the dominated convergence theorem we have that ∀(s0, I0) ∈ S ×{0, 1}
lim n→∞ vπ,gc (s0, I0) = lim n→∞ Eπ,g  ∞∑ t=0 γt Rθ +∑ k≥1 c(It, It−1)δ t τ2k−1 + Ln(st, at)  (22) = Eπ,g lim
n→∞  ∞∑ t=0 γt Rθ +∑ k≥1 c(It, It−1)δ t τ2k−1 + Ln(st, at)  (23) = Eπ,g
 ∞∑ t=0 γt Rθ +∑ k≥1 c(It, It−1)δ t τ2k−1  (24) = Eπ,g
 ∞∑ t=0 γt R+∑ k≥1 c(It, It−1)δ t τ2k−1  = c K 1− γ + vπ(s0), (25)
where K is the total number of switch activations or interventions and where again we have used the key result in the proof of (i) and Assumption 6 in the last step, after which we deduce (ii) since vπ and vπ,gc differ by only a constant.
Note that by (ii) we heron may consider the quantity for the Generator expected return:
v̂π,gc (s0, I0) = Eπ,g  ∞∑ t=0 γt R+∑ k≥1 c(It, It−1)δ t τ2k−1  . (26)

heading: PROOF OF THEOREM 1

text:
Proof 4 Theorem 1 is proved by firstly showing that when the agents jointly maximise the same objective there exists a fixed point equilibrium of the game when all agents use Markov policies and Generator uses switching control. The proof then proceeds by showing that the MG G admits a dual representation as an MG in which all agents N × {c} jointly maximise the same objective which has MPE 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 all agents maximise an identical objective) in which one of the agents 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π,g : S × {0, 1} → R such that5
vπ,gi (z)− v π′,g i (z) = B π,g(z)−Bπ′,g(z), ∀z ≡ (s, I0) ∈ S × {0, 1},∀i ∈ N × {0}.
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 |gc(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π,gΛ(sτk , I(τk)), [ ψ(sτk ,a) + γmax
a∈A ∑ s′∈S P (s′;a, sτk)Λ(s ′, I(τk)) ]} (27)
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 (27), that is to say we prove the following statements:
i) ∣∣∣∣Θ(zt,a, θct , θct−1) + γmaxa∈A Pas′stψ(s′, ·)− ( Θ(zt,a, θ c t , θ c t−1) + γmax a∈A Pas′stψ ′(s′, ·) )∣∣∣∣ ≤ γ ‖ψ − ψ′‖ ii) ‖Mπ,gψ −Mπ,gψ′‖ ≤ γ ‖ψ − ψ′‖ , (and henceM is a contraction).
iii) ∥∥∥∥Mπ,gψ − [Θ(·,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, θct , θct−1) + γPπs′stψ(s′, ·)− [Θ(zt,a, θct , θct−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π,gψ −Mπ,gψ′)(sτ , I(τ))| 5This property is analogous to the condition in Markov potential games (Macua et al., 2018; Mguni et al.,
2021)
≤ max aτ ,θcτ ,θ c τ−1∈A×Θ2 ∣∣∣∣∣Θ(zτ ,aτ , θcτ , θcτ−1) + c(Iτ , Iτ−1) + γPπs′sτPaψ(sτ , I(τ ′)) − ( Θ(zτ ,aτ , θ c τ , θ c τ−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π,gψ(sτ , I(τ))− ( Θ(zτ ,aτ , θ c τ , θ c τ−1) + γmax
a∈A Pas′sτψ ′(s′, I(τ))
) < 0. (28)
We now observe the following:
Mπ,gψ(sτ , I(τ))−Θ(zτ ,aτ , θcτ , θcτ−1) + γmax a∈A Pas′sτψ ′(s′, I(τ)) ≤ max {
Θ(zτ ,aτ , θ c τ , θ c τ−1) + γPπs′sτP aψ(s′, I(τ)),Mπ,gψ(sτ , I(τ)) }
−Θ(zτ ,aτ , θcτ , θcτ−1) + γmax a∈A Pas′sτψ ′(s′, I(τ))
≤ ∣∣∣∣∣max{Θ(zτ ,aτ , θcτ , θcτ−1) + γPπs′sτPaψ(s′, I(τ)),Mπ,gψ(sτ , I(τ))} −max { Θ(zτ ,aτ , θ c τ , θ c τ−1) + γmax
a∈A Pas′sτψ
′(s′, I(τ)),Mπ,gψ(sτ , I(τ)) }
+ max { Θ(zτ ,aτ , θ c τ , θ c τ−1) + γmax
a∈A Pas′sτψ
′(s′, I(τ)),Mπ,gψ(sτ , I(τ)) }
−Θ(zτ ,aτ , θcτ , θcτ−1) + γmax a∈A Pas′sτψ ′(s′, I(τ)) ∣∣∣∣∣ ≤ ∣∣∣∣∣max { Θ(zτ ,aτ , θ c τ , θ c τ−1) + γmax a∈A Pas′sτψ(s ′, I(τ)),Mπ,gψ(sτ , I(τ)) }
−max {
Θ(zτ ,aτ , θ c τ , θ c τ−1) + γmax a∈A Pas′sτψ ′(s′, I(τ)),Mπ,gψ(sτ , I(τ)) } ∣∣∣∣∣
+ ∣∣∣∣∣max { Θ(zτ ,aτ , θ c τ , θ c τ−1) + γmax a∈A Pas′sτψ ′(s′, I(τ)),Mπ,gψ(sτ , I(τ)) }
−Θ(zτ ,aτ , θcτ , θcτ−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π,gψ(sτ , I(τ))− (Θ(zτ ,aτ , θcτ , θcτ−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π,gψ(sτ , I(τ))− ( Θ(zτ ,aτ , θ c τ , θ c τ−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π,gψ(sτ , I(τ))− ( Θ(zτ ,aτ , θ c τ , θ c τ−1) + γmax
a∈A Pas′sτψ ′(s′, I(τ)) ) ≤Mπ,gψ(sτ , I(τ))− ( Θ(zτ ,aτ , θ c τ , θ c τ−1) + γmax
a∈A Pas′sτψ ′(s′, I(τ))
) − c(Iτ , Iτ−1)
≤ Θ(zτ ,aτ , θcτ , θcτ−1) + c(Iτ , Iτ−1) + γPπs′sτP aψ(s′, I(τ ′)) − (
Θ(zτ ,aτ , θ c τ , θ c τ−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π,gΛ−maxa∈A [ψ(·, a) + γPaΛ′] ∥∥∥∥ ≤ γ ‖Λ− Λ′‖ . (29) 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 3 For any π ∈ Π and for any Generator policy g, there exists a function Bπ,g : S × {0, 1} → R such that
vπ,gi (z)− v π′,g i (z) = B π,g(z)−Bπ ′,g(z), ∀z ≡ (s, I0) ∈ S × {0, 1} (30)
where in particular the function B is given by:
Bπ,g(s0, I0) = Eπ,g  ∞∑ t=0 γt Rθ +∑ k≥1 c(It, It−1)δ t τ2k−1  , (31) for any (s0, I0) ∈ S × {0, 1}.
Proof 6 Note that by the deduction of (ii) in Prop 1, we immediately observe that
v̂π,gc (s0, I0) = B π,g(s0, I0), ∀(s0, I0) ∈ S × {0, 1}. (32)
We therefore immediately deduce that for any two Generator policies g and g′ the following expression holds ∀(s0, I0) ∈ S × {0, 1}:
v̂π,gc (s0, I0)− v̂π,g ′ c (s0, I0) = B π,g(s0, I0)−Bπ,g ′ (s0, I0). (33)
Our aim now is to show that the following expression holds ∀(s0, I0) ∈ S × {0, 1}:
vπ,gi (I0, s0)− v π′,g i (I0, s0) = B π,g(I0, s0)−Bπ ′,g(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π,gT−1(IT−1, sT−1)−B π′,g 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 π,g 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 π′,g 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 π,g T (IT , sT )
− ∑ sT∈S ∑ a′T−1∈A π′(a′T−1; sT−1)P (sT ;a ′ T−1)B π′,g T (IT , sT )
]] .
(34)
We now observe that for any π ∈ Π and for any g we have that Bπ,gT (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 g
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π,gT−1(IT−1, sT−1)−B π′,g 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)
(35)
+ γ ( ∑ sT∈S ∑ aT−1∈A ∑ aT∈A π(aT−1; sT−1)P (sT ;aT−1)π(aT ; sT )R(sT ,aT ) (36)
− ∑ 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 ) (37)
+ ∑ 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)
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
− ∑ 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
]
= 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) using Assumption 6.
Hence we find that EsT−1∼dθ [ Bπ,gT−1(IT−1, sT−1)−B π′,g 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π(aT−1;sT−1)P (sT ;aT−1)∈A π(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π,gi,T−1(sT−1)− v π′,g i,T−1(sT−1) ] (50)
Hence, we have succeeded in proving that the expression (30) 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π,gT−k as
Bπ,gT−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 π,g T−(k+1)(IT−(k+1), sT−(k+1))
] .
(52)
Now we consider the case when we evaluate the expression (30) 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 π,g 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 π′,g 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 π,g 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 π′,g 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π,gT−(k+1)(IT−(k+1), sT−(k+1))−B π′,g T−(k+1)(IT−(k+1), sT−(k+1))
] = 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 π,g 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 π′,g 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 π,g 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 π′,g 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 π,g 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 π′,g i,T−k(IT−k, sT−k)
]] .
= EsT−(k+1)∼dθ [ vπ,gi,T−(k+1)(IT−(k+1), sT−(k+1))− v π′,g T−(k+1)(IT−(k+1), si,T−(k+1)) ] (57)
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
− ∑
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
]
= K  ∑ aT−k∈A π(aT−k)− ∑ a′T−k∈A π′(a′T−k)  = 0 (58) 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,∀π−i ∈ Π−i and ∀s ∈ S:
Es∼P [( vπ,gi − v π′,g i ) (z) ] = Es∼P [( Bπ,g −Bπ ′,g ) (z) ] . (59)
The result is proven by contradiction.
To this end, let us firstly assume ∃c 6= 0 such that Es∼P [( vπ,gi − v π′,g i ) (z) ] − Es∼P [( Bπ,gi −B π′,g i ) (z) ] = c.
Let us now define the following quantities for any s ∈ S and for each πi ∈ Πi and π−i ∈ Π−i and ∀i ∈ N :
vπ,gi,T ′(z) := T ′∑ t=0 µ(s0)πi(a i 0, s0)π−i(a −i 0 , s0) t−1∏ j=0 ∑ sj+1∈S γtP (sj+1; sj , aj)πi(a i j |sj)π−i(a−ij |sj)ri(zj ,aj),
and
Bπ,gT ′ (z) := T ′∑ t=0 µ(s0)πi(a i 0, s0)π−i(a −i 0 , s0) t−1∏ j=0 ∑ sj+1∈S P (sj+1; sj , aj) · πi(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)πi(a i 0, s0)π−i(a −i 0 , s0) T ′−1∏ j=0 ∑ sj+1∈S γtP (sj+1; sj , aj)πi(a i j |sj)π−i(a−ij |sj)v π i (sT ′).
Next we observe that: c = Es∼P [( vπ,gi − v π′,g i ) (z) ] − Es∼P [( Bπ,g −Bπ ′,g ) (z) ]
= Es∼P [( vπ,gi,T ′ − v π′,g i,T ′ ) (z) ] − Es∼P [( Bπ,gT ′ −B π′,g T ′ ) (s) ]
+γT ′ EsT ′∼P [ µ(s0)πi(a i 0, s0)π−i(a −i 0 , s0) T ′−1∏ j=0 ∑ sj+1∈S P (sj+1; sj , aj)πi(a i j |sj)π−i(a−ij |sj) (v π,g i (zT ′)−B π,g(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π ′,g i (zT ′)−B π′,g(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π,gi,T ′ − v π′ i,T ′ ) (z)− ( Bπ,gT ′ −B π′ T ′ ) (z) ]∣∣∣∣∣ > 12c, which is a contradiction since we have proven that for any finite T ′ it is the case that
Es∼P [( vπ,gi,T ′ − v π′ i,T ′ ) (z)− ( Bπ,gT ′ −B π′ T ′ ) (z) ] = 0,
and hence we deduce the result in the infinite horizon case.
PROOF OF PART III
To prove Part III, we firstly define precisely the notion of a stable point of the MG, G:
Definition 3 A policy profile σ? = (g?, π?i , π?−i) ∈ Π is a Markov perfect equilibrium (MPE) in Markov strategies if the following condition holds for any i ∈ N × {0}:
v (g?,π?i ,π ? −i) i (z) ≥ v g?,(π′i,π ? −i) i (z), ∀z ≡ (s0, I0) ∈ S × {0, 1}, ∀π ′ i ∈ Πi. (60) v (g?,π?i ,π ? −i) c (z) ≥ v g′,(πi,π ? −i) c (z), ∀z ≡ (s0, I0) ∈ S × {0, 1}, ∀g′. (61)
The condition characterises strategic configurations which are stable points of the MG, G. In particular, an MPE is achieved when at any state no agent can improve their expected cumulative rewards by unilaterally deviating from their current policy. We denote by NE{G} the set of MPE strategies for the MG, G. Next we prove that the set of maxima of the function B are the MPE of the MG G:
Proposition 4 The following implication holds:
σ ∈ arg sup g′,π′∈Π
Bg ′,π′(s) =⇒ σ ∈ NE{G}. (62)
where B is the function in Prop. 3.
Prop. 4 indicates that the game has an equivalent representation in which all agents maximise the same function and thus play a team game.
Proof 1 We do the proof by contradiction. Let σ = (π1, . . . , πN , g) ∈ arg sup π′∈Π,g′
Bπ ′,g′(s) for any
s ∈ S. Let us now therefore assume that σ /∈ NE{G}, hence there exists some other policy profile σ̃ = (π1, . . . , π̃i, . . . , πN , g) which contains at least one profitable deviation by one of the agents i ∈ N × {0, }. For now let us consider the case in which the profitable deviation is for a agent i ∈ N so that π′i 6= πi for i ∈ N i.e. v (π′i,π−i),g i (s) > v (πi,π−i),g i (s) (using the preservation of signs of integration). Prop. 3 however implies that B(π ′ i,π−i),g(s)−B(πi,π−i),g(s) > 0 which is a contradiction since σ = (πi, π−i, g) is a maximum of B. The proof can be straightforwardly adapted to cover the case in which the deviating agent is Generator after which we deduce the desired result.
The last result completes the proof of Theorem 1.

heading: PROOF OF PROPOSITION 2

text:
Proof 7 (Proof of Prop. 2) The proof is given by establishing a contradiction. Therefore suppose thatMπ,gψ(sτk , I(τk)) ≤ ψ(sτk , I(τk)) and suppose that the switching time τ ′1 > τ1 is an optimal switching time. Construct the Generator g′ and g̃ policy switching times by (τ ′0, τ ′ 1, . . . , ) and g ′2 policy by (τ ′0, τ1, . . .) respectively. Define by l = inf{t > 0;Mπ,gψ(st, I0) = ψ(st, I0)} and m = sup{t; t < τ ′1}. By construction we have that
vπ,g ′
c (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π,g ′ c (s ′, I(τ ′1)) ]]]] < E [ R(s0,a0) + E [ . . .+ γl−1E [ R(sτ1−1,aτ1−1) + γMπ,g̃vπ,g ′ c (sτ1 , I(τ1)) ]]]
We now use the following observation E [ R(sτ1−1,aτ1−1) + γMπ,g̃vπ,g ′ c (sτ1 , I(τ1)) ]
≤ max { Mπ,g̃vπ,g′c (sτ1 , I(τ1)), max
aτ1∈A
[ R(sτk ,aτk) + γ ∑ s′∈S P (s ′;aτ1 , sτ1)v π,g c (s ′, I(τ1)) ]} .
Using this we deduce that
vπ,g ′
2 (s, I0) ≤ E [ R(s0,a0) + E [ . . .
+ γl−1E [ R(sτ1−1,aτ1−1) + γmax { Mπ,g̃vπ,g ′
c (sτ1 , I(τ1)), max aτ1∈A
[ R(sτk ,aτk) + γ ∑ s′∈S P (s′;aτ1 , sτ1)v π,g c (s ′, I(τ1)) ]}]]] = E [ R(s0,a0) + E [ . . .+ γl−1E [ R(sτ1−1,aτ1−1) + γ [ Tvπ,g̃c ] (sτ1 , I(τ1)) ]]] = vπ,g̃c (s, I0))
where the first inequality is true by assumption onM. This is a contradiction since g′ is an optimal policy for Generator. 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:
Proof 8 (Proof of Theorem 2) The proof which is done by contradiction follows from the definition of vc. Denote by v π,g≡0 i value function an agent i ∈ N excluding Generator and its intrinsic-reward
function. Indeed, let (π̂, ĝ) be the policy profile induced by the Nash equilibrium policy profile and assume that the intrinsic-reward F leads to a decrease in payoff for agent i. Then by construction vπ,g(s) < vπ,g≡0(s) which is a contradiction since (π̂, ĝ) is an MPE profile.

heading: PROOF OF THEOREM 3

text:
To prove the theorem, we make use of the following result:
Theorem 4 (Theorem 1, pg 4 in (Jaakkola et al., 1994)) 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π,gQ(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π,gQ(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π,gQ(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π,gQ(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π,gQ(sτk , Iτk ,a), φ(sτk ,a) + γmax
a′∈A Q(s′, Iτk ,a ′)
} −Q?(st, It, a) ] = E [( max { Mπ,gQ(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π,gQ(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π,gQ(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 FUNCTION APPROXIMATION

text:
First let us recall the statement of the theorem:
Theorem 3 LIGS 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 5 (Th. 17, p. 239 in (Benveniste et al., 2012)) 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 5, 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.

title: LIGS: LEARNABLE INTRINSIC-REWARD GENERATION SELECTION