Learning to Steer Markovian Agents under Model Uncertainty
Authors: Jiawei Huang
Vinzenz Thoma
Zebang Shen
Heinrich H. Nax
Niao He
Venue: ICLR 2025 Poster (2025)
Keywords: Steering Learning Dynamics
Reinforcement Learning
Markov Games
Mechanism Design
Primary area: reinforcement learning
TL;DR: We study the steering Markovian agents under model uncertainty. We propose a formal problem formulation and a new optimization objective with theoretical justification. We contribute theoretical understanding and empirical solutions to our objective.

Abstract: Designing incentives for an adapting population is a ubiquitous problem in a wide array of economic applications and beyond. In this work, we study how to design additional rewards to steer multi-agent systems towards desired policies \emph{without} prior knowledge of the agents' underlying learning dynamics. Motivated by the limitation of existing works, we consider a new and general category of learning dynamics called \emph{Markovian agents}. We introduce a model-based non-episodic Reinforcement Learning (RL) formulation for our steering problem. Importantly, we focus on learning a \emph{history-dependent} steering strategy to handle the inherent model uncertainty about the agents' learning dynamics. We introduce a novel objective function to encode the desiderata of achieving a good steering outcome with reasonable cost. Theoretically, we identify conditions for the existence of steering strategies to guide agents to the desired policies. Complementing our theoretical contributions, we provide empirical algorithms to approximately solve our objective, which effectively tackles the challenge in learning history-dependent strategies. We demonstrate the efficacy of our algorithms through empirical evaluations.

Published as a conference paper at ICLR 2025
LEARNING TO STEER MARKOVIAN AGENTS UNDER MODEL UNCERTAINTY
Jiawei Huang', Vinzenz Thoma', Zebang Shen', Heinrich H. Nax Department of Computer Science, ETH Zurich
Nax3,Nio Niao Hel
i
(jiawei. huang, zebang. shen, niac
$ ETH AI Center
vinzenz. thoma@al ethz. ch
$ University of Zurich
chinzich.naxuuzh.chh cawbuzh.ch
ABSTRACT
Designing incentives for an adapting population is a ubiquitous problem in a wide array of economic applications and beyond. In this work, we study how to design additional rewards to steer multi-agent systems towards desired policies without prior knowledge of the agents' underlying learning dynamies. Motivated by the limitation of existing works, we consider a new and general category of learning dynamics called Markovian agents. We introduce model-based non-episodic Reinforcement Learning (RL) formulation for our steering problem. Importantly, we focus on learning history-dependee model uncertainty about the agents' learning dynamics. We introduce a novel ob- jective function encode the desiderata of achieving good steering outcome with reasonable cost. Theoretically, we identify conditions for the existence of steering strategies guide agents to the desired policies. Complementing our theoretical contributions, we provide empirical algorithms to approximately solve our objec- tive, which effectively tackles the challenge in learning history-dependen strategies. We demonstrate the efficacy of our algorithms through empirical evaluations.
steering strategy to handle the inherent
INTRODUCTION
Many real-world applications can be formulated as Markov Games (Littman 1994) where the agents repeatedly interact and update their policies based on the received feedback. In this context, different learning dynamics and their convergence properties have been studied extensively (see, for example, Fudenberg and Levine (1998)). Because of the mismatch between the individual short-run and collective long-run incentives, or the lack of coordination decentralized systems, agents following standard learning dynamics may not converge to outcomes that are desirable from system designer perspective, such as the Nash Equilibria (NE) with the largest social welfare. An interesting class of games that exemplify these issues are so-called "Stag Hunt" games (see Fig.[I which used to study a broad array of real-world applications including collective action, public good provision, social dilemma, team work and innovation adoption (Skyrms) 2004 [ Stag Hunt games have two pure-strategy NE, one of which is payoff-dominan that is, both players obtain higher payoffs in that equilibrium than in the other. Typical algorithms may fail reach the payoff-dominant equilibrium (H, H) (LHS Fig. (b)). Indeed, the other equilibrium (G, G) is typically selected when it risk-dominan (Harsanyi and Selten 1988 Newton 2021).
This paper focuses on situations when an external "mediator" exists, who can influence and steer the agents' learning dynamies by modifying the original rewards via additional incentives. This kind of mediator can be conceptualized in various ways. In particular, we can think of social planner who provides monetary incentives for joint ventures or for adoption an innovative technology via individual financial subsidies. As illustrated on the RHS of Fig. (b), with suitable steering, agents' dynamics can be directed to the best outcome. Our primary objective is to steer the agents to some desired policies, that is, to minimize the steering gap vis-a-vis the target outcome. As secondary
We defer conerete and practical scenario which can he modeled by the Stag Humt game Appx. B.1

---

Published as a conference paper at ICLR 2025
objective, the payments agents regarding the steering rewards should be reasonable, that is, the steering cost should be low.
To our knowledge, Zhang al. (2023) is the first work studying a similar steering problem as ours. They assume the agents no-regret learners and may act in arbitrarily adversarial ways, In some natural settings, such assumption may not be practical, because no-regret criterion typically requires careful processing of the en- tire history of learning. In settings with limited cognitive resources and bounded rationality, is natural to favor models where the agents only process a subset of the available information (Camerer 2011). In particular, humans have been widely shown to rely overproportionally on recent experiences in decision making, known as 'recency bias' (Costabile and Klein 2005; Page and Pagel 2010 Durand et al. (021). Be- sides, there is evidence that behavioral dynamics that only rely on the most recent experience are able to fit behavioral data well in certain situa- tions (Mäs and Nax 2016). Motivated by these insights, we therefore study steering a different category of learning dynamics called Markovian agents, where the agents' policy updates only depend on their current policy and the (modi- fied) reward function. Our model complements the prior work on no-regret agents, and serves as the first abstraction of behavior based on limited cognitive abilities with recency bias in steering setting. Theoretically, Markovian agents subsumes broader class of popular policy-based methods as concrete examples (Giannou et al. [022] Ding et al., 2022). which are not covered by no-regret assumptions. We note that concurrent work (Canyakmaz et al. 2024) considers a similar setting as ours, and we defer to Sec. [.] for further discussion.
G
(5. 5)
(0, 4)
(4, 0)
(2, 2)
(a) Payoff Matrix of the Two-Player "Stag Hunt" Game. and G stand for two actions Hunt and Gather. Both (H, H) and (G, G) NE and (H, H) is payoff-dominant.
1.0
No Steering
1.0
With Steering
0.5
0.0
0.5 rH
1.0
0.0
0.5 (H(H)
1:0
(b) Dynamics of Agents Policies without/with Steering. Agents follow natural policy gradient (replicator dynam- ics) for policy update. and y axes correspond to the probability to take action by the row and column play- ers. Red curves represent the dynamics of agents' poli- cies starting from different intializations (black dots).
Figure 1: Example: The "Stag Hunt" Game
In practice, learning the right steering strategies encounters two main challenges. First, the agents may not disclose their learning dynamics model to the mediator. As a result, this creates fundamental model uncertainty, which we will tackle with appropriate Reinforcement Learning (RL) techniques to trading-off exploration and exploitation. Second, it may be unrealistic to assume that the mediator able to force the agents to "reset" their policies in order to generate multiple steering episodes with the same initial state. This precludes the possibility of learning steering strategies through fixed-horizon episodic RL (Dann)
episodic trial-and-error. Therefore, the most commonly-considenn and Brunskill 2015) framework is not applicable here. Instead, we will consider a finite-horizon non-episodic setup, where the mediator can only generate one finite-horizon episode, which we have to conduct both the model learning and steering of the agents simultaneously. Motivated by these considerations, we would like to address the following question in this paper:
How learn desired steering strategies for Markovian agents in the non- non-episodic setup under model uncertainty?
We consider a model-based setting where the mediator can get access to a model class F containing the agents' true learning dynamics f We summarize and highlight our key contributions follow:
Conceptual Contributions: In Sec. we formulate steering non-episodic RL problem, and propose a novel optimization objective in Obj. ① where we explicitly tackle the inherent model uncertainty by learning history-dependent steering strategies. As we show in Prop. 3.3 under certain conditions, even without prior knowledge of / the optimal solution to Obj. achieves not only low steering gap, but also "Pareto Optimality" in terms of both steering costs and gaps.
Theoretical Contributions: In Sec. 4 we provide sufficient conditions under which there exists steering strategies achieving low steering gap. These results in turn justify our chosen objective and problem formulation.
2

---

Published as a conference paper at ICLR 2025
Algorithmic Contributions: Learning history-dependent strategy presents challenges due the exponential growth in the history space. We propose algorithms to overcome these issues.
When the model class [F[] is small, in Sec. 5.1 we approach our objective from the perspective of learning in a Partially Observable MDP, and propose to learn a policy over the model belief state space instead of over the history space.
For the case when [F] is large, exactly solving Obj. (T can be challenging. Instead, we focus on approximate solutions to trade-off optimality and tractability. In Sec. 5.2, we propose a First-Explore- Secsploor-Then-Bieee Then-Exploit ETE) framework. Under some conditions, can still ensure the directed agents converge to the desired outcome.
Empirical Validation: In Sec. G we evaluate our algorithms in various representative environments, and demonstrate their effectiveness under model uncertainty.
1.1 CLOSELY RELATED WORKS
We discuss the works most closely related to ours in this section, and defer the others to Appx. B.2
Steering Learning Dynamics As mentioned in the introduction, Zhang et al. (2023) are the first to introduce the "steering problem", but their setting differs quite fundamentally from ours in several key aspects. Firstly, they assume that agents behave as no-regret and arbitrarily adversarial learners, which may be unrealistic in settings with limited information and feedback. and owed to agents' limited cogmitive resources (Camerer 201T) including recency bias (Costabile and Klein 2005). Motivated by this, we instead focus on a broad class of Markovian dynamics. Secondly, the mediator's objective in Zhang et al. (2023) is to steer agents such that the average policy converges to the target NE while maintaining a sublinear accumulative budget, motivated by their infinite-horize contrast, we consider the finite-horizon setting, and therefore, we are concerned with minimizing the steering gap of the terminal policy and the cumulative steering cost. Thirdly, when the desired NE is not pure. Zhang et al. (2023) require the mediator to be able to "give advice" to the players to facilitate coordination, while do not allow the mediator to do this. Because of these differences, the methods and results obtained by /Zhang et al. (2023) and us are not directly comparable, yet complement another depending on application considered.
setup. In
Perhaps the closest to ours is a concurrent work by Canyakmaz et al. 2024). They consider a similar finite-horizon non-episodic setup as ours, and experimentally investigate the use of control methods to direct game dynamics towards desired outcomes, in particular allowing for model uncertainty. Compared to their work, we handle the model uncertainty in a more principled way by employing distory-dependen steering strategies, since history can serve as sufficient information set for decision making under uncertainty. This leads to several differences in the design principles between our algorithms and Canyakmaz et al. (2024). Concretely, we propose a learning objective for history- dependent strategies in Obj. (I). and two algorithms for low uncertainty (small F) and high uncertainty (large F) settings, respectively. In the former case, contribute belief-state based algorithm that can exactly solve Obj- ( offering a stronger solution due to the theoretical guarantee in Prop. 3.3 For the latter, although both our FETE and SIAR-MPC (Canyakmaz et al. [024] share two-phase (exploration + exploitation) structure, ours represents a more general framework with a more advanced exploration strategy (see more explanation in Sec. [.2]. Besides, develop additional novel theory regarding the existence of strategies with low steering gap.
2 PRELIMINARY
In the following, we formally define the finite-horizon Markov Game that will focus on. We summarize all the frequently used notations in this paper in Appx. A
Finite Horizon Markov Game A finite-horizon N N-player Markov Game is defined by a tuple G:= G- $1, H, H.S.A := [A")"_ P. r- == {-= where N := 21. N) } is the indices of agents, s1 is the fixed initial state, H the horizon length, S is the finite shared state space, A²" is the finite action space for agent n, and A denotes the joint action space. Besides, IP : [Pa)ne with PA : S::S x A - A(S) denotes the transition function of the shared state, and r = hee with Tf : S x A - [o, 1] denotes the reward function for agent n. For each agent n. we consider the non- stationary Markovian policies 1 := (xr (TT,-.. ..., TH |Ah E [H], T S A(A")). We denote
3

---

Published as a conference paper at ICLR 2025
: .... x II to be the joint policy space of all agents. Given policy := f "..,,,)} II,
a trajectory is generated by: vh E [H], An E [N], of ~ x"(+(s)), Th < (s,, an), sh+1 ~ PA (-1s), an), where as := [aj [ne]N]] denotes the collection of all actions. Given policy n,,
define the value functions by: 2%/ (t--) =- Ex B T7 (sw, anx){s; = an = -J, A/r pr (+) ==
Ex -h (88', as))|sn = -], where we use |r to specify the reward function associated with the value functions. In the rest of the paper, we denote A", = 0r- Vrr to be the advantage value
function, and denote (TT) == v to be the total return of agent w.r.t. policy
THE PROBLEM FORMULATION OF THE STEERING MARKOVIAN AGENTS
We first introduce our definition of Markovian agents. Informally, the policy updates of Markovian agents independent of the interaction history conditioning on their current policy and observed rewards. This encompass a broader class of popular policy- methods as concrete examples
(Giannou al. 2022 Ding et al. 2022 Xiao 2022
Daskalakis al. 2020).
Definition 3.1 (Markovian Agents), Given a game G, a finite and fixed T, the agents are Markovian if their policy update rule f only depends on the current policy T, and the reward function r::
E [T], T++1 ~ f()
Here only highlight the dependence n. and r, and omit other dependence (e.g. the transition function of G). It is worth to note that we do not restrict whether the updates of agents' policies are independent correlated with each other, deterministic stochastic. We assume I is known to us.
In the steering problem, the mediator has the ability to change the reward function r via the steering reward u, that the agents' dynamics are modified to:
Vt E [T], Ue whel- | U1 ... -r 1r Te),, TT+1 f(||TT r uc).
Here vb := (e(r) denotes the mediator's "steering strategy" to generate u4. We consider history- dependent strategies to handle the model uncertainty, which we will explain later. Besides, u, := (u];,) (e[_)))[[[]] where Wf,,h S x A [0, Umax] is the steering reward for agent n at game horizon h and steering step t. Umax < +00 denotes the upper bound for the steering reward. With bit of abuse of notation, here we treat both r and u, as vectors with length H H | and use + u to denote elementwise addition. For practical concerns, we follow the standard constraints that the steering rewards are non-negative.
The mediator has terminal reward function ry8oal and a cost function s780at First, n780al [0, 7max] assesses whether the final policy TT+1 aligns with desired behaviors-thi encapsulates our primary goal of a low steering gap. Note that we consider the general setting and do not restrict the maximizer of na to be a Nash Equilibrium. For instance, to steer the agents to desired policy n², we could choose 17800 (TT) := - π - π T²1 Alternatively, in scenarios focusing on maximizing utility, on (T) could be defined as the total utility Σme[N] Jh (TT). For 1f IT Rzo.
is used to quantify the steering cost incurred while steering. In this paper, we fix ( u) := Ene[N] J (=")
(T") to be the total return related to and the steering reward u. Note that always
have 0 & 17000 TT, u. & H..
Steering Dynamics as a Markov Decision Process (MDP) Given game G, the agents' dy- namics f and (1780st s the steering dynamics can be modeled by a finite-horizon MDP. M : (Ti, T, II, J. (1pson 1/80o))3 with initial state TI, horizon length T. state space II, action space U := [0, Umax]* (NN stationary transition f. running reward 17t0s and terminal reward yauall For completeness, we defer to Appx. B.3 for an introduction of finite-horizon MDP
Steering under Model Uncertainty In practice, the mediator may not have precise knowledge of agents learning dynamics model, and the uncertainty should be taken into account. We will only focus on handling the uncertainty in agents' dynamics f. and assume the mediator has the full knowledge of G and the reward functions ye and of We consider the model-basee setting where the mediator only has access finite model class F ((FI- < +00) satisfying the following assumption:
Assumption A (Realizability). The true learning dynamics fe is realizable, i.e. f F.
4

---

Published as a conference paper at ICLR 2025
A Finite-Hoziron Non-Episodic Setup and Motivation As motivated previously, we formu- late steering as a finite-horizon non-episodic RL problem. To our knowledge, in contrast to our finite-horizon setting, most of the non-episodic RL settings consider the infinite-horizon setup with stationary or non-stationary transitions, and therefore, they are also not suitable here. We provide more discussion in Appx. [8.2
Definition 3.2 (Finite Horizon Non-Episodic Steering Setting). The mediator can only interact with the real agents for one episode [ u1,.... F uT, TT+1), where T ~ f (+ r + un) for all t E [T]. Nonetheless, the mediator can get access to the simulators for all models in F. and it can sample arbitrary trajectories and do episodic learning with those simulators to decide the best steering actions U1, U2,,... ur to deploy.
The Learning Objective Motivated by the model-based non-episodic setup, we propose the following objective function, where we search over the set of all history-dependent strategies, denoted by V, to optimize the average performance over all f f F.
1 E FEF
1p TT,, un)
arg max NEW
Here we use E := Vi E denote the expectation over trajectories generated by & and of E F: >> is regularization factor. Next, we explain the rationale to consider history-dependent strategies. As introduced in Def. 3.2 we only intereact with the real agents once. Therefore, the mediator needs to use the interaction history with f* to decide the appropriate steering rewards to deploy, since the history is the sufficient information set including all the information regarding f* availale to the mediator.
1-- [T]. u, (- ue } 11 )T., Te+1 [[. un)] to
We want to clarify that in our steering framework, we will first solve Obj. (I. and then deploy g to steer real agents. The learning and optimization of &* in Obj. ( only utilizes simulators of F. Besides, after deploying v/* to real agents, will not update v6* with the data generated during the interaction with real agents. This is seemingly different from common online learning algorithms (Dean
which conduct the learning and interaction repeatedly (Dann and Brunskill 2015). But we want to highlight that, given the fact that d is depeede-,,,,nn,nt, it is already encoded in u how to make decisions (or say, learning) in the face of uncertainty after gathering data from real agents. In other words, one can interpret that, in Obj. ① the * to be optimized is an "online algorithm" which can "smartly" decide the next steering reward to deploy given the past interaction history. As we will justify in the following, our Obj. I can indeed successfully handle the model uncertainty.
Justification for Objective II We use Co.T(f) == Eo. of ut)] and Ag.(()
E [max, x 1)800l (Tr) - s/ IT) as short notes of the steering cost and the steering gap (of the terminal policy 1)) 1) respectively. Besides, we denote v :- (t) E Y maxfer A (vr((F) & e to be the collection of all steering strategies with e-steering gap. Based on these notations, we introduce
two desiderata, and show how optimal solution vt* of Obj. ① can achieve them.
Desideratum 1 (E- (E-Steering Gap). We say &i has E-steering gap, if max (f) E.
Desideratum 2 (Pareto Optimality). We say và Pareto Optimal if there does not exist another V/ V. such that (1) fff E F, (f) & Cwr(()) and A & (f)r(f); (2) 3f E F, s.t. either (f)) < (f. or (. < (f).
Proposition 3.3. (Justification for Obj. T By solving Obj. (1) 1h*h is Pareto Optimal; (2) Given any E, > 0, if ////= # Ø and 3 U N we have vi* E wote';
Next, we give some interpretation. As our primary desideratum, we expect the agents converge to some desired policy that maximizes the goal function yس after being steered for T steps, regardless of the true model f*. Therefore, we restrict the worst case steering gap to be small. As stated in Prop. 3.3 for any accuracy level & > 0, as long as e/ e/| gap is achievable, by choosing / large enough, we can approximately guarantee & has e-steering gap. For the steering cost, although it is not our primary objective, Prop. 3.3 states that at least we can guarantee the Pareto Optimality: competing with vi* there does not exist another 1i', which can improve either the steering cost or gap for some f E F without deteriorating any others.
PI fact, besides T also depends on other parameters like T, Unax: F and the initial policy πΙ For simplicity, we omit those dependence unless necessary.
5

---

but could Published as a conference paper at ICLR 2025
Given the above discussion, natural question is that: when is d non-empty, equivalently, when does a strategy v with E-steering gap exist? In Sec. we provide sufficient conditions and concrete examples to address this question in theory. Notably,
suggest conditions where & is non-empty for any 0, so that the condition /re/ Ø in Prop. 3.3 is realizable, even for large [FI. After that, in Sec. 5. we introduce algorithms to solve our Obj.
EXISTENCE OF STEERING STRATEGY WITH E- E-STEERING GAP
In this section, identify sufficient conditions such that Tf is non-empty. In Sec. 4.1 start with the special case when f* is known, i.e. F {.f². The results will serve as basis when we study the general unknown model setting with [F Sec. 4.2
4.1 EXISTENCE WHEN f IS KNOWN: NATURAL POLICY GRADIENT AS AN EXAMPLE
In this section, we focus on a popular choice of learning dynamics called Natural Policy Gradient (NPG) dynamics (Kakade 2001 Agarwal et al. 202T) (a.k.a. the replicator dynamics (Schuster and Sigmund 1983)) with direct policy parameterization. NPG is special case of the Policy Mirror Descent (PMD) (Xiao 2022). For the readability, we stick to NPG in the main text, and in Appx. [DII] we formalize PMD and extend the results to the general PMD, which subsumes other learning dynamics, like the online gradient ascent (Zinkevich) 2003).
Definition 4.1 (Natural Policy Gradient). For any [ [T]. h E [H].s) E S, the policy is updated by: 1f estimation for the advantage value A.. Aug with E,z"
T (-18%) (x. tug (sh; )). Here A 4ag is some random
[1 41p (sh,
We use Ar Apr (and A ) to denote the concatenation of the values of all agents, horizon, states and actions. We only assume r+tu be biased, which we call the "general incentive driven" agents. Assumption B (General Incentive Driven Agents). Vt [T]. <B[AAp+u,l 1.47+ > Aminl Irtu, Ir+ u. 11. X2 X 1 rr 112
is controllable and has positive correlation with A rtt
A
Irtu,
Note that the exact NPG is captured by the special case with Amin = Amax 1. For NPG, since the policy always bounded away from O. We will use II := [T|Vn, h, ah, Th (anl s/)) 0} to denote such feasible policy set. We state our main result below.
Theorem 4.2 (Informal). Suppose of is Lipschitz n, given any initial क. II+,, for any >> if the agents follow Def. 4.1 under Assump. and T and Umax are large enough, we have the # Ø.
Our result is strong in indicating the existence of steering path for any feasible initialization. The * proof based on construction. The basic idea design the u, so that A oc log N. for some target policy π I (approximately) maximizing ny then can guarantee the convergence of n, towards π under Assump. B The main challenge here would be the design of u4. We defer the details and the formal statements to Appx.
4.2 EXISTENCE WHEN f* IS UNKNOWN: THE IDENTIFIABLE MODEL CLASS
Intuitively, when f is unknown, if we can first use a few steering steps T < T explore and identify
f*, and then steer the agents from Tp to the desired policy within T - I steps given the identified f+, we can expect & * Ø. Motivated by this insight, we introduce the following notion.
Definition 4.3 (65 5 -dentifiable). Given
(0, 1), we say F is (ő, (5, -identiiii,,,,,,, fMLEel > - 8, where [[ = if E is true and otherwise O; SMLE arg max SEF 11 log [TT [T,, u:).
max, min [
Intuitively, FF is (8, T iidentiiiiie, if 3t, s.t. after T steering steps, the hidden model f can be identified by the Maximal Likelihood Estimation (MLE) with high probability. Next, we provide a general of (6, T -ddentiiiee function classes with T5. upper bounded for any 8 (0. 1).

---

Published as a conference paper at ICLR 2025
Example 4.4. [tne-Step Difference] If Vπ II, there exists steering reward ur E U, s.t. miny. (f r + Un), f' TT r + ux)) > Ç, for some universal Ç > 0, where H is the Hellinger distance, then for any E (0, F is (6, -identiiide with 7 = O - log F
Based on Def. we provide a sufficient condition when T is non-empty.
Theorem 4.5. [A Sufficient Condition for Existence] Given any > O, (F;
if < T,
s.t. (1) F is (2 .T) -ideentiie, (2) 5/2 (F; mT) + Ø for any possible गे generated at step T during the steering.
We conclude this section by noting that, by Thm. the above condition (2) is realistic for NPG (or more general PMD) dynamics. The proofs for all results in this section are deferred to Appx.
5 LEARNING (APPROXIMATELY) OPTIMAL STEERING STRATEGY
In this section, we investigate how to solve Obj. (T. Comparing with the episodic RL setting, the main challenge learn history-dependent policy. Since the history space grows exponentially in T, directly solving Obj. ( can be computationally intractable for large T. Therefore, the main focus of this section is design tractable algorithms overcome this challenge.
As special case, when the model is known, i.e. == { by the Markovian property, Obj reduces to normal RL objective, and a sete-dependent steering strategy & II 2 is already enough. For completeness, we include the algorithm but defer to Alg. 3 in Appx. B.4 In the rest of
this section, we focus on the general case [F] > In Sec. 5.1 we investigate the solutions when [Fl is small, and in Sec. 5.2
we study the more challenging case when [F] is large.
5.1 SMALL MODEL CLASS: DYNAMIC PROGRAMMING WITH MODEL BELIEF STATE
A Partially Observable MDP Perspective In fact, we interpret Obj. I as learning the optimal policy in POMDP, in which the hidden state is (Te, ). i.. a tuple containing the policy and the hidden model f uniformly sampled from F, and the mediator
only partially observe the policy Te. It is well-known that any POMDP can be lifted to the belief MDP, where the state is the belief state of the original POMDP. Then, the optimal policy in the belief MDP is exactly the optimal history-dependent policy in the original POMDP (Ibe 2013). In our case, for each step & E [7], the belief state is (T 6r), where b, == [Pr(f[(m) [ ue 1 n /EF is the "model belief state" defined to be the posterior distribution of models given the history of observations and actions. When [F] is small, the model belief state be !! by running any RL algorithm on the lifted MDP. In Proc. [.
111 is low dimensional and computable. Learning &b is tractable
we show how steer in this setting. We defer the detailed algorithm of learning such belief-state dependent strategy to Alg. 4 in Appx. B.5
Procedure 1: The Steering Procedure when [F]] is Small
Input: Model Set F; Total step T'; Solving Obj. (T] by learning belief state-dependent strategy vieeteer by Alg. with JF and T. Deploy with Beteer to steer the real agents for T steps.
5.2 LARGE MODEL CLASS: A FIRST-EXPLORE: -HEELLLLL--ETEE-----EE EXPLOIT FRAMEWORK
When [F] is large, the method Sec. 5.1 is inefficient since the belief state b, is digensiieniion.l.. In fact, the above POMDP interpretation implies the intractability of Obj 11 for large |Fl: the number of hidden states of the POMDP scales with [F]. Therefore, instead of exactly solving Obj- ( we turn to the First-Explore-Ther
(FETE) framework as stated in Procedure
The first Î < T steps the exploration phase, where we learn and deploy exploration policy Explore maximizing the probability of identifying the hidden model with the MLE estimator. The
Herr highlight the dependence initial policy, model, and time for clarity (see Footnote
7

---

Published as a conference paper at ICLR 2025
remaining T steps belong to the exploitation stage. We first estimate the true model by the MLE with the interaction history with real agents. Next, we learn an exploitation strategy to steer real agents for the rest T T' steps by solving Obj. I with F = {fMLE), time T - T and the initial policy 7 if MMLE is the true model.
Justification for FETE We cannot guarantee that Desiderata & are achievable, because do not exactly solve Obj. However, F is (6/ T )-identifiable (Def. 4.3) and we choose T x T can verify Pr(SMLE f*) > - 8 in FETE. Therefore, can still expect the exploitation policy v Exploit steer the agents to approximately maximize steering cost for the rest steps.
with reasonable
Procedure 2: The Steering Procedure when
[ is Large (The FETE Framework)
Input: Model Set F; Total step T'; Exploration horizon T; Exploration Phase
*/
Learn an exploration strategy Explore <- arg max F Ener Priii w ui ~ v..
arg max fer E log (T++1 u(]l-
Deploy y) Explore to steer the real agents and collect [TT, u1, Th 247 t++1}
Exploitation Phase
Estimate SMLE + arg max fEF 21-1 log f(TT+( Te. 24.)
Deploy Exploit +
arg maxy Enr m7 (TT -++1 ET 17 (Te, ue) 7
We conclude this section by highlighting the computational tractability FETE. Note that when computing Exploit we treat fMLE the true model, Therefore, the only part where we need to learn a history-dependent strategy is the exploration stage, and the maximal history length is at most T, which can be much smaller than T. Moreover, in some cases, it is already enough to just learn hiitooyy indeeended Explore to do the exploration (for example, the model class in Example 4.4)
Exploit is enough.
Comparison with Canyakmaz et (004) Both SIAR-MPC in Canyakmaz et al. (2024) and our FETE (Procedure 2 adopt
structure. We examine the differences between two algorihms from two aspects: exploration strategy and model estimation strategy. Regarding exploration strategy, SIAR-MPC uses noise-based random exploration, whereas we adopt a more strategic approach, which uses the identification success rate as a signal to learn the exploration policy, Empirical results in Sec. 6.2 demonstrate the higher efficiency of our methods. In terms of model estimation strategy, SIAR-MPC estimates the hidden model by solving a constrained regression problem (Eq. (8) in Canyakmaz et al. (2024)), while solve MLE objective. In principle, our MLE objective is more general and can recover the regression problem SIAR-MPC choosing, F to be the function class including Gaussian noise perturbed dynamics with side-information constraints introduced in Canyakmaz et al. (2024).
EXPERIMENTS
In this section, we discuss our experimental results. For more details of all experiments in this section (c.g. experiment setup and training details), we defer to Appx. G The steering horizon is set to be 500, and all the error bar shows 95% confidence level. We denote [x] == max (0, z).
6.1 LEARNING STEERING STRATEGIES WITH KNOWLEDGE OF f
Normal-Form Stag Hunt Game In Fig, (b). we compare the agents' dynamics with/without steering, where the agents learn to play the Stag Hunt Game in Fig. (a). We report the experiment setup here. Both agents follow the exact NPG (Def. 4.1 with A A with fixed learning rate 0.01. For the steering setup, choose the total utility sp and PPO to train the steering strategy (one can choose other RL or control algorithms besides PPO). We also conduct experiments in representative zero-sum game 'aathhing Pennies', which defer the details to Appx. G.2
8

---

Published as a conference paper at ICLR 2025
Grid World Stag Hunt Game: Learning Steering Strategy with Observations on Agents' Behaviors In the previous experiments, we consider the direct parameterization and the state space X' II = R+ has low dimension. In real-world scenarios, the policy space II can be extremely rich and high-dimensional if the agents consider neural networks as policies. In ad- dition, the mediator may not get access to the agents' exact policy æ because of privacy issues. This motivates us to investigate the possibility of steering agents with observations on agents' behavior only (e.g. trajectories of agents in game G), instead of the full observation of æ. In Appx. F we justify this setup and formalize it as a partially observable extension of our current framework. We consider the evaluation in grid- world version of the Stag Hunt Game as shown in Fig. (a). In this setting, the state space in game becomes pixel-based images, and both agents (blue and red) will adopt Convolutional Neural Networks (CNN) based policies with thousands of parameters and update with PPO. We train steering strategy, which only takes the agents' recent trajectories as input to infer the steering reward. As shown in Fig. (bb). without direct usage of the agents' policy, we can still train a steering strategy towards desired solution.
4.0
3.0
2.0
setal
1.0
with sleering steering
10 Steering Step t
15
Figure 2: Grid-World Version of Stag Hunt Game. Left: Illustration of game. Right: The perfor- mance of agents with/without steering. Without steering, the agents converge to go for hares, which has sub-optimal utility. Under our learned steering strategy, the agents converge to a better equilib- rium and chase the stag.
6.2 LEARNING STEERING STRATEGIES WITHOUT KNOWLEDGE OF f*
Small Model Set F Belief State Based Steering Strategy In this part, evaluate Proc.
1
designed for small F. We consider the same normal-form Stag Hunt game and setup as Sec. 6.
while the agents update by the NPG with random learning rate a [E]+, where [M, 0.3"
Here the mean value is unknown to the mediator, and we consider a model class F == {fo 7. f1.0]
including two possible values of μ e {0.7, 1.0). We report our experimental results in Table
Table I: Evaluation for Proc. 1 (Averaged over 25 different initial πT see Appx. G.1
(a) Performance in fo.7
(b) Performance in fLD
p( A A & E)
C..T
p AArr & E)
C
0.99 + 0.01
10.6 + 0.3
1.00 0.00
8.2 + 0.2
0.13 - 0.02
7.6 0.2
2 .
1.00 + 0,00
5.6 + 0.2
1.0
1/ Belier
0.87 + 0.05
10.5 0.4
Heliel
0.99 0.01
6.1 + 0.3
Firstly, we demonstrate the suboptimal behavior if the mediator ignores the model uncertainty and just randomly deploys the optimal strategy of fo.7 or fi.- To do this, we train the (history-independenn) optimal steering strategy by Alg. as if know f* fo.7 (or f fi.)), which we denote as [ we first set the accuracy level e = 0.01, and search
20,7 (or ))). To meet with our Desideratum] the minimal so that the learned steering strategy can achieve s-steering gap (see Appx. G.3.1 Because of the difference in μ. we have B = 70 and 3 20 in training v and v/ respectively, and empirically, we observe that vö.7 requires much larger steering reward than v As we marked in red in Table (a) and (b), because of the difference in the steering signal, 16,7 consumes much higher steering cost to achieve the same accuracy level in f1.0, and vi. may fail to steer agents with fo.r to the desired accuracy. Next, we train another strategy V via Alg. which predicts the steering reward based on both the agents' policy π and the belief state of the model. As we can see, 1/ Beteet can almost always achieve the desired E-steering gap with reasonable steering cost.
Large Model Set FF: The FETE Framework In this part, we evaluate the FETE framework (Proc. 2 in Sec. 5.2 We consider cooperative setting with N 10 players. Each agent has two actions A and B. and the mediator only receives non-zero utility when all the agents cooperate together to take action A, i.e. 17 (π)) := I T" (A). The agents do not have intrinsic rewards (r = 0), but the mediator's can steer them to maximize its own utility by providing additional steering rewards.

---

Published as a conference paper at ICLR 2025
We consider "avaricious agents" with varying de- grees of greediness, who tend to decrease the learn- ing rates if the payments by mediator are high, Conse- quently, they require more steering steps to converge to the desired policies, poten- tially earning more incen- tive payments from the me- diators. More concretely, the learning rate of agent is On := [En] with En ~ (115--1mmm.. [Vm x²]+, 0.5²). where 1rt is a scaling factor and A" > is the threshold exhibit
1.0-
Oradi
Gradi
FETE
PETB FETE-RE
Ax Prihing
FETE-RE
.N
0.02
2
Random Expleration
Our
30 100
200
300
0
f True Models
f
0
Steering Step
Trun Models
Figure Evaluation for Proc. 2 Left: Accuracy of MLE estimator
(MLE) after doing exploration for t steps. Ours can achieve near 100% accuracy after 30 steering steps, while the random exploration takes more than 300 steps. Middle and Right: Average steering gap and steering cost of Oracle, FETE and FETE-RE. Our FETE achieves competitive performance comparing with Oracle, and significantly outperforms FETE- RE (adaption of SIAR-MPC (Canyakmaz et al. 2024) our setting) in terms of steering gap.
avaricious behavior. In our experiments, the model uncertainty comes from multiple possible realiza- tion of X (0.25, 0.75, +20), which results in an extremely large model class JF with |F[ 3 Here \ 00 corresponds to normal agents whose learning rates are stable. The mediator does not know the agents' types {}"] [E[]]]] in advance, and can only observe one learning rate samples {an) [an]ne[[]] of agents per iteration E [T] and estimate the true types from those samples. We consider the fixed initial policy with Vn E [N], x (A) = (B) 1/3, and set the maximal steering reward U maxx 1.0.
To understand the exploration challenge, note that, during the exploration phase, if the steering signal u is not strong enough, i.c. Vi < X", , the mediator may fail to distinguish those avaricious agents from the normal ones, because they behave exactly the same. Such failure can lead to undesired outcomes in the exploitation phase: higher steering rewards can accelerate the convergence of normal agents, but can lead to larger steering gaps for avaricious agents.
We provide the evaluation results in Fig. First, we compare the exploration efficiency. We can see the clear advantage of our strategic exploration in FETE (Procedure 2 compared with basse random exploration (Canyakmaz et al.
2024). Next, we compare the steering gaps and costs of three methods: (i) F FETE; (ii) FETE-RE; (iii) Oracle if the mediator knows f* in advance and solving Obj. I with F = { Here FETE-RE RE can be regarded as adaption of SIAR-MPC (Canyakmaz) al. 2024 our case by replacing strategic exploration in FETE with random exploration (see
Appx. for more explanation). We choose exploration horizon T 30 suggested by the previous exploration experiment, and report results for three realizations of f e (f1, f2. fa). For fi and f2. all the agents share X" = 0.75 and +00, respectively. fa is a mixed setup where A = 0.75 for 1 < 5 and A +00 for 5 < & 10. As we can see, comparing with Oracle, both the steering gap and cost of our FETE are competitive. Moreover, thanks to our strategic exploration method, FETE exhibits significiant advantage over Canyakmaz et al. (222)) in terms of steering gaps.
CONCLUSION
In this paper, we introduce the problem of steering Markovian agents under model uncertainty. We provide theoretical foundations for this problem by formulating a novel optimization objective and providing existence results. Moreover, we design several algorithmic approaches suitable for varying degrees of model uncertainty in this problem class. We test their performances in different experimental settings and show their effectiveness. Our work opens up avenues for compelling open problems that merit future investigation. Firstly, future work could aim to identify superior optimization objectives that guarantee strictly better performances cost than ours. Secondly, when applying our strategies in real- wall-wrrld applications, constraints the steering reward budget could be added. Finally, the framework could be generalized to permit non-Markovian agents.
terms of steering gap and
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENT
The work is supported by ETH research grant and Swiss National Science Foundation (SNSF) Project Funding No. 2000211207343 and SNSF Starting Grant. VT is supported by an ETH AI Center Doctoral Fellowship. HHN is supported by the Swiss National Science Foundation under Eccellenza Grant 'Markets and Norms,' as well as under NCCR Automation Grant 51NF40- 180545.
REPRODUCIBILITY STATEMENT
The code of experiments in this paper and the instructions for running can be found in https: thw.. fiawe www.wwwwwwwaggggg..ocm.. Steerinegng Baainngaaaaaaaa Markovian, Barriin___geee A
REFERENCES
Abel, D., Barreto, A., Van Roy, B., Precup, D., van Hasselt, H. P., and Singh, S. (2024). A definition of continual reinforcement learning. Advances in Neural Information Processing Systems, 36.
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. (2021). On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98):1-77.
Akin, E. and Losert, V. (1984). Evolutionary dynamics of zero-sum games. Journal of mathematical biology, 20:231-258.
Auer, P., Jaksch, T., and Ortner, R. (2008). Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21.
Azar, M. G., Osband, I., and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In International conference machine learning, pages 262-272. PMLR.
Bai, Y., Jin, C.,, and Yu, (2020). Near-optimal reinforcement learning with self-play. Advances in neural information processing systems, 33:2159-2170,
Balcan, M.-F., Blum, A., and Mansour, Y. (2013). Cireumventing the price of anarchy: Leading dynamics to good behavior. SIAM Journal on Computing, 42(1):230-264.
Başar, T. and Berhard, P. (2008). H-infinity optimal control and related minimax design problems: dynamic game approach. Springer Science & Business Media.
Baumann, T., Graepel, T., and Shawe-Taylor, J. (2020). Adaptive mechanism design: Learning to
promote cooperation. In 2020 International Joint Conference on Neural Networks (IJCNN) pages 1-7. IEEE.
Burda, Y., Edwards, H., Storkey, A., and Klimov, O. (2018). Exploration by random network distillation. arXiv preprint arXiv:1810.1220 12299..
Cai, Y., Luo, H., Wei, C.-Y., and Zheng, W. (2024). Near-optimal policy optimization for correlated equilibrium in general-sum markov games. arXiv preprint arXi::2401.15240.
Camerer, C. F. (2011). Behavioral game theory: Experiments in strategic interaction. Princeton university press.
Canyakmaz, I., Sakos, I., Lin, W., Varvitsiotis. A., and Piliouras, G. (2024). Steering game dynamics towards desired outcomes. arXiv preprint arXiv:2404.01066.
Chakraborty, S.. Bedi, A. S., Koppel, A., Manocha, D., Wang, H., Wang, M., and Huang, F. (2023). Parl: A unified framework for policy alignment in reinforcement learning. arXiv preprint arXiv:2308.02588
Chen, S., Yang. D.. Li. J., Wang. S., Yang, Z., and Wang, Z. (2022). Adaptive model design for markov decision process. In International Conference on Machine Learning, pages 3679-3700. PMLR.
11

---

Published as a conference paper at ICLR 2025
Costabile, K. A. and Klein, S. B. (2005). Finishing strong: Recency effects in juror judgments. Basic and Applied Social Psychology. 27(1):47-58.
Curry, M., Thoma, V., Chakrabarti, D., McAleer, S., Kroer, C.,, Sandholm, T., He, N., and Seuken, (2024). Automated design of affine maximizer mechanisms in dynamic settings. Proceedings of the AAAI Conference on Artificial Intelligence, 38(9):9226-633.
Dann, C. and Brunskill, E. (2015). Sample complexity of episodic fixed-horizon reinforcement learning. Advances Neural Information Processing Systems, 28.
Dann, C., Lattimore, T., and Brunskill, E. (2017). Unifying pac and regret: Uniform pac bounds for
episodic reinforcement learning. Advances in Neural Information Processing Systems, 30.
Daskalakis, C., Fishelson, M., and Golowich, N. (2021). Near-optimal no-regret learning in general games. Advances in Neural Information Processing Systems, 34:27604-77616.
Daskalakis, C., Foster, D. J., and Golowich, N. (2020). Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33:5527- 5540.
Deng, Y., Schneider, J., and Sivan, B. (2019), Strategizing against no-regret learners. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché- Alché-Buc,, F., Fox, E., and Garnett, R., editors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc.
Ding, D., Wei, C.-Y., Zhang, K., and Jovanovic, M. (2022). Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. In International Conference on Machine Learning, pages 5166-522 5220. PMLR.
Dong, K., Wang, Y., Chen, X., and Wang. L.. (2019). Q-learning with ucb exploration is sample efficient for infinite-horizon mdp. arXiv preprint arXiv:1901.093::
Durand, R. B., Patterson, F. M.. and Shank, C. A. (2021). Behavioral biases in the nfl gambling market: Overreaction news and the recency bias. Journal of Behavioral and Experimental Finance, 31:100522.
Fiez, T., Chasnov, B., and Ratliff, L. (2020). Implicit learning dynamics in stackelberg games: Equilibria characterization, convergence analysis, and empirical study. In III, H. D. and Singh, A., editors, Proceedings of the 37th International Conference Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 3133-3144 PMLR.
Foerster, J., Chen, R. Y., Al-Shedivat, M., Whiteson, S., Abbeel, P., and Mordatch, I. (2018). awareness. In Proceedings of the 17th International Conference
Learning with on Autonomous Agents and MultiA Systems, pages 122-130.
Fudenberg, D. and Levine, D. K. (1998). The Theory of Learning in Games, volume 1 of MIT Press Books. The MIT Press.
Gerstgrasser, M. and Parkes, D. C. (2023). Oracles and followers: Stackelberg equilibria in deep multi-agent reinforcement learning. In Krause, A., Brunskill, E.. Cho, K., Engelhardt, B., Sabato, S., and Scarlett, J., editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 11213-1122 11236. PMLR.
Giannou, A., Lotidis, K., Mertikopoulos, and Tataais-GGaragkouul E.-V (2022). On the convergence of policy gradient methods to nash equilibria in general stochastic games. Advances in Neural Information Processing Systems, 35:7128-7141
Gong, L.,, Yao, W., Gao, J., and Cao, M. (2022). Limit cycles analysis and control of evolutionary game dynamics with environmental feedback. Automatica, 145:110536
Guo, X., Li, L., Nabi, S., Salhab, R., and Zhang, J. (2023). Mesob: Balancing equilibria & social optimality.
Harsanyi, J. C. and Selten, R. (1988). A general theory of equilibrium selection in games. MIT Press Books, 1.
12

---

Published as a conference paper at ICLR 2025
Harsanyi, J. C. and Selten, R. (1992). general theory of equilibrium selection in games. The MIT Press Classics. The MIT Press, Cambridge Mass, [2nd printing] edition.
Hernandez-Leal, P., Kaisers, M., Baarslag, T., and De Cote, E. M. (2017). A survey of learning in multiagent environments: Dealing with non-stationarity. arXiv preprint 1rXiv:1707.09138
Huang, J., He, N., and Krause, A. (2024a). Model-based rl for mean-field games is not statistically harder than single-agent rl. arXiv preprint arXiv:2402.05724.
Huang, J., Yardim, B., and He, N. (2024b). On the statistical efficiency of mean mean-field reinforcement learning with general function approximation. International Conference on Artificial Intelligence and Statistics, pages 289-297. PMLR.
lbe, O. (2013). Markov processes for stochastic modeling. Newnes.
Jacobson, D. (1973). Optimal stochastic linear systems with exponential performance criteria and their relation deterministic differential games. IEEE Transactions on Automatic control, 1832):124-13.
Jin, C., Allen-Zhu, Z.. Bubeck, S., and Jordan, M. (2018). Is q-learning provably efficient? Advances in neural information processing systems, 31.
Jin, C., Liu, Q. Wang, Y. and Yu, T. (2021). V-learning-a simple, efficient, decentralized algorithm for multiagent rl. arXiv preprint arXiv:21 145555.
Kakade, S. M. (2001). A natural policy gradient. Advances in nearal information processing systems, 14.
Khetarpal, K., Riemer, M., Rish, and Precup, D. (2022). Towards continual reinforcement learning:
A review and perspectives. Journal of Artificial Intelligence Research, 75:1401-1476.
Leonardos, S., Overman, W., Panageas, I., and Piliouras, G. (2021). Global convergence of multi- agent policy gradient in markov potential games. arXiv preprint arXiv:2106.0/966
J., Yu, J., Nie, Y. M., and Wang, Z. (2020). End-to-end learning and intervention in games.
Littman, M. (1994). Markov games as a framework for multi-agent reinforcement learning. In Machine learning proceedings 1994, pages 157-163. Elsevier.
Liu, B., Li, J., Yang, Z.., Wai, H.-T., Hong, M., Nie, Y., and Wang. 7. (2022). Inducing equilibria via incentives: Simultaneous design-and-play ensures global convergence. Advances in Neural Information Processing Systems, 35:29001-29013.
Lu, C., Willi, T., De Witt, C. A. S., and Foerster, J. (2022). Model-free opponent shaping. In International Conference on Machine Learning, pages 14398-14411, PMLR.
Luo, Z.-Q., Pang, J.-S., and Ralph, D. (1996). Mathematical Programs with Equilibrium Constraints. Cambridge University Press.
Mäs, M. and Nax, H. H. (2016), A behavioral study of "noise" in coordination games. Journal of Economic Theory, 162:195-208.
Mertikopoulos, P., Papadimitriou, C., and Piliouras, G. (2018), Cycles in adversarial regularized learning. In Proceedings of the twenty-ninth annual ACM -IAM symposium on discrete algorithmss, pages 2703-277 2717. SIAM.
Monderer, D. and Tennenholtz, M. (2004). K-implementation. J. Artif. Int. Res., 21(1):37-62.
Newton, J. (2021). Conventions under heterogeneous behavioural rules. The Review of Economic Studies, 2894))209-22188
Osband, I., Blundell, C., Pritzel, A., and Van Roy, B. (2016). Deep exploration via bootstrapped dqn. Advances in neural information processing systems, 29.
13

---

Published as a conference paper at ICLR 2025
Paarpom, K., Eksin, C., Weitz, J. S., and Wardi, Y. (2018). Optimal control policies for evolutionary dynamics with environmental feedback. In 2018 IEEE Conference on Decision and Control (CDC), pages 1905-1910.
Paccagnan, D. and Gairing, M. (2021). In congestion games, taxes achieve optimal approximation. In Proceedings of the 22nd ACM Conference on Economics and Computation, EC '21, page 743-744, New York, NY, USA. Association for Computing Machinery.
Page, L. and Page, K. (2010). Last shall be first: A field study of biases in sequential performance evaluation on the idol series. Journal of Economic Behavior & Organization, 73(2):186-)
Raffin, A., Hill, A., Gleave, A., Kanervisto, A., Ernestus, M., and Dormann, N. (2021). Stable- baselines3: Reliable reinforcement learning implementations. Journal of Machine Learning Research, 22(268):1-8.
Ratliff, J., Dong, R., Sekar, S., and Fiez, T. (2019). A perspective on incentive design: Challenges and opportunities. Annual Review of Control, Robotics, and Autonomous Systems, 2(1):305-338.
Richl, J., Ramazi, P., and Cao, M. (2018), A survey the analysis and control of evolutionary matrix games. Annual Reviews Control, 45:87-106.
Roughgarden, T. and Tardos, É. (2004). Bounding the inefficiency of equilibria in nonatomic congestion games. Games and Economic Behavior, 47(2)3389 403.
Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O. (2017). Proximal policy optimization algorithms. arXiv preprint arXiv:1707.06347.
Schuster, P. and Sigmund, K. (1983). Replicator dynamics. Journal of theoretical biology, 100(3):533- 538.
Shen, H., Yang, Z., and Chen, T. (2024). Principled penalty- -hased methods for bilevel reinforcement learning and rlhf. arXiv preprint arXiv:2402.0668 06886.
Skyrms, B. (2004). The stag hunt and the evolution of social structure. Cambridge University Press.
Thoma, V., Pasztor, B., Krause, A., Ramponi, G., and Hu, Y. (2024). Stochastic bilevel optimization with lewer-level contextual markov decision processes. arXiv preprint arXiv:2406.0157
Wang. J., Song, M., Gao, F., Liu, B., Wang, Z., and Wu, Y. (2023). Differentiable arbitrating in zero- sum markov games. In Proceedings of the 2023 International Conference on Autonomous Agents and Multiagent Systems, AAMAS '23, page 1034- 1043, Richland, SC. International Foundation for Autonomous Agents and Multiagent Systems.
Wang, K., Xu, L., Perrault, A., Reiter, M. K., and Tambe, M. (2022). Coordinating followers to reach better equilibria: End-to-end gradient descent for stackelberg games. Proceedings of the AAAI Conference on Artificial Intelligence, 36(5):5219-5277.
Wei, C.-Y., Jahromi, M. J., Luo, H., Sharma, H., and Jain, R. (2020). Model-free reinforcement learning in anfinite-horizon average-reward markov decision processes. In International conference on machine learning, pages 10170-10180 80. PMI.R.
Willi, T., Letcher, A. H., Treutlein, J., and Foerster, J. (2022). Cola: consistent learning with opponent-learning awareness. In International Conference Machine Learning, pages 23804- 23831. PMLR.
Willis, R., Du, Y., Leibo, J., and Luck, M. (2023). Resolving social dilemmas through reward transfer commitments. Adaptive and Learning Agents Workshop: Conference date: 29-05-2023 Through 30-05-2023.
Xiao, L. (2022). On the convergence rates of policy gradient methods. The Journal of Machine Learning Research, 23(1):12887-1222)
Yang, J., Li, A., Farajtabar, M., Sunehag. P., Hughes, E.,, and Zha, H. (2020). Learning incentivize other learning agents. In Proceedings of the 34th International Conference on Neural Information Processing Systems, NIPS 20, Red Hook, NY, USA. Curran Associates Inc.
14

---

Published as a conference paper at ICLR 2025
Yang, J., Wang, E.,, Trivedi, R., Zhao, T., and Zha, H. (2022). Adaptive incentive design with multi- agent meta gradient reinforcement learning. In Proceedings of the 21st International Conference Autonomous Agents and Multiagent Systems, AAMAS '22, page 1436-1445, Richland, SC. International Foundation for Autonomous Agents and Multiagent Systems.
Yardim, B., Cayci, S., Geist, M., and He, N. (2023). Policy mirror ascent for efficient and independent learning in mean field games. In International Conference on Machine Learning, pages 39722- 39754. PMLR.
Zhang, B. H., Farina, G., Anagnostides, I., Cacciamani, F., McAleer, S. M., Haupt, A. A., Celli, A., Gatti, N., Conitzer, V., and Sandholm, (2023). Steering no-regret learners to optimal equilibria. arXiv preprint arXiv:2306.05222
Zhang, K., Yang. Z., and Basar, T. (2019). Policy optimization provably converges nash equilibria in zero-sum linear quadratic games. Advances in Neural Information Processing Systems, 32.
Zhang, K., Yang, Z., and Başar, T. (2021), Multi-agent reinforcement learning: A selective overview of theories and algorithms. Handbook of reinforcement learning and control, pages 321-384.
Zhao, S., Lu, C., Grosse, R. B., and Foerster, (2022). Proximal learning with opponent- awareness, Advances in Neural Information Processing Systems, 35:26324-263366
Zhong, H., Yang, Z., Wang. Z., and Jordan, M. I. (2024). Can reinforcement learning find stackelberg- nash equilibria in general-sum markov games with myopically rational followers? J. Mach. Learn. Res., 24(1).
Zinkevich, M. (2003). Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th international conference on machine learning (icml-03), pages 928-936.
15

---

Published as a conference paper at ICLR 2025
CONTENTS
Introduction
1.1
Closely Related Works
2
Preliminary
3
The Problem Formulation of the Steering Markovian Agents
Existence Steering Strategy with s-Steering Gap
4.1
Existence when f is Known: Natural Policy Gradient as an Example
4.2
Existence when f Unknown: the Identifiable Model Class
5
Learning (Approximately) Optimal Steering Strategy
5.1
Small Model Class: Dynamic Programming with Model Belief State
5.2
Large Model Class: A Hiine-Explonee/Teee--ppooo Framework
6
Experiments
6.1
Learning Steering Strategies with Knowledge of 8*
6.2
Learning Steering Strategies without Knowledge of f
Conclusion
10
Frequently Used Notations
18
Missing Details in the Main Text
18
B.
A Real-Wort World Scenario that Can be Modeled Stag Hunt Game
18
2
Additional Related Works
18
B 3
A Brief Introduction to Markoy Decision Process
20
4
Algorithm for Learning Optimal (History- Indeeedde)) Strategy when Known
20
B.5
Algorithm for Learning Belief-State Dependent Steering Strategy
20
Missing Proofs in Section
20
Missing Proofs for Existence when the True Model f Known
22
D.I More Details about Policy Mirror Descent
22
D.2 Proofs for the Existence of Desired Steering Strategy
23
D.2.1 Special Case: PMD with Exact Advantage- Valuc
23
D.2.2 The General Incentive Driven Agents under Assump.
25
E Missing Proofs for Existence when the True Model f is Unknown
26
Generalization to Partial Observation MDP Setup
28
F1 POMDP Basies
28
16

---

Published as a conference paper at ICLR 2025
F22
Steering Process as a POMDP
29
Missing Experiment Details
29
G.1
About Initialization in Evaluation
29
G.2
Experiments for Known Model Setting
30
G.2.1
Experiment Details in Normal- Stag Hunt Game
30
G.2.2
Experiment Details in Grid World Version of Stag Hunt Game
30
G.2.3
Experiments in Matching Pennies
31
G.3
Experiments for Unknown Model Setting
32
G.3.1
Details for Experiments with Small Model Set J
32
G.3.2
Details for Experiments with Large Model Set
33
G.4
Explanation of the Consistency of the Adaption
33
G.5
Summary of the Compute Resources by Experiments in this Paper
Additional Discussion about Generalizing Results
34
17

---

Published as a conference paper at ICLR 2025
A
FREQUENTLY USED NOTATIONS
Notation
Description
G
A finite-horizon general-sum Markov Game
N
The number of agents
S,A
State space and action space of the game G
H
The horizon of the game G
P
Transition function of the game G Reward function of the game G
The agents' policy (collection of policies of all agents)
The initial policy
M
A finite-horizon Markov Decision Process (the steering MDP) State space and action space of M
X,U
r
The horizon of M (i.e. the horizon of the steering dynamics) (Stationary) Transition function of M The steering cost function of M
post
The history-dependent steering strategy by mediator
(or un for specific horizon
The steering reward function
U max
The upper bound for steering reward
Agents learning dynamics (T = f in the steering MDP) The goal function of M The model class of agents dynamics (with finite candidates)
F
Regularization coefficient in Obj. [
Cp.r(/) (f)
The total expected steering cost E. -t cos uc)
The steering gap: E [max, 17 (T) 10 (TT+1))
The collection of all history dependent policies
T as a short note of The lir+uu
T,Uma 11)
(t e V W [max, ()800((T) - s7 (TF+1) < c}
Qui Qur+u Vn. An.
The Q-value, V-value and ad value functions for agent
fMLE b
The Maximal Likelihood Estimator (introduced in Def. 4.3
Model belief state [Pr(f]( we 1 Te Te)r E R
Explooe Exploit
The exploratioon/exllottttioo policy in FETE framework.
00), 00),00),00)0()00000,3
Standard Big-O O notations, (.) omits the log terms.
B MISSING DETAILS IN THE MAIN TEXT
B. A REAL-WORLD SCENARIO THAT CAN BE MODELED AS A STAG HUNT GAME
As a real-world example, the innovation adaption can be modeled as a (multi-player) Stag Hunt game. Consider situation involving a coordination problem where people can choose between an inferior/unsuusainable communication or transportation technology that is cheap (the Gather action) and superior technology that is sustainable but more expensive (the Hunt action). more and more people buy products by the superior technology. the increasing profits can lead to the development of that technology and the decrease of price. Eventually, everyone can afford the price and benefit from the sustainable technology. In contrast, if people are trapped by the products of the inferior technology due to its low price, the long-run social welfare can sub-optimal. The mediator's goal to steer the population to adopt the superior technology.
B.2 ADDITIONAL RELATED WORKS
We first complements the comparison with Zhang et al. (2023) in Sec. [.] by noting a minor but worth to be mentioned difference between setting and (Zhang et al. 2023 in terms of incentive
18

---

Published as a conference paper at ICLR 2025
schemes. While they consider that the mediator influences the agents' learning dynamics through scalar payment function, we operate with additional steering rewards in a dinteiiiimnninnal reward vector space. As result, there may not exist direct ways to translate the steering strategies between both settings, especially in the bandit feedback setting where only the sampled actions of agents can be observed (Zhang et al. 2023).
Opponent Shaping In the RL literature a line of work focus on the problem of opponent shaping.
where agents can influence each others learning by handing out rewards (Foerster et al. 2018 Yang
et al, 2020; Willi et al. 2022] Lu et al.; 2022 Willis et al. 2023 Zhao et al. 2022 Although the ways of influencing agents are similar our setting, we study the problem of mediator that
acts outside the Markov Game and steers all the agents towards desired policies, while in opponent
shaping the agents themselves learn to influence each other for their own interests.
Learning Dynamics in Multi-Agent Systems In multi-agent setting, is an important question to design learning dynamics and understand their convergence properties (Hernandez-Leer et al. 2017). Previous works has established near-optimal convergence guarantees to equilibra (Daskalakis) et al. 2021 Cai et al. 2024). When the transition model of the multi-agent system is unknown, many previous works have studied how to conduct efficient exploration and learn equilibria under uncertainty (Jin et al.; [222 Bai et al. 2020 Zhang al. 2021 Leonardos et al. 2021 Yardim et al., 2023) Huang et al. 2024b a). However, most these results only have guarantees on solving an arbitrary equilibrium when multiple equilibria exists, and it is unclear how build algorithms based on them to reach some desired policies to maximize some goal functions.
Mathematical Programming with Equilibrium Constraints (MPEC) MPEC generalises bilevel optimization problems where the lower level consists of solving equilibrium problem (Luo ett al. 1996). (Li et al. 2020: Liu et al.; 2022 Wang et al.] 2022 2023 Yang et al.] 2022). These works consider variants of an MPEC and present gradient based approaches, most which rely on computing hypergradients via the implicit function theorem and thus strong assumptions on the lower level problem, such as uniqueness of the equilibrium. Most games fail to satisfy such constraints. In
contrast, our work makes no assumptions on the equilibrium structure and instead mild assumptions on the learning dynamics.
Game Theory and Mechanism Design In Game Theory, setup such as ours can be modelled as a Stackelberg game. Several works have considered finding Stackelberg equilibria using RL (Gerstgrasser and Parkes, 2023) Zhong et al. 2024) or gradient-based approaches (Fiez et al., 2020). Deng et al. (2019) showed how agents manipulate learning algorithms to achieve more reward, as they were playing a Stackelberg game. Related problems are implementation theory (Monderer and Tennenholtz 2004) and equilibrium selection (Harsanyi and Selten 1992). Moreover, the field of mechanism design has been concerned with creating economic games that implement certain outcomes as their equilibria. Several recent works have considered mechanism design on Markov Games (Curry et al. 2024: [Baumann et al., 2020 Guo et al.] 2023). In the case of congestion games, mechanisms have been proposed circumvent the price of anarchy (Balcan et al.) (201)] Paccagnan and Gairing 2021 Roughgarden and Tardos 2004), i.c. equililbria with low social welfare.
There is also a line of work has focused on control strategies for evolutionary games (Gong et al. 2022; Paarporn et al.) 20118). However, the game and learning dynamics differ significantly from our approaches, we refer the reader to Ratliff et al. (0119;
setting. For a full survey of
Riehl et al. (2018).
Bilevel Reinforcement Learning Bilevel RL considers the problem of designing an MDP ByD-by for example changing the rewards-ww with a desireable optimal policy. Recently, several works have studied pradient-based approaches to find such good MDP configurations (Chen et al.) 2022 Chakraborty et al.] 2023; Shen et al., 2024 Thoma et al., 2024). While similar in some regards, in this setting we assume the lower level a Markoy Game instead of just an MDP. Moreover, our aim is not to design a game with a desireable equilibrium from scratch, but to take a given game and agent dynamics and steer them with minimal additional rewards to desired outcome within certain amount of time. Therefore our upper-level problem is a strategic decision decision-making problem, solved by RL. instead of running gradient descent on some parameter space.
19

---

Published as a conference paper at ICLR 2025
Episodic RL and Non-Episodic RL Most of the existing RL literature focus the episodic learning setup, where the entire interaction history can be divided into multiple episodes starting from the same initial state distribution(Dann and Brunskill 2015 Dann et al. 2017). Comparing with this setting, our finite-horizon non-episodic setting is more challenging because the mediator cannot simply learn from repeated trial-and-error. Therefore, the learning criterions (e.g. no-regret (Azar et al., 2017; Jin et al., 2018) or sample complexity (Dann and Brunskill] 2015)) in episodic RL setting not suitable in our case, which targets at finding near-optimal policy in maximizing return. This motivates us to consider the new objective (Obj.
To our knowledge, most of the previous works use "non-episodic RL" to refer to the learning in infinite-horizon MDP. One popular setting is the unfinitehhrrizn MDPs with stationary transitions, where people consider the discounted (Schulman al. 2017: Dong et al., 2019) or average return (Auer et al.) 2008: Wei et al. (022). The infinit-
setting with non-stationary dynamics is
known as the continual RI. (Khetarpal et al. [022]] Abel et al.) 2024), where the learners "never stops
learning" and continue to adapt to the dynamics. Since we focus on the steering problem with fixed and finite horizon, the methodology in those works cannot be directly applied here.
Most importantly, we are also the first work to model the steering problem as a RL problem.
B.3 A BRIEF INTRODUCTION MARKOV DECISION PROCESS
hnrie-horizon Markov Decision Process is specified by a tuple M :- (x,, T. (1) 17 "r }
where 21 is the fixed initial state, T is the horizon length, X' is the state space, U is the action space. Besides, T == {T,, (TT)) with T, X
( denoting the transition function 1 = (n he(] with 7% : X' U [0, is the normal reward function and 1/!-m X' x [o. I denotes the additional terminal reward function. In this paper, without further specification, we will consider history dependent non-stationary policies V := (e == {v1,,.. 3/r |vt E [T]. th
(X' u) X A(U)). Given a & V episode of M is generated by: Vt E [T], U 14-1 1 V) < (Ire, ud), 1++1 Te(-kar,, uz); y/erm m) (IT+1);
Weeee ue
B.4 ALGORITHM FOR LEARNING OPTIMAL (HISTORY-INDEPENDENT STRATEGY WHEN f* IS KNOWN
Algorithm 3: Learning with Known Steering Dynamics
Input: Model Set F= := { Initial steering strategy vb = { he(Ty; Regularization coefficient 3; Iteration number K;
for k 1, 2, K do
Agents initialize with policy nィ. Sample trajectories with Vicc. Vt [T]]:
k (1(+1 Tht f ('(', + ut)), nt ( ut) t
Update k++ - RLAlgori thm ( (at utt nt IT- u (B spoo (0o0
end
Output
2+ TPCK.
B.5 ALGORITHM FOR LEARNING BELIEF-STATE DEPENDENT STEERING STRATEGY
C MISSING PROOFS IN SECTION 3
T1 By solving Obj. ( (1) 1/. Pareto Optimal; (2) Given any e, > 0, we/lFl + Ø and 3 > Umax NHTT
Proposition 3.3. [Justification for Obj.
we have vf* E wett';
'In this paper, we focus on stationary transition function, i.c. T₁ TT.
20

---

Published as a conference paper at ICLR 2025
Algorithm 4: Solving Obj. (1) by Learning Belief State-Dependent Strategy
Input: Model Set F; Regularization coefficient (3; Initial steering strategy ob : (112) Iteration number K:
for k = 1, 2.... K" do
Sample f ~~ Uniform(F); Initialize á = π.
Sample trajectories with wf from simulator of f:
V [T] bp := Pr(- mr. u² .... Ti- u Tt), ui ~ w/t (-10), mt),,
o|+ f(- f(|mmf + u!), of - mp (TT ut)
Update w/++1 RIAlgori paallgorhhh(ppp wb (1T bf), ut nh 1t=1 13- (
12
end
return
1+ = witk = (EX 11=1
Suppose 1F/)FF non-empty, we denote (/5/1F) as one of the elements in &e//Fl, By definition, since max ny (T) is fixed, we have:
Proof.
1
Σ
-
arg max
F
jeF
If T/33 2 Unaa NHT F
by definition,
e'
BD f.T) - C(b*, ((10)))))))
(
Σ JEF
BA f,T) -CU5)11 ,,17)
| f,T) AlU*, (..)))))))))) Umax N HT
JEF
(the steering reward u E [0, Umax))
1 F
3
E
(,),, U NHT
(W51FFl V Tmusa (F))
|
FEF
U
NT
E
ECV U UT feF
[
As direct observation, if -
v00 ffT)] + E A(V", f.T) $ the RHS will |
be strictly less than O, which results in contradiction. Therefore, we must have VfEF, A TTT)) & [F| Ey..n f,T) <
which implies 3 E viete"
Next, we show the Pareto Optimality. If there exists vi and such that
For all f' E F with + f", C(b* .fT) > C(b,,, T) and A(**, ,JT) > A(H,f.T);
For J, either C(ub (,7) > C(b, S. 7) and ((tb*, > A(v; (,T) or C(1 >
C(p,,, and A (1b* (,T) AT),
Therefore, we must have:
1
1 Σ (A ..T)) C
- < F
F
JEJ
JEJ
which conflicts with the optimality condition of Obj. JI.
Remark C.1. Intuitively, Pareto optimality ensures the steering rewards predicted by x are not necessarily large. For example, consider agents following NPG dynamics (Def. 4.1 Given any
steering strategy vp and a constant c >> O, consider another steering strategy (-) := +() + c, i.e. by increasing the steering reward predicted by 1o with Note that the learning dynamics under both d and vf are the same. and therefore the final steering gaps are the same. Pareto optimality implies that of will never be more preferable than db.
21

---

Published as a conference paper at ICLR 2025
D MISSING PROOFS FOR EXISTENCE WHEN THE TRUE MODEL f IS KNOWN
In this section, we study the Policy Mirror Descent as a concrete example. In Appx. D.I we provide more details about PMD. Then, study the PMD with exact updates and stochastic updates in Appx. D.2. and D.2.2 respectively. The theorems in Sec. 4.1 will be subsumed as special cases.
D.1 MORE DETAILS ABOUT POLICY MIRROR DESCENT
Definition D.1 (Policy Mirror Descent). For each agent n e [M], the updates at step t E [T'] follows:
Vh E [M]] Sh E S, (11s)))) (-1s)) + A Apm tup (s, (Update in the mirror space)
0 1, 1, (-1sA) (Map A back to the primal space) T (.(s))))))))))))))))))))) arg min D pm (2, 2 (-1s), =EA(An)
1, (11s) -
(Projection)
Similar to Def. 4.1 here An A/pr +ug some random estimation for the advantage value A. A|pm tug krr tug (sh, -)]= O. Besides, 6% E R|S||A| denotes the variable in the dual space. 6" dom (²) - R is function satisfying Assump. C below, which gives the mirror map Vø"; (Vø")=l the inverse mirror map; Don(2, 2) == 6" (2) <VØ" (3), 2) is the Bregman divergence regarding o"
with -, [4 m
Assumption C.
We assume for all [N], 6² is p-strongly convex and essentially smooth, i.e. differentiable and [ø"(=*)] + + for any sequence z² E dom(ø") converging to point on the boundary of (o").
By Pythagorean Theorem and the strictly convexity of Døn, the projection л in Def. D.1 is unique.
Lemma D.2. Given a convex set and a function o which is p-strongly convex on C, we have
arg min Da(2, (Vo) arg min (z (Vz) & 11: 02/2- sec
-arggnn sel
Proof. Given any dual variables 01 and 02 and their projection
arg mingec Do(z, (V6)='(0)) and 22 == arg min Dz(z, (B2)), by the first order optimality condition, we have:
V (Vo(z)) - 01, - 21) 2 0, (Vo(22) 02 2 22)
If we choose in the first equation and = 21 in the second equation, and sum together, have:
( vo(z) Vo(z)) 02, 22) 7 0,
By strongly convexity of o. the above implies:
(0: 0z 21
=22 > (VØ(21) - Vo(22)) - 22) 2 n || - 1
Therefore,
M| 22l & |10 0211.
and we finish the proof.
Next, we discuss concrete examples.
Example D.3 (Natural Policy Gradient). If we consider the mirror map and Bregman Divergence
generated by o² (z) == Yn z(a") log z(a"), we have D²(",, 22) (L(=1l)22), and recover
the NPG in Def. 4.1 Note that 6" is 1-strongly convex the convex A(A"), Assump. C
is
satisfied with μ
22

---

Published as a conference paper at ICLR 2025
Example D.4 (Online Gradient Ascent (Zinkevich, 2003), If we consider the Euclidean distance generated by ln-norm (²) = 2 | we recover the projected gradient ascent
Definition D.5. For each agent [N], the updates step [7'] follows:
hh [H]. Sh E S, x (*+1)(+1s)) Proja(ar) (= (m", (-18h) + a A upr (8, 1)),
Note that the projection with Euclidean distance is 1-Lipschitz, Assump.
C is satisfied with f 1.
Other Notations and Remarks In the following, use II to be the "feasible policy set" (for NPG in Def. II refers to be set of policies bounded away from 0), such that for any π II,, there exists dual variable 0 corresponding ग,, i.e.,
Vn [N], E [H] 3/ E S, T - arg min Dø ( (z, (V6")) zeA(A")
In the following Lem. D.6 we show that constant shift in " (-18)) does not change the projection result. Therefore, when we say the dual variable A associated with given policy we only consider those f satisfying Eng- ag [0][(]] (a st)] 0.
Lemma D.6 (Constant Shift does not Change the Projection). For any n E [M]. regularizer o" satisfying conditions in Assump. and any 0 E RlA"1, consider the constant vector cl, where c E RR constant and 1 {1, 1 RIAA have:
arg min D (z, (V)")-1(0)) = arg min Den (2, (Vo")~ cl)) x=((A")
sEA(A")
Proof.
arg min <=)(An)
D (Vx")) + cl)
arg min =EA(A")
(²()) (0 (0 cl,²)
= arg min *A(A")
(=) (0, +c
(we have constraints that 2 E A(A"))
arg min
(=(2) (0,
=e((Ar)
arg min D Den (2. zEA(A")
D.2 PROOFS FOR THE EXISTENCE DESIRED STEERING STRATEGY
We first formally introduce the Lipschitz condition that Thm. 4.2
requires.
Assumption D (1780l) is T--Lipschitz). For any π. T' E IT, 1 T
s/soal (x')) < T.[T π T'|l2-
In the following, in Appx. D exactly the true advantage value AT (which can be regarded as a special case of Assump. B)) Then, in Appx. D.2.2] we study the general setting and prove Thm. 4.2 special case of PMD.
warm-up, start with the exact case when the estimation AT
D.2.1 SPECIAL CASE: PMD WITH EXACT ADVANTAGE-VAL VALUE
Lemma D.7 (Existence of Steering Path between Feasible Policies). Consider two feasible policies
m, मे which are induced by dual variables (0T, mee and ) he]j)e respectively. If the agents follow Def. D.I with exact Q value and start with π n. as long as Umax > sn)]l), exists a (history-indepeedennt) steering strategy ib := (Weherrr with the II U. s.t., TT = f.
2.H + 2 (maxn,h..e.. O (ag)ss) (a])))))) Eag-sr (4s ( (a (s))))) (T]]))))))] there
Proof. For agent n [N]. given a ाe. we consider the following steering reward functions
(sh, a.) =vii (sh, a.) An. (sh, aF)) Ean (1ss [2] (sh, aip)
(2
A. (Sh. af:]]
23

---

Published as a conference paper at ICLR 2025
min (Vi, (3h, 0%) Fn
Ahppa (5h, 0%h
B - (1ss))
(1ss)) I (5h, (%)
Appp (5h, [m]]]
where VG,
A R will be defined later. By construction, have:
Bog (llon) Ri (sh: am)1
(2)
min ( (5h 0%) Appp (5h. af) Eg (1nn) (3h, (g) Alpp (3), ag)]], $1.0%
(3)
which is a constant and independent w.r.t. sn, ag. Besides, by definition, we can ensure the non- negativity of uh As result,
Ci e [T].
uup (sh, a%) =
4 hip (sh, aB) + uh, a + Ch(ss)
(Eq.
(s 0% C% (sa).
where we use (sh) and C% (sx) to denote some state-dependent but aetion-independen value. According to Lem. D.6 under the above steering reward design, the dynamics of Te TT can be described by the following dynamics:
Vt [T], Vn [N], h [H], sn E S
(+,1n((|sMh - 07, (+lsh) + avi a.)
(5)
m (+1sh) arg Døm (z, 11 SEA(A")
(6)
Now we consider the following choice of ViA
(sh, ai)) = 0 (X sh) 0% (aj]ss))
aT
which implies 0r+1 = 0, and therefore, TT स. Besides, the steering reward function can be upper bounded by:
with (sh. an 2 max I/ (5h, a.)) Eh.ag
An.mi (3k, ai)) Ea- (la 27) -A//" (5), aT)]]
2 max
$2H
(R(a))))) 0 (H
aT n.h.shag
which implics the appropriate choice of Umax-
Theorem D.8. Under Assump. D given the initial π II, for any T > 1 and 0, if the agents follow Def. 4.1 with exact Q value, then V * D if the following conditions are satisfied:
There exists feasible से II+ such that op max 2o (TT
Denote 0 and θ the dual variables associated with and स. respectively. We require Umax (0 (a% (s.) -0 (a))))s))))
2H 2 (maxx,
Proof. The proof is directly application of Lem. D.7
NPG Special Case
For NPG, we have the following results.
Lemma D.9. Given VT, #े 11+, T > 1, the agents follow Def. 4.1 with exact adv-value and start from π = n, by choosing Umax appropriately, there exists a (history- innieeneend))))nett) steering strategy
= (Welee with 1/, II U, s.t., TT+1 N.
Theorem D.10. Under Assump. D given any initial क E II for any T > 1 and E > 0, if the agents follow Def. 4.7 with exact value, by choosing Umax appropriately, have T Ø.
24

---

Published as a conference paper at ICLR 2025
Proof for Lem. D.9 and Thm. D.10 The proof is by directly applying Lem. D.7 and Thm. D.8 since NPG is a special case of PMD with KL-Divergence as Bregman Divergence. For any π, π II we consider the dual variables 0, such that:
(-sss) log (-1sa) Bag= a [[ (-(ss)) log # (-1sh) - Eog=az [lg #h (a sh)]
(7)
Choice of max in Lem. D.9 choice of U max
By applying Lem. D.7 and Thm. D.8 we consider the following
2 aT
# (sh, 0%) log
Eay x [log T (sh. 0%
Umax 3 2H
+
max n...88.0.
II.
(8)
"h (5h,
8h, (%)
"h sh: 1/
Choice of Umax in Thm. D.10 We denote n arg max well mo T
II+
When л ITT we can directly apply Thm. D.8 with π and choosing Umax correspondingly following Eq. (8).
However, in some cases, л* $ II because it takes deterministic action in some states. In that case, since rptual is L-Lipschitz in π,, can consider the mixture policy मे == (1 (1-0 ( +
(
Uniform- where Tniffoem is the uniform policy. As a result, we have Ā IT+ as well as
gpoaa (T) z maXxell 17000l (T) c. Then the Umax can be chosen following Eq.
8
D.2.2 THE GENERAL INCENTIVE DRIVEN AGENTS UNDER ASSUMP.
B
Theorem D.11 (Formal Version of Thm. 4.2 for the general PMD). Under Assump. Dand Assump.
C
given the initial गi := π E II+,, for any O, if the agents follow Def. 4. under the Assump.
then V Tumax # Ø if the following conditions are satisfied:
There exists feasible से E 11+t such that a7 3 maxT 10 (TT)
Denote 0 and 0 as the dual variables associated with π and स,, respectively. We require Umaxe 2> 2(H
Amin (1 +
Anan
X2 log yT1 01)2) and O
-10-011).
ax
Amnax
man
Me
Remark D.12. In Thm. D.2.2 our bound for Umax here is just worst-case bound handle the
noisy updates the worst case. With high probability, the dual variable 9r will converge A and the steering reward does not have to be as large as Umax-
Proof. Given a Te, we consider the following steering reward uty:
uh (Sh, at) = -. (sh, ah Te) An. (sh, an) Egn (Hlaa) (lw.aalllaaaaao (sn, The TI.) A. (sh, aR] hlr"
min ( 0hi TT) - ARipi (5hy a%) - Eg m (11 (i,,,, (8h, The oT)) En.0h
A n.
App" (5h, 2h) ]}
Here we choose vin (Sh; 0%, nT) :- 1 (ag]ss) 0 (agls))) sx)). where Ø denotes the dual variable of policy मे and 7 will be determined later. Comparing with the design in the proof of Thm. D.& here the "driven term" vy need depend on n. because of the randomness in updates.
As we can see, u/ (8h, 0%)
> 0, and for each f,, we have:
E[[i - 0c+1 1 3
E[ 0
( 02, 0+11 0,)] + 0 - 0.1131
= =E 0.1121 20EK 0,, Ame A/ttw.!! ELI A frtu 12
$ (1 - 2Amin a X2 a²
max x2 [E[ - O2 1.1...
7
which implies
X a² / 0
E 0r+1 [| & (1 2\mia ?
25

---

Published as a conference paper at ICLR 2025
X Amna which implies, Amin
We consider the choice 7
E 0r+ $
min
)01 0
2 max
When 7 200
Amox log Amam
2L 012
co log
22 Annx
222116-613
x²²²
for some constant Co. we have:
μEE
B1
0T+1 [2] <
2L
which implies,
[[ )- ypunll ( 0 & 2 LE[] TT+ 1122 &
E 2
- 0
Next, we discuss the choice of Umax. by Assump. we know,
| Oc+1l
=I 0, aA prtue l2 E 110 0ell2 + all alllApttnal ll2
0 0.112 + amdmaxl 1 r 12
Amin )
{(1
0r//
Amax
where we use the fact that A | r 1l2 1110 0-112 and our choice of y. Therefore, for all [T].
100 0el12 & (1 +
Amin
yr110 0112. To ensure our design of u,,,, is feasible, we need to set:
Amax
Unax -2(H + 1 (1+ +
Amin
) 01(2)
Amax
=2(H + Amin (1
Amin )r 0l)2)
a
Amax
Proof for Thm. 4.2
As discuss in Example. D.3 Assump. satisfied with μ a direct application of Thm. with the same choice of dual variables as Eq. (7).
The proof
E MISSING PROOFS FOR EXISTENCE WHEN THE TRUE MODEL. f IS UNKNOWN
In the following, establish some technical lemmas for the maximal likelihood estimator. Given steering dynamics model class and the true dynamics f ~ Po and a steering strategy 11 U,
consider steering trajectory Thb = {TT1 U1 .... Thes WT. #1,+1) generated by: u ((()))) T
V [Tol.
where te+1 is independent w.r.t. Ty for l' < conditioning कę. In the following, we will denote T: = (TT, Ui,..., Te, Ue 1 to be the trajectory up to step t.
For any f F, we define:
To I f (T,
Pf(TT)) =
(10)
Given Trp we use Trp to denote the "tangent" trajectory {(TT,, u4 #t+1)) f* f*(ITT,, uz) is independently sampled from the same distribution T conditioning on the same n. and ut.
To where π
Lemma E.1. Let 1. IT U II be real-valued loss function. Define I(Tr.) To I(T,, ue Te+1) and L(Tr)) = Wob I(Tr. ur, #e+1). Then, for arbitrary L [To]. E[exp([[(7)) log Ezy, (exp(T((F))]7]]) =
26

---

Published as a conference paper at ICLR 2025
Proof. We denote E' == Ex,, [exp([(<T; u4, +f+1))( uu fM.. J. By definition, have:
E,, [exp( Σ ( Uy m
E
Therefore,
Er (exp( log Err, [exp( [ (FT,))](TO.
exp( 2
2-| (TT,, Ur T(+1))
Br - uny Errzo
776-1 (TT,, ur,]]
BrID [exp( (2 1(Te, ue (T+1))
expl L/1 1( (TT, ths T(+1)) 1))
Br Puto- uny B
P u (TT, WT, ill
1. E
expl 11==
Ta-1 [(T,, ue Te+1)) Euryti
MTTT:: uro TT
-Brzo 11
1 (TT.. un, Ill
To-1 F
E
To 1(T,, ue, -
expl
=Errg-
E
Lemma E.2. [Property of the MLE Estimator] Under the condition in Prop. 4.4 given the true model f* and any deterministic steering strategy vb II + U. define fMLE arg max 21=1 log (Te+1 Te, ue), where the trajectory is generated by:
u - ((()), T++1 ~ f (-1TT,, ut), then, for any 8 (0, 1), w.p. at least 5, we have:
V [To].
To
F
IHP [fuLLE(-1TT (T,,, un), (-(TT,, log(
Proof. Given model f F, consider the loss function:
log f( [((])))))))
if ( #
(T),, 0,
otherwise
Considering the event E:
8 8: (- Bra, lexp L (TTo) ] & -LM(TTO) + log( VJEF..
where we define (Tr,)) Besides, by applying Lem. I on Im defined above and applying Markov inequality and the union bound over all f F, we have Pr(E) > 1 On the event &, we have:
Et Iu T ue x++1) and (Tr.) f := Et= L (r,, ue T++1).
log Ery, [exp L fune (Fr.)) |Tro]
< ( + log( F
<IMLE(F IMLE(fMLE) + log( 8
< log
(fMLE maximizes the fog-likelihood)
8
Therefore,
To
f( Te, We (T.. Ue. f*1
log
log
V
8
fT TT,, Us
27

---

Published as a conference paper at ICLR 2025
s TT, ue (e. Uc f*]
E E W (1t un)
(- log 3 1
H (f(-ITe ue), f (- u)).
Example 4.4. [One-Step Difference] If V' II. there exists steering reward ur E U, s.t. miny,rer (- + ux), ( (-1 T. r + ux) )x 3 C. for some universal Ç > 0, where HH is the
Hellinger distance, then for any E (0, 1), F is (6, -identifiabll with T O log(
Proof. Consider the steering strategy (T)) u Given any ʃ F, and the trajectory sampled by [F if IMLE * J. have:
and f, by Lem. E.2 w.p. 1
2 log(
H² Te, u.), /MLE(- U.)) Tos.
By union bound over all f F, if log xo 1 + 1, the following holds:
max max S [L[ fMLE]] max fEJ
Bs
I[f = arg max PeF
log (Te, uel
21-6.
fer
Theorem 4.5. [A Sufficient Condition for Existence] Given any > (F(F; + Ø. iff < <T s.t., (1) F is 2m -ddentiifie (2) T T-T (F; my)) + Ø for any possible Tς. generated at step
T during the steering.
Proof. We denote t'Eaplrr (1EEppoor,)) (EE(] to be the exploration strategy to identify S* Given 2//2 Tz. we denote Unक : (w Meetr 1Te/2 T- (TT)) to be one of the steering strategy with s-optimal
gap starting from π77-
We consider the history- steering strategy &b := ( such that for & T, th Explore, and for all T. have vi. u
As a result, for any f E F. the final gap would be:
A ( Pr(SMLE = 2 + Pr(SMLE # f) Mmax & E,
which implies t E (F; TT).
F
GENERALIZATION TO PARTIAL OBSERVATION MDP SETUP
F.1 POMDP BASICS
Partial Observation Markov Decision Process A (finite-horzoon) Partial-Observation Markov Decision Process (with hidden states) can be specified by a tuple M := {v1, X,U, O, T, n, O}. Here F1 is the initial state distribution, L is the maximal horizon length, X' is the hidden state space, is the action space, is the observation space. Besides, T: X' x 21 - X' denotes the stationary transition function, O X A(O) denotes the stationary emission model, i.e. the probability of some observation conditioning on some state. We will denote H4, := O x Ui... x On to be the history space, and 7h, (01, uI, u1,..., 0z.) to history observation up step h. We consider the history dependent policy x = (w1,-.,, vH) with vh : Hr - ( Starting from the initial state I1, the trajectory induced by a policy v generated by:
wh [H],
o O(1Ia)) u, (ba())))), Th (o un), F4+1 T(- un).
'Here highlight the dependence initial policy, model, and time for clarity (see Footnote
28

---

Published as a conference paper at ICLR 2025
Steering Reward M1 (x(-l1)) (o,)
Steering Reward
~ Va 40 0z)
24
U2
02
Observation Emission
Observation Emission
0: O (x)
a
Xg
X3
11
T1
State Transition
122
T2
State Transition
n23
73
f( (m'. u'))
x²
1 +, +
66 (x))
1 G(: (xr
Figure Probabilistic Graphic Model (PGM) of the POMDP formulation of the steering process. Starting with the initial state 21 := (T1, for all f > 1, the mediator receives observation or (11[2)) and output the steering reward given the history u, v(-101, UI,..., 0z). The agents
then update their policies following the dynamics f and the modified reward function r +
F.2 STEERING PROCESS AS POMDP
Given game G, we consider the following Markovian agent dynamics:
V [T],
Tt. ~ We: Te+1 ~ [(-|Tr, Te,
where 7. == {s]
a1 1.k 1kk t.k
..... H
HH fk=1
is several trajectories generated by the policy πy.
In each step f, we assume the agents first collect trajectories Tı with policy Ty, and then optimize their policies following some update rule f((| T,, r). Comparing with the Markovian setup in Sec. 3 here / has additional dependence on the trajectories тr.
Based on this new formulation, the dynamics given the steering strategy is defined by:
Vt E [T], Tt Te. Ut ve>>/e(-TTT (/1(-ITT, U1,... Tt-1, 4:-1 TT), T+++1 f(-| ue),
In Fig. 4 we illustrate the steering dynamics by Probabilistic Graphical Model (PGM). Here we treat the joint of n. and T, as the hidden state at step and the trajectory тÜ the partial observation o received by the mediator. Next, we introduce the notion of decodable POMDP, where the hidden state is determined by a short history.
Definition F.1 Decooeadeelle POMDP). Given POMDP M, say it is m-decodale, if there exists a decoder の, such that, Fy 6(0n-m, Uh-mu my -h--1, 44-1, on).
In our steering setting, for any f F. is m-decodable, we just need learn steering strategy 1b : (O x t O 44, which predicts the steering reward given the past m-step history. This the motivation for our experiment setup in the Grid World Stag Hunt game in Sec. [6.1] More concretely, we assume the agents trajectories in the past few steps can be used as sufficient statistics the current policy, and use them as input of the steering strategy (see Appx. G.2.2 for more details).
G MISSING EXPERIMENT DETAILS
G.1 ABOUT INITIALIZATION IN EVALUATION
some experiments, we will evaluate our steering strategies with multiple different initial policy ai. in order to make sure evaluation results representative.
Here we explain how we choose the initial policies πe We will focus on games with two actions which is the only case we use this kind of initialization. For each player, given integer we
construct an increasing sequence with common difference Seq, := ( 2 :i.... 2:
2;-1 Then, we
consider the initial policies ग, such that π (a') = 1 - x (a²) Seq, t = 10=2((a (a E Seq, In this way, obtain of initial policies uniformly distributed in grids with common difference
29

---

Published as a conference paper at ICLR 2025
As conerete example, the initial points in Fig. (b) marked in color black is generated by the above procedure with 10.
G.2 EXPERIMENTS FOR KNOWN MODEL SETTING
G.2.1 EXPERIMENT DETAILS IN NORMAL-FORM STAG HUNT GAME
We provide the missing experiment details for the steering experiments in Fig. [.bb).
Choice of nynual We consider the total utility as the goal function. But for the numerical stability, choose ypam (T = Emee(N] (T) 10 where we shift the reward via the maximal utility value 10.
The Steering Strategy
The steering strategy is a 2- MLP with 256 hidden layers and tanh as the activation function. Given time step and the policy क.. { m²) with of (H) + T +²(G) 1 for n {1, 2), the input of the steering strategy is
(H) (G)
(H) (G)
(H) T((G)
( T T-t T((G)) 100
(log
log
log
log
(11)
Here the first (second) two components correspond to the "dual variable" of the policy (H) and (G) (H) and (G)), respectively; the last component is the time embedding because our steering strategy is time-dependent.
The steering strategy will output vector with dimension which corresponds the steering rewards for two actions of two players. Note that here the steering reward function u² S x AA L U Umax] (for agent 1) and 2² == S x 2 [0, m (agent is defined on the joint of state space and individual action space. This can be regarded as a specialization of the setup in our main text, where we consider u" S x A [0, max] Vn E [N], which defined on the joint of state space and the entire action space.
Training Details The maximal steering reward Umax is set to 10, and we choose 3 = 25. We the PPO implementation of StableBaseline3 (Raffin al. 202T). The training hyper-parament can be found in our codes in our supplemental materials.
During the training, the initial policy is randomly selected from the feasible policy set, in order to ensure the good performance in generalizing to unseen initialization points. Another empirical trick adopt in experiments is that, strengthen the learning signal of the goal function by including 7) (T²) for each step t E [T]. In another word, we actually optimize the following objective function:
R arg max
Ex. ...1 pool Σ fEF
Σ B. (TT))
11 1
(Te, uz)
(12)
NEW
The main reason is that here T 500 is very large, and if we only have the goal reward at the terminal step, the learning signal is extremely sparse and the learning could fail.
Other Experiment Results In Fig. 5 investigate the trade-off between steering gap and the steering cost when choosing different coefficients B. In general, the larger 3 can result in lower steering gap and higher steering cost.
G.2.2 EXPERIMENT DETAILS IN GRID-WORLD VERSION OF STAG HUNT GAME
We recall the illustration in LHS of Fig. 2 We consider 3x3 grid world environment with two agents (blue and red). At the bottom-left and up-right blocks, we have 'stag' and 'hares', respectively, whose positions are fixed during the game. At the beginning of each episode, agents start from the up- and bottom-right blocks, respectively.
For each time step h [H] every agent take four actions {up, down, left, right to move to the blocks next to their current blocks. But the agent hits the wall after taking the action (e.g. the agent locates at the most right column and takes the action ri right), it will not move. As long one
30

---

Published as a conference paper at ICLR 2025
10
Gx(((")
by. 2
5
3- ==25
= 10
Figure 5: Trade-off between Stecring Gap (Left) and Steering Cost (Right), (averaged over 5x5 uniformly distributed grids as initializations of ıi Appx. G.D.
agent reaches the block with either stag or hare, the agents will receive rewards and be reset to the initial position (up-left and bottom-right blocks). The reward is defined by the following.
If both agents reach the block with stag at the same time, each of them receive reward 0.25.
both agents reach the block with hares at the same time, each of them receive reward 0.1.
If one agent reaches the block with hares, will get reward 0.2 and the other get reward O.
In other cases, the agents receive reward 0.
We choose H 16. The best strategy that all the agents move together towards the block with Stag, within episode, the agents reach the Stag 16 / 2 times, and the maximal total return would be 0.25 = 4.0.
In the following, introduce the training details. Our grid-world environment and the PPO training algorithm is built based on the open source code from Lu et al. 2022).
Agents Learning Dynamics The agents will receive 3x3x4 image encoding the position of all objects to make the decision. The agents adopt CNN, and utilize PPO to optimize the CNN parameters with learning rate 0.005.
Steering Setup and Details in Training Steering Strategy Our steering strategy is another CNN, which takes the agents recent trajectories as input. More concretely, for cach steering iteration t, we ask the agents interact and generated 256 episodes with length H, and concatenate them together to a tensor with shape [256 H, 3, 3, 4]. The mediator takes that tensor as input and output an 3-dimension steering reward vector. Here the steering rewards corresponds to the additional rewards given to the agents when one of them reach the blocks with stag or hares (we do not provide individual incentives for states and actions before reaching those blocks). To be correspond to the additional reward for blue and red agents for the following 4 scenarios: (1) both agents reach stag together both agents reach hares together (3) this agent reach stag while the other does not reach stag (4) this agent reach hares while the other does not reach hares.
concrete, the 8 rewards
The steering strategy also trained by PPO. We choose the total utility as the goal function, and we adopt the similar empirical trick as the normal- form version, where we include n2 into the reward function for every t е [T] (Eq. (12). The results in Fig. is is the average of steering strategies trained by different seeds for 80 iterations. The two-sigma emror bar shown.
25 and learning rate 0.001. We consider
G.2.3 EXPERIMENTS IN MATCHING PENNIES
Matching Pennies is two-player zero-sum game with two actions H=Head and T=Tail and its payoff matrix is presented in Table
Choice of nntnal In this game, the unique Nash Equilibrium is the uniform policy π NE with n.NN (H) n "T.NBTT) function, i.c. 178oal - NB
for all n 21. We consider the distance with NE as the goal
Experiment Setups We follow the same steering strategy and training setups for Stag Hunt Game in Appx. G.2.T The agents follow NPG to update the policies with learning rate 10.
31

---

Published as a conference paper at ICLR 2025
Table 2: Payoff Matrix of Two-Player Game Matching Pennies. Two actions and T stand for Head and Tail, respectively.
H
T
H
(1,
-1-
(-1, I) (1,
T
(-1,
1)
No Steering
With Steering
1.0
1.0
10
A. (3e-3)
nP(tledd)
(H(ed
0.5
0.5
0.5
0.5 (HHad)
1.0
0.5 (HHad
B=10 25
10100
#=10
2= _ 100
(a) Dynamics of Agents Policies.
(b) Trade-off between Accuracy and Cost by 3.
Figure 6: Experiments in MatchingPennies. (a) and y correspond to the probability that agents take Head. Black dots mark the initial policies, and red curves represents the trajectories of agents policies. The steering strategy to plot the figure is trained with & = 25. (b) We compare B 10, 25, 100. Error bar shows 95% confidence intervals. (averaged over 5x5 uniformly distributed grids as initializations of IT Appx. G.I
Experiment Results guidance (Akin and Losert 1984 Mertikopoulos et al., (018). In contrast, our learned steering strategy can successfully guide the agents towards the desired Nash. Fig. (b-)), also report the trade-off between steering gap and steering cost with different choice of B.
As shown in Fig. (a),
observe the cycling behavior without steering
G.3 EXPERIMENTS FOR UNKNOWN MODEL SETTING
G.3.1 DETAILS FOR EXPERIMENTS WITH SMALL MODEL SET F
The results in Table T is averaged over seeds and the error bars show 95% confidence intervals.
Training Details for v and v The training of vū.7 and v1. follow the similar experiment setup Appx. G.2.2 except here the agents adopt random learning rates. For the choice of 8, we train the optimal steering strategy with 3 E {10, 20, 30, 40, 50, 60, 70, 80, 90, 100) for both fo.7 and achieve almost 100% accuracy (i.e. Ap, < e for almost all 5x5 uniformly distributed initial policies generated by process in Appx. G.1 As reported in the main text, obtain 70 for fu.7 and B 20 for f1.0-
fL.0, and choose the minimal 8 such that the resulting steering strategy
Training Details for Weellet For the training of Velleer the input of the steering strategy is the original state (Eq. (TT) appended by the belief state of the model. In each steering step [T]. we assume the mediator can observe a learning rate sample a, and use it to update the model belief state correspondingly. The regularization coefficient & for the training of theliet is set to be the expected regularization coefficient over the belief state b(fo.7) 70 b(fi.)) 20. another word, we use the sum of the coefficient of two models weighted by the belief state. This is reasonable by the definition of the reward function in the belief state MDP lifted from the original POMDP. v'eelier is trained the PPO algorithm.
During the training of Beliet. we find that the train not very stable, possibly because the chosen for two models are quite different. Therefore, keep tracking the steering gap of the steering strategy during the training and save the model as long as outperforms the previous ones in stecring gap. Our final evaluation based on that model.
32

---

Published as a conference paper at ICLR 2025
G.3.2 DETAILS FOR EXPERIMENTS WITH LARGE MODEL SET J.
We set Umax 1.0, and the random exploration strategy (red curve in the left sub-plot in Fig.
will sample the steering reward uniformly from the interval [0, maax We use the PPO (Raffin et al. 202T) to train of exploration policy and also the steering strategy given hidden model. To amplity the exploration challenge, we set 8 when x² (A) & 0.5 and increase to 3 10 when n" (A) & 0.5.
As a result, if the mediator follows first-explore- weeoore-tee-eeee thenthheeloore strategy and fail to distinguish avaricious agents from the normal ones, adopting large steering reward can lead to much worse performance.
For the training of exploration policy, although the learning signal If = SMLE] in Proc. 2 is supported by theory, it contains much less information than the posterior probability [Pr(f[ ,.,, TT, ur, Tr+1)] Therefore, empirically, we instead train a history-independer steering strategy maximize the posterior probability of f:
Explare - arg max
Σ JEF
Σ RE[N]
ITL Ui,... Tip (f1i)l
(13)
Here we use the sum of posteriors of A since the X"s are independent for all n [N]. We observe it results in better performance, and it is doable by keep tracking the model belief state of each agent. Be- sides, similar to Stag Hunt games, observe that using the posterior Pr(x"] [T, u1, .... Te, ue T++1) as rewards in the non-terminal steps t < T increase the performance, and we use the same trick (Eq. )
To plot the results in the middle and right sub-plots in Fig. 3 for each model f E (f1, f2, fa), we train three steering strategies (with the same state design in Eq. (T]). The first one is the oracle strategy, which starts with π and steering for 7 = 500 steps. The second one is the FETE strategy, including an exploration policy and another exploitation policy. The exploration policy is trained following the above Eq. (13) with exploration horizon T 30. Then, we estimate the model from samples generated by the exploration policy, and train another exploitation policy following the remaining step of FETE with exploitation horizon T = 470 (Procedure 2}. The third strategy FETE-RE RE is the same FETE except we just use random policy the exploration policy, and estimate the model by interaction samples generated by that. During the evaluation, for F FETE and FETE-RE, steer with the exploration policy for the first 30 steps, and execute the exploitation policy for the rest. The results are averaged over 5 seeds and two-sigma error bar is shown.
G.4 EXPLANATION THE CONSISTENCY OF THE ADAPTION
We first want to highlight it is not easy to have an apples-to-an to-apless comparison with (Canyakmaz jet al. 2024]. First, because the experiment setting in (Canyakmaz et al.) 2024) does not present significant exploration challenges, we design and decide to evaluate both methods in the "avaricious agents" setting (Fig. 3). Second, SIAR-MPE is specialized for polynomial function classes and the dynamics tractable by MPC, making it difficult to generalize beyond that setting. Therefore, we have to do some necessary adaption. To ensure the fair comparison, we consider to use FETE-RE as the adaption of SPAR-MPC in our setting. For the exploration stage, FETE-RE aligns with SIAR-MPC in using random exploration. For the model identification and exploitation phase, FETE-RE adopts MLE estimation and RL methods train the exploitation policy, which inherit the same inspirits as SIAR-MPC and also aligned with our original FETE.
From another perspective, the main focus of our empirical comparison between FETE and (Canyak- maz et al. 2024) is the impact of difffernnt exploration strategies on the final steering gap and steering costs. This reasonable. Because from the discussion in Sec. 5.2 we can conclude that our FETE is more general compared with SIAR-MPC in (Canyakmaz et al. 2024) in terms of both the model estimation strategy and exploitation strategy. The main distinction and improvement of our FETE
compared with (Canyakmaz et al. 2024) is our strategic exploration strategy.
G.5 A SUMMARY OF THE COMPUTE RESOURCES BY EXPERIMENTS IN THIS PAPER
Experiments Two-Player Normal-Form Games For the experiments in 'Stag Hunt' and 'Matching Pennies' (illustrated in Fig. I 5 6). we only use CPUs (AMD EPYC 7742 64-Core Processor). It takes less than 5 hours finish the training.
33

---

Published as a conference paper at ICLR 2025
Experiments on Grid-World Version of 'Stag Hunt' For the experiments in grid- world 'Stag Hunt' (illustrated in Fig. 2 we use one RTX 3090 and less than 5 CPUs (AMD EPYC 7742 64-Core Processor). The training (per seed) takes around 48 hours.
Experiments on N-Player Normal-Form Cooperative Games For the experiments in cooperative games (illustrated in Fig. B) we only use CPUs (AMD EPYC 7742 64-Core Processor). It takes less than 10 hours to finish the training.
H ADDITIONAL DISCUSSION ABOUT GENERALIZING OUR RESULTS
In this section, we discuss some extensions of the principle and algorithms in this paper more general settings.
Non-Tabular Setting When the game is non-tabular and its state and action spaces are infinite, the steering problem itself fundamentally challenging without additional assumptions, since the policies continuous distributions with infinite dimension and the learning dynamics can be arbitrarily complex. Nonetheless, when the agents' policies and steering rewards are parameterized by finite variables, our methods and algorithms still be generalized by treating the parameters as representatives.
As concrete example, the Linear- Quadratic (LQ) game is popular model involving countinuous state and action spaces (Jacobson) 1973 Başar and Bernhard 2008) Zhang et al., 2019). In zero-sum LQ game, the game dynamies characterized by linear system:
1+41 = Ar, + By: + Czu,
with one-step reward function
(It, Vts 24) - Ve, 21) x.. Qr: ye R" 2, R
Here Tt, Te+1 Rd the system states, Y/ 1m and 2, E IR r0 denote the actions of agents. Besides, the agents policies are parameterized by matrices K, E IRmixe xd Le E m xd i.e.
y/ K at =
Following the quadratic form of the original reward, one may consider quadratic steering reward functions with parameters θ, (0 reward for two agents at step / is specified by:
and E, = (E. =y 37), such that, the steering
u/ (Er. =)) = x, 0 x + y1 07 = =
uf Vt, 21) x. -. x. v Ei 2 2
and the reward after modification would be:
r' (Ii, Mt. mx) + // (It, 1/. 2) =1, (0, + Q) 1x + yo (0" + R"))r - =, (0) + R²) ((r,, v1, 21) + u (xt, y/1 zx) = (0, Q) v. (0) R R*) 2 (0) R')
Although the state, action and steering reward spaces are continuous, both the policies and steering reward are determined by their parameters. Therefore, the agents" learning dynamics can be modeled by a function f* mapping between those parameters instead:
(e44)))4)) f*(+l (L), agents" policies
(0, + Q. ON R O -.
R
Rd)
madified rewards
Besides, the learning of steering strategy is equivalent to learning a function mapping vé from parameters in history {(K,, L, θ, E, =- U {(K,,, L.]} to the next steering reward parameter E,), Since both the policy parameters and steering reward parameters have finite dimension, this problem is tractable under our frameworks.
34

---

Published as a conference paper at ICLR 2025
Uncountable function class F Our results can be extended to cases where the model class JF is infinite but has a finite covering number. We denote Feo as the Eg-cover for F, s.t.
E 3 E Feo: s.t. max TV (T((((1);))) - f'(-|T,; (1-TT.1)) u) & 80-
mell,
where TV denotes the total variation distance. algorithms with Fr.o instead of F. Under Assump. A we denote fco Fez is the function En close to f* By simmulation lemma, then we have:
If F is uncoutable but Fea is finite, run our
y (TT++]] E
(n) [TT+I)]]
ET Eo 7mma
rf poot TT, (Te, u:)]
E
cose (T uc]l ET
Eu max ondt nT, u..
As we can see, we can still optimize the objective in Eq. ①1) with Feg and then transfer guarantees on steering gap and cost for fö (e.g. the the worst case guarantees Prop. 3.3) to f* with additional O so) errors, which is ignorable when Eo small enough.
Non- Mon-Markovian Learning Dynamies In general, Markovian learning dynamics is intractable, as implied by the fundamental difficulty in learning optimal policies POMDPs. However, when some special structures exhibit, our methods for Markovian agents can be generalized. One example is the non-Markovian agents with finite-memory. i.e.,
T++1 (* ( r - Te, + Uz).
This can be reformulated by a Markovian dynamics
F (:120,, un),
1++1
with the same steering rewards as actions but a new definition of "state": := { T + Ut-m+1, Tt-1; r + U J. Comparing with Def. 3.1 the dimension of the state space is expanded by m times, which is still tractable for small m.
Neural Networks as Model Class to Approximate Complex f* The main principle for choosing iis to ensure our "realizability" assumption holds with high probability, i.e. the true model f F. The concrete choice of F depends on the prior knowledge we have about the agents' learning dynamics. In general, the less prior knowledge we have, the larger F should be ensure realizability, and vice versa.
In practice, one "safe-choice" can be consider a class of parameterized neural networks as F. since has been proven in deep RL and supervised learning literature that neural networks have powerful approximation ability when f* is potentially very complex. Because in our formulation, we allow the randomness of next policy T++1 (instead of a deterministic output) given π. and r + we may consider a neural network taking the concatenation π. r + u, and another random Gaussian vector & as inputs. Here the noise vector is introduced to model the stochasticity of π.
The parameters of neural networks are general continous variables, which implies the model class uncountable. However, if the parameters has bounded value range, number on the parameter space. If we consider Lipschitz continuous activation functions (which is most of the cases), it implies the bounded covering number.
show the finite covering
Besides, when considering neural networks, the resulting model class F can be extremely large and the MLE-basee strategic exploration in Procedure 2 will be inefficient. We highlight that design such exploration step in order to align with the main principle: the algorithm design should be supported by theoretical guarantees the performance of the learned steering strategy. This focus on theoretical rigor is the main factor limiting the scalability of our algorithms more complex settings. not very challenging adapt
Conversely, if we relax the requirements on theoretical guarantees, our algorithms to complex scenarios. For example, we can instead consider more scalable exploration methods, such as Random Network Distillation (RND) (Burda et al. 2018) or Bootstrapped DQN (Osband et al.] 2016). although without theoretical guarantees.
35


Reviews:
[{"review_id": "Gfl2NcjNv5", "reviewer": "Reviewer_M5wC", "summary": "This paper presents a framework for steering the behaviors of agents towards desired outcomes within a reinforcement learning setting, where the exact learning dynamics of the agents are not known. Specifically, this work introduces the concept of Markovian agents, whose decisions are based only on their current states and immediate rewards, and explores the challenges posed by model uncertainty in practical applications. To address these challenges, the study develops a non-episodic RL approach and proposes the First-Explore-Then-Exploit (FETE) framework. This strategy involves initially exploring to identify the most accurate model from a predefined class and then exploiting this model to effectively steer agent behaviors. The theoretical contribution of the paper establishes that if the model class of learning dynamics is identifiable within finite steps, then a steering strategy with an ε-steering gap can exist. The empirical results in the paper demonstrate that their algorithm can operate under the assumption that each player has only two actions.", "questions": "- While this paper usefully demonstrates the benefit of steering, it does not sufficiently address whether the proposed steering methods are adequately effective when compared to other potential steering strategies. For example, expanding the comparative analysis to include non-Markovian agent models could help justify the emphasis on Markovian agents in the introduction. Non-Markovian models, which account for past states and decisions in their decision-making processes, often represent more realistic and complex environments. Including such models in the analysis would provide a more comprehensive assessment of the proposed strategies.\n\n- Considering exploration is crucial for addressing the uncertainty in agents' learning dynamics, it would be valuable to investigate how an exploration-focused approach like Random Network Distillation (RND) could impact the results (more than random exploration FETE-RE in Section 6.2). This could provide practical insights into managing uncertainty more effectively in complex multi-agent environments.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The method introduced in the paper is commended for its intuitive and logical approach. By assuming that the learning dynamics of the agents are Markovian and can be learned in finite steps, the paper effectively simplifies the complex problem of steering under uncertainty.\n\n- The paper provides transparency regarding the experimental assumptions detailed in the appendices. Moreover, the experimental setup involves a wide range of learning rate combinations, specifically up to 3^10.\n\n- The paper is well-written and very easy to follow, with justification and explanation whenever needed in most places.", "weaknesses": "While I appreciate the application of reinforcement learning (RL) to address the steering problem, balancing exploration and exploitation amidst the uncertainty of agents' learning dynamics, but there are some concerns regarding the paper:\n\n- A primary challenge highlighted is the agents' reluctance to disclose their learning dynamics, creating fundamental model uncertainty. The theoretical discussion posits that if the model class $F$ of the agents is identifiable, then an epsilon-steering strategy is viable. It would enhance the paper if the theoretical sections could more explicitly address how understanding the model class $F$ effectively reduces this uncertainty, thus better connecting the theoretical insights with the algorithmic implementations.\n\n- The algorithm proposed in the paper relies heavily on accurately specifying agents' learning dynamics, which presents a significant challenge when considering real-world complexities where agents' behaviors are influenced by others, such as herd behavior or nonconformity. These dynamic inter-agent interactions introduce variability that the algorithm may not capture effectively, given its current design focused on binary or categorical decision-making scenarios. This specificity restricts its utility, particularly in more complex decision environments where outcomes are not merely binary and agent behaviors are interdependent and continuously evolving. Consequently, while the algorithm provides a structured approach to steering agent decisions within a controlled setting, its application to broader, more realistic scenarios involving complex agent dynamics and multiple decision variables may require significant adaptations to accommodate these behavioral complexity.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "n1gd5B7F7S", "reviewer": "Reviewer_EzpY", "summary": "This paper proposed an RL framework that helps multi-agent systems towards specific behaviors or policies using additional incentives or rewards, even without prior knowledge of agent learning models.", "questions": "1. The paper mentions comparison experiments with control methods. In which scenarios does the proposed method outperform control methods, and in which scenarios does it show similar or inferior performance?\n2. Could you provide a more precise definition of \"desired policies\" and \"desired behaviors”? What exactly does \"desired policy\" mean in this paper? Is \"desired behavior\" different from it?\n3. If we already know the desired policy, why is there still a need for learning? Are there certain situations in the steering problem where learning is still required, even if the desired policy is known?\n4. Why steering is necessary in multi-agent systems? Can existing algorithms find the equilibrium or approximated equilibrium for MAS?", "limitations": "", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 1, "contribution": 2, "strengths": "Strengths:\n\n1. The authors introduce a new objective function that balances the goal of steering agents toward a target policy while minimizing the overall steering cost.\n2. The paper provides sufficient conditions under which the proposed steering strategies are effective, ensuring a low gap between target and actual agent behavior and achieving Pareto optimality.\n3. The paper includes experimental results in different environments, demonstrating the algorithms' performance under varying model uncertainty conditions.", "weaknesses": "Weakness:\n\n1. Poor writing: The writing in this paper needs significant improvement; it appears to have been put together in a hurry, making it very difficult to read. As a new research problem, the steering problem has not been well-motivated or clearly formulated, leaving key concepts ambiguous. For example, the definitions of \"desired policies\" and \"desired behaviors\" are unclear, and it’s difficult to understand their precise meaning in this context. If we already know the desired policies, why any learning is necessary？ Furthermore, the concept of the \"mediator\" is not introduced or explained and suddenly appears in the paper. Similarly, the notation f∗ is introduced abruptly at line 210 without any prior explanation, creating confusion. The new learning objective presented in line 220 is also hard to understand and lacks sufficient clarification regarding its purpose and relevance.\n2. The transitions between paragraphs are also weak, resulting in a lack of cohesion throughout the text. Starting from the problem formulation section, the paper becomes increasingly difficult to follow, with unclear structure and insufficient explanations, making it hard for readers to grasp the main ideas and contributions.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qfHuPoR7ww", "reviewer": "Reviewer_oazJ", "summary": "The paper addresses the challenge of steering multi-agent systems towards desired policies without having prior knowledge of the agents' learning dynamics. The focus is on a new class of learning dynamics called Markovian agents. The authors propose a model-based non-episodic reinforcement learning (RL) framework and formulate an optimization objective incorporating history-dependent steering strategies to handle model uncertainty. The paper presents theoretical results and practical algorithms to achieve this steering, validated with empirical studies.", "questions": "1. What will happen if the model set $\\mathcal{F}$ is uncountably infinite?\n\n2. What will happen for a non-tabular MDP setup?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "*Conceptual Novelty and Relevance*: The paper introduces an approach to steering agents by focusing on Markovian agents with limited cognitive resources.\n\n*Theoretical Contributions*: The authors provide a comprehensive theoretical analysis, including sufficient conditions for achieving low steering gaps and the existence of history-dependent steering strategies. \n\n*Algorithmic Development*: The proposed algorithms (belief-state-based steering strategy for small model classes and a First-Explore-Then-Exploit (FETE) framework for large classes) effectively balance the trade-off between tractability and optimality.", "weaknesses": "This is a solid paper with well-grounded contributions. My primary concern, however, is that the current setting is limited to a tabular MDP with a finite model class. While this simplified setting is acceptable for a theoretical paper, the corresponding experiments appear relatively basic. I am curious about whether the proposed Steering Dynamics framework can be extended effectively to more realistic scenarios (or if the Steering Dynamics framework is helpful in any real-world situation?) involving non-tabular MDPs and an infinite model class.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)