Learning to Steer Markovian Agents under Model Uncertainty

## Abstract

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 dynamics. Motivated by the limitation of existing works, we consider a new and general category of learning dynamics called Markovian agents . We introduce a model-based non-episodic Reinforcement Learning (RL) formulation for our steering problem. Importantly, we focus on learning a 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 1 1 1 The code of all the experiments in this paper can be found in https://github.com/jiaweihhuang/Steering_Markovian_Agents . .

## 1 Introduction

Many real-world applications can be formulated as Markov Games (Littman,, ) 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, ()).
Because of the mismatch between the individual short-run and collective long-run incentives, or the lack of coordination in decentralized systems, agents following standard learning dynamics may not converge to outcomes that are desirable from a 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. 1-(a)), which are used to study a broad array of real-world applications including collective action, public good provision, social dilemma, team work and innovation adoption (Skyrms,, )(^2^22We defer a concrete and practical scenario which can be modeled by the Stag Hunt game to Appx. B.1).
Stag Hunt games have two pure-strategy NE, one of which is ‘payoff-dominant’, that is, both players obtain higher payoffs in that equilibrium than in the other. Typical algorithms may fail to reach the payoff-dominant equilibrium $(\texttt{H},\texttt{H})$ (LHS Fig. 1-(b)).
Indeed, the other equilibrium $(\texttt{G},\texttt{G})$ is typically selected when it is risk-dominant (Harsanyi and Selten,, ; Newton,, ).

This paper focuses on situations when an external “mediator” exists, who can influence and *steer* the agents’ learning dynamics by modifying the original rewards via additional incentives.
This kind of mediator can be conceptualized in various ways. In particular, we can think of a social planner who provides monetary incentives for joint ventures or for adoption of an innovative technology via individual financial subsidies.
As illustrated on the RHS of Fig. 1-(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 a secondary objective, the payments to agents regarding the steering rewards should be reasonable, that is, the *steering cost* should be low.

Figure: (a) Payoff Matrix of the Two-Player “Stag Hunt” Game. H and G stand for two actions Hunt and Gather. Both (H,H) and (G,G) are NE and (H,H) is payoff-dominant.
Refer to caption: x1.png

To our knowledge, Zhang et al., () is the first work studying a similar steering problem as ours.
They assume the agents are 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 entire history of learning.
In settings with limited cognitive resources and bounded rationality, it is natural to favor models where the agents only process a subset of the available information (Camerer,, ).
In particular, humans have been widely shown to rely overproportionally on recent experiences in decision making, known as ‘recency bias’ (Costabile and Klein,, ; Page and Page,, ; Durand et al.,, ).
Besides, there is evidence that behavioral dynamics that only rely on the most recent experience are able to fit behavioral data well in certain situations (Mäs and Nax,, ).
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 (modified) 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 a broader class of popular policy-based methods as concrete examples (Giannou et al.,, ; Ding et al.,, ), which are not covered by no-regret assumptions.
We also note that a concurrent work (Canyakmaz et al.,, ) considers a similar setting as ours, and we defer to Sec. 1.1 for further discussion.

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 is 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 episodic trial-and-error. Therefore, the most commonly-considered, fixed-horizon episodic RL (Dann and Brunskill,, ) 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, in 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 to learn desired steering strategies for Markovian agents
in the non-episodic setup under model uncertainty?
*

We consider a model-based setting where the mediator can get access to a model class $\mathcal{F}$ containing the agents’ true learning dynamics $f^{*}$.
We summarize and highlight our key contributions as follow:

- •
Conceptual Contributions:
In Sec. 3, we formulate steering as a non-episodic RL problem, and propose a novel optimization objective in Obj. (1), 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 $f^{*}$*, the optimal solution to Obj. (1) 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.
- •
Algorithmic Contributions: Learning a history-dependent strategy presents challenges due to the exponential growth in the history space. We propose algorithms to overcome these issues.
–
When the model class $|\mathcal{F}|$ is small, in Sec. 5.1, we approach our objective from the perspective of learning in a Partially Observable MDP, and propose to to learn a policy over the model belief state space instead of over the history space.
–
For the case when $|\mathcal{F}|$ is large, exactly solving Obj. (1) can be challenging. Instead, we focus on approximate solutions to trade-off optimality and tractability. In Sec. 5.2, we propose a First-Explore-Then-Exploit (FETE) framework. Under some conditions, we can still ensure the directed agents converge to the desired outcome.
- •
Empirical Validation: In Sec. 6, 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., () 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 cognitive resources (Camerer,, ) including recency bias (Costabile and Klein,, ).
Motivated by this, we instead focus on a broad class of Markovian dynamics.
Secondly, the mediator’s objective in Zhang et al., () is to steer agents such that the average policy converges to the target NE while maintaining a sublinear accumulative budget, motivated by their infinite-horizon setup.
In 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., () require the mediator to be able to “give advice” to the players to facilitate coordination, while we do not allow the mediator to do this.
Because of these differences, the methods and results obtained by Zhang et al., () and us *are not directly comparable*, yet complement one another depending on application considered.

Perhaps the closest to ours is a concurrent work by Canyakmaz et al., (), which contributes empirical investigation on the use of control methods to direct game dynamics towards desired outcomes, in particular allowing for model uncertainty.
Although not formally specified in Canyakmaz et al., (), they consider a similar finite-horizon non-episodic setup as ours.
However, they only consider *history-independent* steering strategy, which can result in sub-optimal performance in this finite-horizon setup, because one-step observations may not provide sufficient information to tackle model uncertainty.
As our main contribution compared with their work, we point out that, one should, in principle, employ *history-dependent* steering strategies, since history can serve as sufficient information set for decision making under uncertainty.
This leads to significant differences in the design principles of our algorithms compared with Canyakmaz et al., ().
Concretely, we propose a learning objective for history-dependent strategies in Obj. (1), and two algorithms for low uncertainty (small $\mathcal{F}$) and high uncertainty (large $\mathcal{F}$) settings, respectively.
In the former case, we contribute a belief-state based algorithm that can exactly solve Obj. (1), offering a stronger solution than Canyakmaz et al., () due to the theoretical guarantee in Prop. 3.3.
For the latter, although both our FETE and SIAR-MPC (Canyakmaz et al.,, ) share a two-phase (exploration + exploitation) structure, ours represents a more general framework with a more advanced exploration strategy (see more explanation in Sec. 5.2).
Besides, we 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 we will focus on.
We summarize all the frequently used notations in this paper in Appx. A.

Finite Horizon Markov Game A finite-horizon $N$-player Markov Game is defined by a tuple $G:=\{\mathcal{N},s_{1},H,\mathcal{S},\mathcal{A}:=\{\mathcal{A}^{n}\}_{n=1}^{N
},{\mathbb{P}},{\bm{r}}:=\{r^{n}\}_{n=1}^{N}\}$, where $\mathcal{N}:=\{1,2,...,N\}$ is the indices of agents, $s_{1}$ is the fixed initial state, $H$ is the horizon length, $\mathcal{S}$ is the finite shared state space, $\mathcal{A}^{n}$ is the finite action space for agent $n$, and $\mathcal{A}$ denotes the joint action space.
Besides, ${\mathbb{P}}:=\{{\mathbb{P}}_{h}\}_{h\in[H]}$ with ${\mathbb{P}}_{h}:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$ denotes the transition function of the shared state, and $r^{n}:=\{r_{h}^{n}\}_{h\in[H]}$ with $r_{h}^{n}:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ denotes the reward function for agent $n$.
For each agent $n$, we consider the non-stationary Markovian policies $\Pi^{n}:=\{\pi^{n}=\{\pi_{1}^{n},...,\pi_{H}^{n}\}|\forall h\in[H],~{}\pi_{h}^
{n}:\mathcal{S}\rightarrow\Delta(\mathcal{A}^{n})\}$.
We denote $\Pi:=\Pi^{1}\times...\times\Pi^{N}$ to be the joint policy space of all agents.
Given a policy ${\bm{\pi}}:=\{\pi^{1},...,\pi^{N}\}\in\Pi$, a trajectory is generated by:
$\forall h\in[H],~{}\forall n\in[N],\quad a^{n}_{h}\sim\pi^{n}(\cdot|s_{h}),~{}
r^{n}_{h}\leftarrow r^{n}_{h}(s_{h},{\bm{a}}_{h}),~{}s_{h+1}\sim{\mathbb{P}}_{
h}(\cdot|s_{h},{\bm{a}}_{h}),$
where ${\bm{a}}_{h}:=\{a_{h}^{n}\}_{n\in[N]}$ denotes the collection of all actions.
Given a policy ${\bm{\pi}}$, we define the value functions by:
$Q^{n,{\bm{\pi}}}_{h|{\bm{r}}}(\cdot,\cdot):=\mathbb{E}_{{\bm{\pi}}}[\sum_{{h^{
\prime}}=h}^{H}r^{n}_{h^{\prime}}(s_{h^{\prime}},{\bm{a}}_{h^{\prime}})|s_{h}=
\cdot,{\bm{a}}_{h}=\cdot],~{}V^{n,{\bm{\pi}}}_{h|{\bm{r}}}(\cdot):=\mathbb{E}_
{{\bm{\pi}}}[\sum_{{h^{\prime}}=h}^{H}r^{n}_{h^{\prime}}(s_{h^{\prime}},{\bm{a
}}_{h^{\prime}})|s_{h}=\cdot],$
where we use $|r$ to specify the reward function associated with the value functions.
In the rest of the paper, we denote $A^{n,{\bm{\pi}}}_{|{\bm{r}}}=Q^{n,{\bm{\pi}}}_{|{\bm{r}}}-V^{n,{\bm{\pi}}}_{|{
\bm{r}}}$ to be the advantage value function, and denote $J^{n}_{|{\bm{r}}}({\bm{\pi}}):=V^{n,{\bm{\pi}}}_{1|{\bm{r}}}(s_{1})$ to be the total return of agent $n$ w.r.t. policy ${\bm{\pi}}$.

## 3 The Problem Formulation of the Steering Markovian Agents

We first introduce our definition of Markovian agents. Informally, the policy updates of Markovian agents are independent of the interaction history conditioning on their current policy and observed rewards.
This encompass a broader class of popular policy-based methods as concrete examples (Giannou et al.,, ; Ding et al.,, ; Xiao,, ; Daskalakis et al.,, ).

###### 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 ${\bm{\pi}}_{t}$ and the reward function ${\bm{r}}$:

$$ $\displaystyle\forall t\in[T],\quad{\bm{\pi}}_{t+1}\sim f(\cdot|{\bm{\pi}}_{t}, {\bm{r}}).$ $$

Here we only highlight the dependence on ${\bm{\pi}}_{t}$ and ${\bm{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 or correlated with each other, deterministic or stochastic.
We assume $T$ is known to us.

In the steering problem, the mediator has the ability to change the reward function ${\bm{r}}$ via the steering reward ${\bm{u}}$, so that the agents’ dynamics are modified to:

$$ $\displaystyle\forall t\in[T],\quad$ $\displaystyle{\color[rgb]{.75,0,.25}{\bm{u}}_{t}}\sim\psi_{t}(\cdot|{\bm{\pi}} _{1},{\bm{u}}_{1},...,{\bm{\pi}}_{t-1},{\bm{u}}_{t-1},{\bm{\pi}}_{t}),\quad{ \bm{\pi}}_{t+1}\sim f(\cdot|{\bm{\pi}}_{t},{\bm{r}}+{\color[rgb]{.75,0,.25}{ \bm{u}}_{t}}),$ $$

Here $\psi:=\{\psi_{t}\}_{t\in[T]}$ denotes the mediator’s “steering strategy” to generate $u_{t}$.
We consider history-dependent strategies to handle the model uncertainty, which we will explain later.
Besides, ${\bm{u}}_{t}:=\{u_{t,h}^{n}\}_{h\in[H],n\in[N]}$, where $u^{n}_{t,h}:\mathcal{S}\times\mathcal{A}\rightarrow[0,U_{\max}]$ is the steering reward for agent $n$ at game horizon $h$ and steering step $t$. $U_{\max}<+\infty$ denotes the upper bound for the steering reward. For practical concerns, we follow the standard constraints that the steering rewards are non-negative.

The mediator has a terminal reward function $\eta^{\text{goal}}$ and a cost function $\eta^{\text{cost}}$.
First, $\eta^{\text{goal}}:\Pi\rightarrow[0,\eta_{\max}]$ assesses whether the final policy ${\bm{\pi}}_{T+1}$ aligns with desired behaviors—this encapsulates our primary goal of a low steering gap. Note that we consider the general setting and do not restrict the maximizer of $\eta^{\text{goal}}$ to be a Nash Equilibrium.
For instance, to steer the agents to a desired policy ${\bm{\pi}}^{*}$, we could choose $\eta^{\text{goal}}({\bm{\pi}}):=-\|{\bm{\pi}}-{\bm{\pi}}^{*}\|_{2}$. Alternatively, in scenarios focusing on maximizing utility, $\eta^{\text{goal}}({\bm{\pi}})$ could be defined as the total utility $\sum_{n\in[N]}J^{n}_{|{\bm{r}}}({\bm{\pi}})$.
For $\eta^{\text{cost}}:\Pi\rightarrow{\mathbb{R}}_{\geq 0}$, it is used to quantify the steering cost incurred while steering.
In this paper, we fix $\eta^{\text{cost}}({\bm{\pi}},{\bm{u}}):=\sum_{n\in[N]}J^{n}_{|{\bm{u}}}(\pi^{
n})$ to be the total return related to ${\bm{\pi}}$ and the steering reward ${\bm{u}}$.
Note that we always have $0\leq\eta^{\text{cost}}({\bm{\pi}},{\bm{u}})\leq U_{\max}NH$.

Steering Dynamics as a Markov Decision Process (MDP) Given a game $G$, the agents’ dynamics $f$ and $(\eta^{\text{cost}},\eta^{\text{goal}})$, the *steering dynamics* can be modeled by a finite-horizon MDP. $M:=\{{\bm{\pi}}_{1},T,\Pi,\mathcal{U},f,(\eta^{\text{cost}},\eta^{\text{goal}})\}$ with initial state ${\bm{\pi}}_{1}$, horizon length $T$, state space $\Pi$, action space $\mathcal{U}:=[0,U_{\max}]^{HN|\mathcal{S}||\mathcal{A}|}$, stationary transition $f$, running reward $\eta^{\text{cost}}$ and terminal reward $\eta^{\text{goal}}$.
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 $\eta^{\text{goal}}$ and $\eta^{\text{cost}}$.
We consider the model-based setting where the mediator only has access to a finite model class $\mathcal{F}$ ($|\mathcal{F}|<+\infty$) satisfying the following assumption:

###### Assumption A (Realizability) .

$f^{*}\in\mathcal{F}$.

A Finite-Hoziron Non-Episodic Setup and Motivation As motivated previously, we formulate 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 Sec. 1.1.

###### Definition 3.2 (Finite Horizon Non-Episodic Steering Setting) .

The mediator can only interact with *the real agents* for *one episode* $\{{\bm{\pi}}_{1},{\bm{u}}_{1},...,{\bm{\pi}}_{T},{\bm{u}}_{T},{\bm{\pi}}_{T+1}\}$, where ${\bm{\pi}}_{t+1}\sim f^{*}(\cdot|{\bm{\pi}}_{t},{\bm{u}}_{t})~{}\forall t\in[T]$.
Nonetheless, the mediator can get access to the simulators for all models in $\mathcal{F}$, and it can sample *arbitrary* trajectories and do episodic learning with those simulators to decide the best steering actions ${\bm{u}}_{1},{\bm{u}}_{2},...,{\bm{u}}_{T}$ 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 $\Psi$, to optimize the average performance over all $f\in\mathcal{F}$.

$$ $\displaystyle\psi^{*}\leftarrow$ $\displaystyle\arg\max_{\psi\in\Psi}\frac{1}{|\mathcal{F}|}\sum_{f\in\mathcal{F }}\mathbb{E}_{\psi,f}\Big{[}\beta\cdot\eta^{\text{goal}}({\bm{\pi}}_{T+1})- \sum_{t=1}^{T}\eta^{\text{cost}}({\bm{\pi}}_{t},{\bm{u}}_{t})\Big{]},$ (1) $$

Here we use $\mathbb{E}_{\psi,f}[\cdot]:=\mathbb{E}[\cdot|\forall t\in[T],{\bm{u}}_{t}\sim
\psi_{t}(\cdot|\{{\bm{\pi}}_{t^{\prime}},{\bm{u}}_{t^{\prime}}\}_{t^{\prime}=1
}^{t-1},{\bm{\pi}}_{t}),{\bm{\pi}}_{t+1}\sim f(\cdot|{\bm{\pi}}_{t},{\bm{r}}+{
\bm{u}}_{t})]$ to denote the expectation over trajectories generated by $\psi$ and $f\in\mathcal{F}$; $\beta>0$ is a 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.

We want to clarify that in our steering framework, we will first solve Obj. (1), and then deploy $\psi^{*}$ to steer real agents.
The learning and optimization of $\psi^{*}$ in Obj. (1) only utilizes simulators of $\mathcal{F}$.
Besides, after deploying $\psi^{*}$ to real agents, we will not update $\psi^{*}$ with the data generated during the interaction with real agents.
This is seemingly different from common online learning algorithms which conduct the learning and interaction repeatedly(Dann and Brunskill,, ).
But we want to highlight that, given the fact that $\psi^{*}$ is history-dependent, it is already encoded in $\psi^{*}$ 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. (1), we are trying to optimize an “online algorithm” $\psi^{*}$ which can “smartly” decide the next steering reward to deploy given the past interaction history.
As we will justify in the following, our Obj. (1) can indeed successfully handle the model uncertainty.

Justification for Objective (1) We use $C_{\psi,T}(f):=\mathbb{E}_{\psi,f}[\sum_{t=1}^{T}\eta^{\text{cost}}({\bm{\pi}}
_{t},{\bm{u}}_{t})]$ and $\Delta_{\psi,T}(f):=\mathbb{E}_{\psi,f}[\max_{\bm{\pi}}\eta^{\text{goal}}({\bm
{\pi}})-\eta^{\text{goal}}({\bm{\pi}}_{T+1})]$ as short notes of the steering cost and the steering gap (of the terminal policy ${\bm{\pi}}_{T+1}$), respectively.
Besides, we denote $\Psi^{\varepsilon}:=\{\psi\in\Psi|\max_{f\in\mathcal{F}}\Delta_{\psi,T}(
\mathcal{F})\leq\varepsilon\}$(^3^33In fact, besides $\varepsilon$, $\Psi^{\varepsilon}$ also depends on other parameters like $T$, $U_{\max}$, $\mathcal{F}$ and the initial policy ${\bm{\pi}}_{1}$. For simplicity, we only highlight those dependence if necessary.) to be the collection of all steering strategies with $\varepsilon$-steering gap.
Based on these notations, we introduce two desiderata, and show how an optimal solution $\psi^{*}$ of Obj. (1) can achieve them.

###### Desideratum 1 ( $\varepsilon$ -Steering Gap) .

We say $\psi$ has $\varepsilon$-steering gap, if $\max_{f\in\mathcal{F}}\Delta_{\psi,T}(f)\leq\varepsilon$.

###### Desideratum 2 (Pareto Optimality) .

We say $\psi$ is Pareto Optimal if there does not exist another $\psi^{\prime}\in\Psi$, such that (1) $\forall f\in\mathcal{F}$, $C_{\psi^{\prime},T}(f)\leq C_{\psi,T}(f)$ and $\Delta_{\psi^{\prime},T}(f)\leq\Delta_{\psi,T}(f)$; (2) $\exists f^{\prime}\in\mathcal{F}$, s.t. either $C_{\psi^{\prime},T}(f^{\prime})<C_{\psi,T}(f^{\prime})$ or $\Delta_{\psi^{\prime},T}(f^{\prime})<\Delta_{\psi,T}(f^{\prime})$.

###### Proposition 3.3 .

[Justification for Obj. (1)]
By solving Obj. (1):
(1) $\psi^{*}$ is Pareto Optimal;
(2) Given any $\varepsilon,\varepsilon^{\prime}>0$, if
$\Psi^{\varepsilon/|\mathcal{F}|}\neq\emptyset$ and $\beta\geq\frac{U_{\max}NHT|\mathcal{F}|}{\varepsilon^{\prime}}$, we have $\psi^{*}\in\Psi^{\varepsilon+\varepsilon^{\prime}}$;

Next, we give some interpretation.
As our primary desideratum, we expect the agents converge to some desired policy that maximizes the goal function $\eta^{\text{goal}}$ 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 $\varepsilon>0$, as long as $\varepsilon/|\mathcal{F}|$-steering gap is achievable, by choosing $\beta$ large enough, we can approximately guarantee $\psi^{*}$ has $\varepsilon$-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 $\psi^{*}$, there does not exist another $\psi^{\prime}$, which can improve either the steering cost or gap for some $f^{\prime}\in\mathcal{F}$ without deteriorating any others.

Given the above discussion, one natural question is that: *when is $\Psi^{\varepsilon}$ non-empty*, or equivalently, *when does a strategy $\psi$ with $\varepsilon$-steering gap exist*?
In Sec. 4, we provide sufficient conditions and concrete examples to address this question in theory.
Notably, we suggest conditions where $\Psi^{\varepsilon}$ is non-empty for any $\varepsilon>0$, so that the condition $\Psi^{\varepsilon/|\mathcal{F}|}\neq\emptyset$ in Prop. 3.3 is realizable, even for large $|\mathcal{F}|$.
After that, in Sec. 5, we introduce algorithms to solve our Obj. (1).

###### Definition 3.1 (Markovian Agents) .

###### Assumption A (Realizability) .

###### Definition 3.2 (Finite Horizon Non-Episodic Steering Setting) .

###### Desideratum 1 ( ε 𝜀 \varepsilon italic_ε -Steering Gap) .

###### Desideratum 2 (Pareto Optimality) .

###### Proposition 3.3 .

## 4 Existence of Steering Strategy with ε 𝜀 \varepsilon italic_ε -Steering Gap

In this section, we identify sufficient conditions such that $\Psi^{\varepsilon}$ is non-empty.
In Sec. 4.1, we start with the special case when $f^{*}$ is known, i.e. $\mathcal{F}=\{f^{*}\}$.
The results will serve as basis when we study the general unknown model setting in Sec. 4.2.

### 4.1 Existence when f ∗ superscript 𝑓 f^{*} italic_f start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT 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,, ; Agarwal et al.,, ) (a.k.a. the replicator dynamics (Schuster and Sigmund,, )) with direct policy parameterization.
NPG is a special case of the Policy Mirror Descent (PMD)
(Xiao,, ).
For the readability, we stick to NPG in the main text, and in Appx. D.1, we formalize PMD and extend the results to the general PMD, which subsumes other learning dynamics, like the online gradient ascent (Zinkevich,, ).

###### Definition 4.1 (Natural Policy Gradient) .

For any $n\in[N],t\in[T],h\in[H],s_{h}\in\mathcal{S}$, the policy is updated by:
$\pi_{t+1,h}^{n}(\cdot|s_{h})~{}\propto~{}\pi_{t,h}^{n}(\cdot|s_{h})\exp(\alpha
{\widehat{A}}^{n,{\bm{\pi}}_{t}}_{h|r^{n}+u^{n}_{t}}(s_{h},\cdot)).$
Here ${\widehat{A}}^{n,{\bm{\pi}}_{t}}_{h|r^{n}+u^{n}_{t}}$ is some random estimation for the advantage value $A^{n,{\bm{\pi}}_{t}}_{h|r^{n}+u^{n}_{t}}$ with $\mathbb{E}_{\pi^{n}}[{\widehat{A}}^{n,{\bm{\pi}}_{t}}_{h|r^{n}+u^{n}_{t}}(s_{h
},\cdot)]=0$.

We use ${\widehat{A}}^{\bm{\pi}}_{|{\bm{r}}+{\bm{u}}}$ (and $A^{\bm{\pi}}_{|{\bm{r}}+{\bm{u}}}$) to denote the concatenation of the values of all agents, horizon, states and actions.
We only assume ${\widehat{A}}^{{\bm{\pi}}_{t}}_{|{\bm{r}}+{\bm{u}}}$ is controllable and has positive correlation with $A^{{\bm{\pi}}_{t}}_{|{\bm{r}}+{\bm{u}}}$ but could be biased, which we call the “general incentive driven” agents.

###### Assumption B (General Incentive Driven Agents) .

$$ $\forall t\in[T],\quad\langle\mathbb{E}[{\widehat{A}}^{{\bm{\pi}}_{t}}_{|{\bm{r }}+{\bm{u}}_{t}}],A^{{\bm{\pi}}_{t}}_{|{\bm{r}}+{\bm{u}}_{t}}\rangle\geq \lambda_{\min}\|A^{{\bm{\pi}}_{t}}_{|{\bm{r}}+{\bm{u}}_{t}}\|_{2}^{2},~{}\|{ \widehat{A}}^{{\bm{\pi}}_{t}}_{|{\bm{r}}+{\bm{u}}_{t}}\|^{2}_{2}\leq\lambda_{ \max}^{2}\|A^{{\bm{\pi}}_{t}}_{|{\bm{r}}+{\bm{u}}_{t}}\|_{2}^{2},$ $$

For NPG, note that the policy is always bounded away from 0. We will use $\Pi^{+}:=\{{\bm{\pi}}|\forall n,h,a_{h},s_{h}:\pi^{n}_{h}(a_{h}|s_{h})>0\}$ to denote such feasible policy set.
We state our main result below.

###### Theorem 4.2 (Informal) .

Suppose $\eta^{\text{goal}}$ is Lipschitz in ${\bm{\pi}}$, given any initial ${\bm{\pi}}_{1}\in\Pi^{+}$, for any $\varepsilon>0$, if the agents follow Def. 4.1 under Assump. B, if $T$ and $U_{\max}$ are large enough, we have $\Psi^{\varepsilon}\neq\emptyset$.

Our result is strong in indicating the existence of a steering path for any feasible initialization.
The proof is based on construction.
The basic idea is to design the ${\bm{u}}_{t}$ so that $A^{{\bm{\pi}}_{t}}_{|{\bm{r}}+{\bm{u}}_{t}}\propto\log\frac{{\bm{\pi}}^{*}}{{
\bm{\pi}}_{t}}$, for some target policy ${\bm{\pi}}^{*}\in\Pi^{+}$ (approximately) maximizing $\eta^{\text{goal}}$, then we can guarantee the convergence of ${\bm{\pi}}_{t}$ towards ${\bm{\pi}}^{*}$ under Assump. B.
The main challenge here would be the design of $u_{t}$.
We defer the details and the formal statements to Appx. D.

###### Definition 4.1 (Natural Policy Gradient) .

###### Assumption B (General Incentive Driven Agents) .

###### Theorem 4.2 (Informal) .

### 4.2 Existence when f ∗ superscript 𝑓 f^{*} italic_f start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT is Unknown: the Identifiable Model Class

Intuitively, when $f^{*}$ is unknown, if we can first use a few steering steps $\widetilde{T}<T$ to explore and identify $f^{*}$, and then steer the agents from ${\bm{\pi}}_{\widetilde{T}}$ to the desired policy within $T-\widetilde{T}$ steps given the identified $f^{*}$, we can expect $\Psi^{\varepsilon}\neq\emptyset$.
Motivated by this insight, we introduce the following notion.

###### Definition 4.3 ( $(\delta,T_{\mathcal{F}}^{\delta})$ -Identifiable) .

Given $\delta\in(0,1)$, we say $\mathcal{F}$ is $(\delta,T_{\mathcal{F}}^{\delta})$-identifiable, if $\max_{\psi}\min_{f\in\mathcal{F}}\mathbb{E}_{\psi,f}[\mathbb{I}[f=f_{\text{MLE
}}]]\geq 1-\delta$, where $\mathbb{I}[\mathcal{E}]=1$ if $\mathcal{E}$ is true and otherwise 0; $f_{\text{MLE}}:=\operatorname*{arg\,max}_{f\in\mathcal{F}}\sum_{t=1}^{T_{
\mathcal{F}}^{\delta}}\log f({\bm{\pi}}_{t+1}|{\bm{\pi}}_{t},{\bm{u}}_{t})$.

Intuitively, $\mathcal{F}$ is $(\delta,T_{\mathcal{F}}^{\delta})$-identifiable, if $\exists\psi$, s.t. after $T_{\mathcal{F}}^{\delta}$ steering steps, the hidden model $f$ can be identified by the Maximal Likelihood Estimation (MLE) with high probability.
Next, we provide an example of $(\delta,T_{\mathcal{F}}^{\delta})$-identifiable function class with $T_{\mathcal{F}}^{\delta}$ upper bounded for any $\delta\in(0,1)$.

###### Example 4.4 .

[One-Step Difference]
If $\forall{\bm{\pi}}\in\Pi$, there exists a steering reward ${\bm{u}}_{\bm{\pi}}\in\mathcal{U}$, s.t.
$\min_{f,f^{\prime}\in\mathcal{F}}{\mathbb{H}}^{2}(f(\cdot|{\bm{\pi}},{\bm{r}}+
{\bm{u}}_{\bm{\pi}}),f^{\prime}(\cdot|{\bm{\pi}},{\bm{r}}+{\bm{u}}_{\bm{\pi}})
)\geq\zeta,$
for some universal $\zeta>0$, where ${\mathbb{H}}$ is the Hellinger distance, then for any $\delta\in(0,1)$, $\mathcal{F}$ is $(\delta,T_{\mathcal{F}}^{\delta})$-identifiable with $T_{\mathcal{F}}^{\delta}=O(\zeta^{-1}\log({|\mathcal{F}|}{/\delta}))$.

Based on Def. 4.3, we provide a sufficient condition when $\Psi^{\varepsilon}$ is non-empty.

###### Theorem 4.5 .

[A Sufficient Condition for Existence]
Given any $\varepsilon>0$, $\Psi^{\varepsilon}_{T}(\mathcal{F};{\bm{\pi}}_{1})\neq\emptyset$(^4^44Here we highlight the dependence on initial policy, model, and time for clarity (see Footnote 3)), if $\exists~{}\widetilde{T}<T$, s.t., (1) $\mathcal{F}$ is $(\frac{\varepsilon}{2\eta_{\max}},\widetilde{T})$-identifiable, (2) $\Psi^{\varepsilon/2}_{T-\widetilde{T}}(\mathcal{F};{\bm{\pi}}_{\widetilde{T}})\neq\emptyset$ for any possible ${\bm{\pi}}_{\widetilde{T}}$ generated at step $\widetilde{T}$ during the steering.

We conclude this section by noting that, by Thm. 4.2, 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. E.

###### Definition 4.3 ( ( δ , T ℱ δ ) 𝛿 superscript subscript 𝑇 ℱ 𝛿 (\delta,T_{\mathcal{F}}^{\delta}) ( italic_δ , italic_T start_POSTSUBSCRIPT caligraphic_F end_POSTSUBSCRIPT start_POSTSUPERSCRIPT italic_δ end_POSTSUPERSCRIPT ) -Identifiable) .

###### Example 4.4 .

###### Theorem 4.5 .

## 5 Learning (Approximately) Optimal Steering Strategy

In this section, we investigate how to solve Obj. (1).
Comparing with the episodic RL setting, the main challenge is to learn a history-dependent policy.
Since the history space grows exponentially in $T$, directly solving Obj. (1) can be computationally intractable for large $T$.
Therefore, the main focus of this section is to design tractable algorithms to overcome this challenge.

As a special case, when the model is known, i.e. $\mathcal{F}=\{f^{*}\}$, by the Markovian property, Obj. (1) reduces to a normal RL objective, and a state-dependent steering strategy $\psi:\Pi\rightarrow\mathcal{U}$ 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 $|\mathcal{F}|>1$.
In Sec. 5.1, we investigate the solutions when $|\mathcal{F}|$ is small, and in Sec. 5.2, we study the more challenging case when $|\mathcal{F}|$ is large.

### 5.1 Small Model Class: Dynamic Programming with Model Belief State

A Partially Observable MDP Perspective In fact, we can interpret Obj. (1) as learning the optimal policy in a POMDP, in which the hidden state is $({\bm{\pi}}_{t},f)$, i.e. a tuple containing the policy and the hidden model $f$ uniformly sampled from $\mathcal{F}$, and the mediator can only partially observe the policy ${\bm{\pi}}_{t}$.
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,, ).
In our case, for each step $t\in[T]$, the belief state is $({\bm{\pi}}_{t},b_{t})$, where $b_{t}:=[\Pr(f|\{{\bm{\pi}}_{t^{\prime}},{\bm{u}}_{t^{\prime}}\}_{t^{\prime}=1}
^{t},{\bm{\pi}}_{t})]_{f\in\mathcal{F}}$ is the “model belief state” defined to be the posterior distribution of models given the history of observations and actions.
When $|\mathcal{F}|$ is small, the model belief state $b_{t}\in\mathcal{R}^{|\mathcal{F}|}$ is low dimensional and computable.
Learning $\psi^{*}$ is tractable by running any RL algorithm on the lifted MDP.
In Proc. 1, we show how to steer in this setting.
We defer the detailed algorithm of learning such belief-state dependent strategy to Alg. 4 in Appx. B.5.

Figure: Procedure 1 The Steering Procedure when $|\mathcal{F}|$ is Small

### 5.2 Large Model Class: A First-Explore-Then-Exploit Framework

When $|\mathcal{F}|$ is large, the method in Sec. 5.1 is inefficient since the belief state $b_{t}$ is high-dimensional.
In fact, the above POMDP interpretation implies the intractability of Obj. (1) for large $|\mathcal{F}|$: the number of hidden states of the POMDP scales with $|\mathcal{F}|$.
Therefore, instead of exactly solving Obj. (1), we turn to the First-Explore-Then-Exploit (FETE) framework as stated in Procedure 2.

The first $\widetilde{T}<T$ steps are the exploration phase, where we learn and deploy an exploration policy $\psi^{\text{Explore}}$
maximizing the probability of identifying the hidden model with the MLE estimator.
The remaining $T-\widetilde{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-\widetilde{T}$ steps by solving Obj. (1) with $\mathcal{F}=\{f_{\text{MLE}}\}$, time $T-\widetilde{T}$ and the initial policy ${\bm{\pi}}_{\widetilde{T}+1}$, as if $f_{\text{MLE}}$ is the true model.

Justification for FETE We cannot guarantee that Desiderata 1& 2 are achievable, because we do not exactly solve Obj. 1.
However, if $\mathcal{F}$ is $({\delta}/|\mathcal{F}|,T_{\mathcal{F}}^{\delta/|\mathcal{F}|})$-identifiable (Def. 4.3) and we choose $\widetilde{T}\geq T_{\mathcal{F}}^{\delta/|\mathcal{F}|}$, we can verify $\Pr(f_{\text{MLE}}=f^{*})\geq 1-\delta$ in Proc. 2.
Therefore, we can still expect the exploitation policy $\psi^{\text{Exploit}}$ steer the agents to approximately maximize $\eta^{\text{goal}}({\bm{\pi}}_{T+1})$ with reasonable steering cost for the rest $T-\widetilde{T}$ steps.

Figure: Procedure 2 The Steering Procedure when $|\mathcal{F}|$ is Large (The FETE Framework)

We conclude this section by highlighting the computational tractability of FETE.
Note that when computing $\psi^{\text{Exploit}}$, we treat $f_{\text{MLE}}$ as the true model, so an history-independent $\psi^{\text{Exploit}}$ is enough.
Therefore, the only part where we need to learn a history-dependent strategy is in the exploration stage, and the maximal history length is at most $\widetilde{T}$, which can be much smaller than $T$. Moreover, in some cases, it is already enough to just learn a history-independent $\psi^{\text{Explore}}$ to do the exploration (for example, the model class in Example 4.4).

Comparison with Canyakmaz et al., () Although both SIAR-MPC in Canyakmaz et al., () and our FETE (Procedure 2) adopt a first-explore-then-exploit structure, FETE is more general and more effective. Both algorithms have three main components: exploration strategy, model estimation strategy and exploitation strategy, and we inspect our advantages from these three aspects.
(i) 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.
(ii) Model estimation strategy: SIAR-MPC estimates the hidden model by solving a regression problem with constraints (Eq. (8) in Canyakmaz et al., ()), while we solve a MLE objective. In fact, our MLE objective is more general and can recover the regression problem in SIAR-MPC, if we consider a model class $\mathcal{F}$ that includes Gaussian noise perturbed dynamics with the side-information constraints introduced in Canyakmaz et al., ().
(iii) Exploitation strategy: As a general framework, our FETE does not restrict how to compute the exploitation strategy $\psi^{Exploit}$. As we suggest in paper, any RL or control method can be used, including the MPC approach in Canyakmaz et al., ().

## 6 Experiments

In this section, we discuss our experimental results.
For more details of all experiments in this section (e.g. experiment setup and training details), we defer to Appx. G.
The steering horizon is set to be $T=500$, and all the error bar shows 95% confidence level.
We denote $[x]^{+}:=\max\{0,x\}$.

### 6.1 Learning Steering Strategies with Knowledge of f ∗ superscript 𝑓 f^{*} italic_f start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT

Normal-Form Stag Hunt Game In Fig. 1-(b), we compare the agents’ dynamics with/without steering, where the agents learn to play the Stag Hunt Game in Fig. 1-(a).
We report the experiment setup here.
Both agents follow the exact NPG (Def. 4.1 with $\widehat{A}^{\bm{\pi}}=A^{\bm{\pi}}$) with fixed learning rate $\alpha=0.01$.
For the steering setup, we choose the total utility as $\eta^{\text{goal}}$, and use PPO to train the steering strategy (one can choose other RL or control algorithms besides PPO).
We also conduct experiments in a representative zero-sum game ‘Matching Pennies’, which we defer the details to Appx. G.2.

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 $\mathcal{X}=\Pi\subset{\mathbb{R}}^{4}$ has low dimension.
In real-world scenarios, the policy space $\Pi$ can be extremely rich and high-dimensional if the agents consider neural networks as policies. In addition, the mediator may not get access to the agents’ exact policy ${\bm{\pi}}$ because of privacy issues.

Figure: (a)
Refer to caption: extracted/5907892/Pictures/GridWorldStagHunt.png

This motivates us to investigate the possibility of steering agents with observations on agents’ behavior only (e.g. trajectories of agents in a game $G$), instead of the full observation of ${\bm{\pi}}$.
In Appx. F, we justify this setup and formalize it as a partially observable extension of our current framework.
We consider the evaluation in a grid-world version of the Stag Hunt Game as shown in Fig. 2-(a).
In this setting, the state space in game $G$ 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 a steering strategy, which only takes the agents’ recent trajectories as input to infer the steering reward.
As shown in Fig. 2-(b), without direct usage of the agents’ policy, we can still train a steering strategy towards desired solution.

### 6.2 Learning Steering Strategies without Knowledge of f ∗ superscript 𝑓 f^{*} italic_f start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT

Small Model Set $|\mathcal{F}|$: Belief State Based Steering Strategy In this part, we evaluate Proc. 1 designed for small $\mathcal{F}$.
We consider the same normal-form Stag Hunt game and setup as Sec. 6.1, while the agents update by the NPG with a random learning rate $\alpha=[\xi]^{+}$, where $\xi\sim\mathcal{N}(\mu,0.3^{2})$.
Here the mean value $\mu$ is unknown to the mediator, and we consider a model class $\mathcal{F}:=\{f_{0.7},f_{1.0}\}$ including two possible values of $\mu\in\{0.7,1.0\}$.
We report our experimental results in Table 1.

**Table 1: Evaluation for Proc. 1 (Averaged over 25 different initial ${\bm{\pi}}_{1}$, see Appx. G.1).**
|  | $p(\Delta_{\psi,T}\leq\varepsilon)$ | $C_{\psi,T}$ |
| --- | --- | --- |
| $\psi^{*}_{0.7}$ | 0.99 $\pm$ 0.01 | 10.6 $\pm$ 0.3 |
| $\psi^{*}_{1.0}$ | 0.13 $\pm$ 0.02 | 7.6 $\pm$ 0.2 |
| $\psi^{*}_{\text{Belief}}$ | 0.87 $\pm$ 0.05 | 10.5 $\pm$ 0.4 |

Firstly, we demonstrate the suboptimal behavior if the mediator ignores the model uncertainty and just randomly deploys the optimal strategy of $f_{0.7}$ or $f_{1.0}$.
To do this, we train the (history-independent) optimal steering strategy by Alg. 3, as if we know $f^{*}=f_{0.7}$ (or $f^{*}=f_{1.0}$), which we denote as $\psi^{*}_{0.7}$ (or $\psi^{*}_{1.0}$).
To meet with our Desideratum 1, we first set the accuracy level $\varepsilon=0.01$, and search the minimal $\beta$ so that the learned steering strategy can achieve $\varepsilon$-steering gap (see Appx. G.3.1).
Because of the difference in $\mu$, we have $\beta=70$ and $\beta=20$ in training $\psi^{*}_{0.7}$ and $\psi^{*}_{1.0}$, respectively, and empirically, we observe that $\psi^{*}_{0.7}$ requires much larger steering reward than $\psi^{*}_{1.0}$.
As we marked in red in Table 1-(a) and (b), because of the difference in the steering signal, $\psi^{*}_{0.7}$ consumes much higher steering cost to achieve the same accuracy level in $f_{1.0}$, and $\psi^{*}_{1.0}$ may fail to steer agents with $f_{0.7}$ to the desired accuracy.
Next, we train another strategy $\psi^{*}_{\text{Belief}}$ via Alg. 4, which predicts the steering reward based on both the agents’ policy ${\bm{\pi}}$ and the belief state of the model.
As we can see, $\psi^{*}_{\text{Belief}}$ can almost always achieve the desired $\varepsilon$-steering gap with reasonable steering cost.

Large Model Set $|\mathcal{F}|$: The FETE Framework In this part, we evaluate the FETE framework (Proc. 2 in Sec. 5.2).
We consider an 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. $\eta^{\text{goal}}({\bm{\pi}}):=\prod_{n=1}^{N}\pi^{n}(\texttt{A})$.
The agents do not have intrinsic rewards (${\bm{r}}=0$), but the mediator’s can steer them to maximize its own utility by providing additional steering rewards.

Figure: Figure 3: Evaluation for Proc. 2. Left: Accuracy of MLE estimator ($\lambda^{n}_{\text{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.,, ) to our setting) in terms of steering gap.
Refer to caption: x4.png

We consider “avaricious agents” with varying degrees of greediness, who tend to decrease the learning rates if the payments by mediator are high.
Consequently, they require more steering steps to converge to the desired policies, potentially earning more incentive payments from the mediators.
More concretely, the learning rate of agent $n$ is $\alpha_{n}:=[\xi_{n}]^{+}$ with $\xi_{n}\sim\mathcal{N}(1.5-\beta^{n}\cdot[V_{|{\bm{u}}}^{n,{\bm{\pi}}}-\lambda
^{n}]^{+},0.5^{2})$, where $\beta^{n}>0$ is a scaling factor and $\lambda^{n}>0$ is the threshold to exhibit avaricious behavior.
In our experiments, the model uncertainty comes from multiple possible realization of $\lambda^{n}\in\{0.25,0.75,+\infty\}$, which results in an extremely large model class $\mathcal{F}$ with $|\mathcal{F}|=3^{10}$. Here $\lambda^{n}=+\infty$ corresponds to normal agents whose learning rates are stable.
The mediator does not know the agents’ types $\{\lambda^{n}\}_{n\in[N]}$ in advance, and it can only observe one learning rate samples $\{\alpha_{n}\}_{n\in[N]}$ of agents per iteration $t\in[T]$ and estimate the true types from those samples.
We consider the fixed initial policy with $\forall n\in[N],~{}\pi^{n}_{1}(\texttt{A})=1-\pi^{n}_{1}(\texttt{B})=1/3$, and set the maximal steering reward $U_{\max}=1.0$.

To understand the exploration challenge, note that, during the exploration phase, if the steering signal ${\bm{u}}$ is not strong enough, i.e. $V^{n,{\bm{\pi}}}_{|{\bm{u}}}<\lambda^{n}$, 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. 3.
First, we compare the exploration efficiency. We can see the clear advantage of our strategic exploration in FETE (Procedure 2) compared with noise-based random exploration (Canyakmaz et al.,, ).
Next, we compare the steering gaps and costs of three methods: (i) FETE; (ii) FETE-RE;
(iii) Oracle – if the mediator knows $f^{*}$ in advance and solving Obj. (1) with $\mathcal{F}=\{f^{*}\}$.
Here FETE-RE can be regarded as adaption of SIAR-MPC (Canyakmaz et al.,, ) to our case by replacing strategic exploration in FETE with random exploration (see Appx. G.4 for more explanation).
We choose exploration horizon $\widetilde{T}=30$ suggested by the previous exploration experiment, and report results for three realizations of $f^{*}\in\{f_{1},f_{2},f_{3}\}$.
For $f_{1}$ and $f_{2}$, all the agents share $\lambda^{n}=0.75$ and $+\infty$, respectively.
$f_{3}$ is a mixed setup where $\lambda^{n}=0.75$ for $1\leq n\leq 5$ and $\lambda^{n}=+\infty$ for $5<n\leq 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., () in terms of steering gaps.

## 7 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 in terms of steering gap and cost than ours.
Secondly, when applying our strategies in real-world applications, constraints on the steering reward budget could be added.
Finally, the framework could be generalized to permit non-Markovian agents.

## Acknowledgement

The work is supported by ETH research grant and Swiss National Science Foundation (SNSF) Project Funding No. 200021-207343 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 codes for all the experiments in this paper and the instructions for running can be found in the supplementary materials.

## Appendix A Frequently Used Notations

| Notation | Description |
| --- | --- |
| $G$ | A finite-horizon general-sum Markov Game |
| $N$ | The number of agents |
| $\mathcal{S},\mathcal{A}$ | State space and action space of the game $G$ |
| $H$ | The horizon of the game $G$ |
| ${\mathbb{P}}$ | Transition function of the game $G$ |
| $r$ | Reward function of the game $G$ |
| ${\bm{\pi}}$ | The agents’ policy (collection of policies of all agents) |
| ${\bm{\pi}}_{1}$ | The initial policy |
| $M$ | A finite-horizon Markov Decision Process (the steering MDP) |
| $\mathcal{X},\mathcal{U}$ | State space and action space of $M$ |
| $T$ | The horizon of $M$ (i.e. the horizon of the steering dynamics) |
| ${\mathbb{T}}$ | (Stationary) Transition function of $M$ |
| $\eta^{\text{cost}}$ | The steering cost function of $M$ |
| $\psi$ | The history-dependent steering strategy by mediator |
| $u$ (or $u_{t}$ for a specific horizon $t$) | The steering reward function |
| $U_{\max}$ | The upper bound for steering reward |
| $f$ | Agents learning dynamics (${\mathbb{T}}=f$ in the steering MDP) |
| $\eta^{\text{goal}}$ | The goal function of $M$ |
| $\mathcal{F}$ | The model class of agents dynamics (with finite candidates) |
| $\beta$ | Regularization coefficient in Obj. (1) |
| $C_{\psi,T}(f)$ | The total expected steering cost $\mathbb{E}_{\psi,f}[\sum_{t=1}^{T}\eta^{\text{cost}}({\bm{\pi}}_{t},{\bm{u}}_{<br>t})]$ |
| $\Delta_{\psi,T}(f)$ | The steering gap: $\mathbb{E}_{\psi,f}[\max_{\bm{\pi}}\eta^{\text{goal}}({\bm{\pi}})-\eta^{\text{<br>goal}}({\bm{\pi}}_{T+1})]$ |
| $\Psi$ | The collection of all history dependent policies |
| $\Psi^{\varepsilon}$ as a short note of $\Psi^{\varepsilon}_{T,U_{\max}}(\mathcal{F};{\bm{\pi}}_{1})$ | $\{\psi\in\Psi|\mathbb{E}_{\psi,f}[\max_{\bm{\pi}}\eta^{\text{goal}}({\bm{\pi}}<br>)-\eta^{\text{goal}}({\bm{\pi}}_{T+1})|{\bm{\pi}}_{1}]\leq\varepsilon\}$ |
| $Q^{n,{\bm{\pi}}}_{h|{\bm{r}}+{\bm{u}}},V^{n,{\bm{\pi}}}_{h|{\bm{r}}+{\bm{u}}},<br>A^{n,{\bm{\pi}}}_{h|{\bm{r}}+{\bm{u}}}$ | The Q-value, V-value and advantage value functions for agent $n$ |
| $f_{\text{MLE}}$ | The Maximal Likelihood Estimator (introduced in Def. 4.3) |
| $b_{t}$ | Model belief state $[\Pr(f|\{{\bm{\pi}}_{t^{\prime}},u_{t^{\prime}}\}_{t^{\prime}=1}^{t},{\bm{\pi}<br>}_{t})]_{f\in\mathcal{F}}\in\mathcal{R}^{|\mathcal{F}|}$ |
| $\psi^{\text{Explore}}/\psi^{\text{Exploit}}$ | The exploration/exploitation policy in FETE framework. |
| $O(\cdot),\Omega(\cdot),\Theta(\cdot),\widetilde{O}(\cdot),\widetilde{\Omega}(<br>\cdot),\widetilde{\Theta}(\cdot)$ | Standard Big-O notations, $\widetilde{(\cdot)}$ omits the log terms. |

## Appendix B Missing Details in the Main Text

### B.1 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 a situation involving a coordination problem where people can choose between an inferior/unsustainable communication or transportation technology that is cheap (the Gather action) and a superior technology that is sustainable but more expensive (the Hunt action).
If 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 be sub-optimal.
The mediator’s goal is to steer the population to adopt the superior technology.

### B.2 Additional Related Works

We first complements the comparison with Zhang et al., () in Sec. 1.1 by noting a minor but worth to be mentioned difference between our setting and (Zhang et al.,, ) in terms of incentive schemes.
While they consider that the mediator influences the agents’ learning dynamics through a scalar payment function, we operate with additional steering rewards in a multi-dimensional reward vector space.
As a 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.,, ).

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.,, ; Yang et al.,, ; Willi et al.,, ; Lu et al.,, ; Willis et al.,, ; Zhao et al.,, ).
Although the ways of influencing agents are similar to our setting, we study the problem of a 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, it is an important question to design learning dynamics and understand their convergence properties (Hernandez-Leal et al.,, ).
Previous works has established near-optimal convergence guarantees to equilibra (Daskalakis et al.,, ; Cai et al.,, ).
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.,, ; Bai et al.,, ; Zhang et al.,, ; Leonardos et al.,, ; Yardim et al.,, ; ; ).
However, most of these results only have guarantees on solving an arbitrary equilibrium when multiple equilibria exists, and it is unclear how to 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 to problems where the lower level consists of solving an equilibrium problem (Luo et al.,, ). (Li et al.,, ; Liu et al.,, ; Wang et al.,, ; ; Yang et al.,, ). These works consider variants of an MPEC and present gradient based approaches, most of 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, a setup such as ours can be modelled as a Stackelberg game. Several works have considered finding Stackelberg equilibria using RL (Gerstgrasser and Parkes,, ; Zhong et al.,, ) or gradient-based approaches (Fiez et al.,, ). Deng et al., () showed how agents can manipulate learning algorithms to achieve more reward, as if they were playing a Stackelberg game. Related problems are implementation theory (Monderer and Tennenholtz,, ) and equilibrium selection (Harsanyi and Selten,, ).
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.,, ; Baumann et al.,, ; Guo et al.,, ). In the case of congestion games, mechanisms have been proposed to circumvent the price of anarchy (Balcan et al.,, ; Paccagnan and Gairing,, ; Roughgarden and Tardos,, ), i.e. equililbria with low social welfare.

There is also a line of work has focused on control strategies for evolutionary games (Gong et al.,, ; Paarporn et al.,, ). However, the game and learning dynamics differ significantly from our setting. For a full survey of control-theoretic approaches, we refer the reader to Ratliff et al., (); Riehl et al., ().

##### Bilevel Reinforcement Learning

Bilevel RL considers the problem of designing an MDP—by for example changing the rewards—with a desireable optimal policy. Recently, several works have studied gradient-based approaches to find such good MDP configurations (Chen et al.,, ; Chakraborty et al.,, ; Shen et al.,, ; Thoma et al.,, ). While similar in some regards, in this setting we assume the lower level is a Markov 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 a desired outcome within a certain amount of time. Therefore our upper-level problem is a strategic decision-making problem, solved by RL instead of running gradient descent on some parameter space.

##### Episodic RL and Non-Episodic RL

Most of the existing RL literature focus on 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,, ; Dann et al.,, ).
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.,, ; Jin et al.,, ) or sample complexity (Dann and Brunskill,, )) in episodic RL setting is not suitable in our case, which targets at finding a near-optimal policy in maximizing return.
This motivates us to consider the new objective (Obj. (1)).

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 infinite-horizon MDPs with stationary transitions, where people consider the discounted (Schulman et al.,, ; Dong et al.,, ) or average return (Auer et al.,, ; Wei et al.,, ).
The infinit-horizon setting with non-stationary dynamics is known as the continual RL (Khetarpal et al.,, ; Abel et al.,, ), 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 to Markov Decision Process

A finite-horizon Markov Decision Process is specified by a tuple $M:=\{x_{1},T,\mathcal{X},\mathcal{U},{\mathbb{T}},(\eta,\eta^{\text{term}})\}$, where $x_{1}$ is the fixed initial state, $T$ is the horizon length, $\mathcal{X}$ is the state space, $\mathcal{U}$ is the action space.
Besides, ${\mathbb{T}}:=\{{\mathbb{T}}_{t}\}_{t\in[T]}$ with ${\mathbb{T}}_{t}:\mathcal{X}\times\mathcal{U}\rightarrow\Delta(\mathcal{X})$ denoting the transition function(^5^55In this paper, we focus on stationary transition function, i.e. ${\mathbb{T}}_{1}=...={\mathbb{T}}_{T}$.), $\eta:=\{\eta_{t}\}_{t\in[T]}$ with $\eta_{t}:\mathcal{X}\times\mathcal{U}\rightarrow[0,1]$ is the normal reward function and $\eta^{\text{term}}:\mathcal{X}\times\mathcal{U}\rightarrow[0,1]$ denotes the additional terminal reward function.
In this paper, without further specification, we will consider history dependent non-stationary policies $\Psi:=\{\psi:=\{\psi_{1},...,\psi_{T}\}|\forall t\in[T],\psi_{t}:(\mathcal{X}
\times\mathcal{U})^{t-1}\times\mathcal{X}\rightarrow\Delta(\mathcal{U})\}$. Given a $\psi\in\Psi$, an episode of $M$ is generated by:
$\forall t\in[T],~{}{\bm{u}}_{t}\sim\psi_{t}(\cdot|\{x_{t^{\prime}},{\bm{u}}_{t
^{\prime}}\}_{t^{\prime}=1}^{t-1},x_{t}),~{}\eta_{t}\leftarrow\eta_{t}(x_{t},{
\bm{u}}_{t}),~{}x_{t+1}\sim{\mathbb{T}}_{t}(\cdot|x_{t},{\bm{u}}_{t});~{}\eta^
{\text{term}}\leftarrow\eta^{\text{term}}(x_{T+1});$

### B.4 Algorithm for Learning Optimal (History-Independent) Strategy when f ∗ superscript 𝑓 f^{*} italic_f start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT is Known

Figure: Algorithm 3 Learning with Known Steering Dynamics

### B.5 Algorithm for Learning Belief-State Dependent Steering Strategy

Figure: Algorithm 4 Solving Obj. (1) by Learning Belief State-Dependent Strategy

## Appendix C Missing Proofs in Section 3

See 3.3

###### Proof.

Suppose $\Psi^{\varepsilon/|\mathcal{F}|}$ is non-empty, we denote $\psi^{\varepsilon/|\mathcal{F}|}$ as one of the elements in $\Psi^{\varepsilon/|\mathcal{F}|}$. By definition, since $\max_{\bm{\pi}}\eta^{\text{goal}}({\bm{\pi}})$ is fixed, we have:

$$ $\displaystyle\psi^{*}\leftarrow\arg\max_{\psi}\frac{1}{|\mathcal{F}|}\sum_{f \in\mathcal{F}}-\beta\Delta(\psi,f,T)-C(\psi,f,T).$ $$

If $\beta\geq\frac{U_{\max}NHT|\mathcal{F}|}{\varepsilon^{\prime}}$, by definition,

$$ $\displaystyle 0\leq$ $\displaystyle\Big{(}\frac{1}{|\mathcal{F}|}\sum_{f\in\mathcal{F}}-\beta\Delta( \psi^{*},f,T)-C(\psi^{*},f,T)\Big{)}-\Big{(}\frac{1}{|\mathcal{F}|}\sum_{f\in \mathcal{F}}-\beta\Delta(\psi^{\varepsilon/|\mathcal{F}|},f,T)-C(\psi^{ \varepsilon/|\mathcal{F}|},f,T)\Big{)}$ $\displaystyle\leq$ $\displaystyle\frac{1}{|\mathcal{F}|}\sum_{f\in\mathcal{F}}\beta\Big{(}\Delta( \psi^{\varepsilon/|\mathcal{F}|},f,T)-\Delta(\psi^{*},f,T)\Big{)}+U_{\max}NHT$ (the steering reward $u\in[0,U_{\max}]$ ) $\displaystyle\leq$ $\displaystyle\frac{1}{|\mathcal{F}|}\sum_{f\in\mathcal{F}}\beta\Big{(}\frac{ \varepsilon}{|\mathcal{F}|}-\Delta(\psi^{*},f,T)\Big{)}+U_{\max}NHT$ ( $\psi^{\varepsilon/|\mathcal{F}|}\in\Psi^{\varepsilon}_{T,U_{\max}}(\mathcal{F})$ ) $\displaystyle\leq$ $\displaystyle\frac{U_{\max}NHT}{\varepsilon^{\prime}}\Big{(}\frac{\varepsilon} {|\mathcal{F}|}-\frac{1}{|\mathcal{F}|}\sum_{f\in\mathcal{F}}\Delta(\psi^{*},f ,T)\Big{)}+U_{\max}NHT$ $$

As a direct observation, if $\mathbb{E}_{f\sim\text{Unif}(\mathcal{F})}[\Delta(\psi^{*},f,T)]=\frac{1}{|
\mathcal{F}|}\sum_{f\in\mathcal{F}}\Delta(\psi^{*},f,T)>\frac{\varepsilon+
\varepsilon^{\prime}}{|\mathcal{F}|}$, the RHS will be strictly less than 0, which results in contradiction.
Therefore, we must have

$$ $\displaystyle\forall f\in\mathcal{F},\quad\Delta(\psi^{*},f,T)\leq|\mathcal{F} |\cdot\mathbb{E}_{f\sim\text{Unif}(\mathcal{F})}[\Delta(\psi^{*},f,T)]\leq \varepsilon+\varepsilon^{\prime}.$ $$

which implies $\psi^{*}\in\Psi^{\varepsilon+\varepsilon^{\prime}}$.

Next, we show the Pareto Optimality.
If there exists $\psi$ and $f$ such that

- •
For all $f^{\prime}\in\mathcal{F}$ with $f\neq f^{\prime}$, $C(\psi^{*},f,T)\geq C(\psi,f,T)$ and $\Delta(\psi^{*},f,T)\geq\Delta(\psi,f,T)$;
- •
For $f$, either $C(\psi^{*},f,T)>C(\psi,f,T)$ and $\Delta(\psi^{*},f,T)\geq\Delta(\psi,f,T)$ or $C(\psi^{*},f,T)\geq C(\psi,f,T)$ and $\Delta(\psi^{*},f,T)>\Delta(\psi,f,T)$.

Therefore, we must have:

$$ $\displaystyle\frac{1}{|\mathcal{F}|}\sum_{f\in\mathcal{F}}\beta\Delta(\psi,f,T )-C(\psi,f,T)<\frac{1}{|\mathcal{F}|}\sum_{f\in\mathcal{F}}\beta\Delta(\psi^{* },f,T)-C(\psi^{*},f,T),$ $$

which conflicts with the optimality condition of Obj. (1).
∎

###### Proof.

## Appendix D Missing Proofs for Existence when the True Model f ∗ superscript 𝑓 f^{*} italic_f start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT is Known

In this section, we study the Policy Mirror Descent as a concrete example.
In Appx. D.1, we provide more details about PMD.
Then, we study the PMD with exact updates and stochastic updates in Appx. D.2.1 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\in[N]$, the updates at step $t\in[T]$ follows:

$$ $\displaystyle\forall h\in[H],s_{h}\in\mathcal{S},\quad$ $\displaystyle\theta^{n}_{t+1,h}(\cdot|s_{h})\leftarrow\theta_{t,h}^{n}(\cdot|s _{h})+\alpha{\widehat{A}}^{n,{\bm{\pi}}_{t}}_{h|r^{n}+u^{n}_{t}}(s,\cdot),$ (Update in the mirror space) $\displaystyle z^{n}_{t+1,h}(\cdot|s_{h})\leftarrow(\nabla\phi^{n})^{-1}(\theta ^{n}_{t+1,h}(\cdot|s_{h}))$ (Map $\theta$ back to the primal space) $\displaystyle\pi^{n}_{t+1,h}(\cdot|s_{h})\leftarrow\operatorname*{arg\,min}_{z \in\Delta(\mathcal{A}^{n})}D_{\phi^{n}}(z,z^{n}_{t+1,h}(\cdot|s_{h})),$ (Projection) $$

Similar to Def. 4.1, here ${\widehat{A}}^{n,{\bm{\pi}}_{t}}_{h|r^{n}+u^{n}_{t}}$ is some random estimation for the advantage value $A^{n,{\bm{\pi}}_{t}}_{h|r^{n}+u^{n}_{t}}$ with $\mathbb{E}_{\pi^{n}}[{\widehat{A}}^{n,{\bm{\pi}}_{t}}_{h|r^{n}+u^{n}_{t}}(s_{h
},\cdot)]=0$.
Besides, $\theta^{n}_{t,h}\in{\mathbb{R}}^{|\mathcal{S}||\mathcal{A}|}$ denotes the variable in the dual space.
$\phi^{n}:\text{dom}(\phi^{n})\rightarrow{\mathbb{R}}$ is a function satisfying Assump. C below, which gives the mirror map $\nabla\phi^{n}$; $(\nabla\phi^{n})^{-1}$ is the inverse mirror map; $D_{\phi^{n}}(z,\widetilde{z}):=\phi^{n}(z)-\phi^{n}(\widetilde{z})-\langle
\nabla\phi^{n}(\widetilde{z}),z-\widetilde{z}\rangle$ is the Bregman divergence regarding $\phi^{n}$.

###### Assumption C .

We assume for all $n\in[N]$, $\phi^{n}$ is $\mu$-strongly convex and essentially smooth, i.e. differentiable and $\|\nabla\phi^{n}(z^{k})\|\rightarrow+\infty$ for any sequence $z^{k}\in\text{dom}(\phi^{n})$ converging to a point on the boundary of $\text{dom}(\phi^{n})$.

By Pythagorean Theorem and the strictly convexity of $D_{\phi^{n}}$, the projection ${\bm{\pi}}$ in Def. D.1 is unique.

###### Lemma D.2 .

Given a convex set $\mathcal{C}$ and a function $\phi$ which is $\mu$-strongly convex on $\mathcal{C}$, we have

$$ $\displaystyle\|\arg\min_{z\in\mathcal{C}}D_{\phi}(z,(\nabla\phi)^{-1}(\theta_{ 1}))-\arg\min_{z\in\mathcal{C}}D_{\phi}(z,(\nabla\phi)^{-1}(\theta_{2}))\|\leq \frac{1}{\mu}\|\theta_{1}-\theta_{2}\|_{2}.$ $$

###### Proof.

Given any dual variables $\theta_{1}$ and $\theta_{2}$, and their projection $z_{1}:=\arg\min_{z\in\mathcal{C}}D_{\phi}(z,(\nabla\phi)^{-1}(\theta_{1}))$ and $z_{2}:=\arg\min_{z\in\mathcal{C}}D_{\phi}(z,(\nabla\phi)^{-1}(\theta_{2}))$, by the first order optimality condition, we have:

$$ $\displaystyle\forall z\in\mathcal{C},\quad$ $\displaystyle\langle\nabla\phi(z_{1})-\theta_{1},z-z_{1}\rangle\geq 0,$ $\displaystyle\langle\nabla\phi(z_{2})-\theta_{2},z-z_{2}\rangle\geq 0$ $$

If we choose $z=z_{2}$ in the first equation and $z=z_{1}$ in the second equation, and sum together, we have:

$$ $\displaystyle\langle\theta_{1}-\nabla\phi(z_{1})+\nabla\phi(z_{2})-\theta_{2}, z_{1}-z_{2}\rangle\geq 0,$ $$

By strongly convexity of $\phi$, the above implies:

$$ $\displaystyle\langle\theta_{1}-\theta_{2},z_{1}-z_{2}\rangle\geq\langle\nabla \phi(z_{1})-\nabla\phi(z_{2}),z_{1}-z_{2}\rangle\geq\mu\cdot\|z_{1}-z_{2}\|^{2}$ $$

Therefore,

$$ $\displaystyle\mu\|z_{1}-z_{2}\|\leq\|\theta_{1}-\theta_{2}\|,$ $$

and we finish the proof.
∎

Next, we discuss some concrete examples.

###### Example D.3 (Natural Policy Gradient) .

If we consider the mirror map and Bregman Divergence generated by $\phi^{n}(z):=\sum_{a^{n}\in\mathcal{A}^{n}}z(a^{n})\log z(a^{n})$, we have $D_{\phi}^{n}(z_{1},z_{2})=\text{KL}(z_{1}\|z_{2})$, and recover the NPG in Def. 4.1.
Note that $\phi^{n}$ is 1-strongly convex on the convex set $\Delta(\mathcal{A}^{n})$, Assump. C is satisfied with $\mu=1$.

###### Example D.4 (Online Gradient Ascent (Zinkevich,, 2003 ) ) .

If we consider the Euclidean distance generated by $l_{2}$-norm $\phi^{n}(z)=\frac{1}{2}\|z\|_{2}^{2}$, we recover the projected gradient ascent

###### Definition D.5 .

For each agent $n\in[N]$, the updates at step $t\in[T]$ follows:

$$ $\displaystyle\forall h\in[H],s_{h}\in\mathcal{S},\quad$ $\displaystyle\pi^{n}_{t+1,h}(\cdot|s_{h})\leftarrow\text{Proj}_{\Delta( \mathcal{A}^{n})}(\pi^{n}_{t,h}(\cdot|s_{h})+\alpha{\widehat{A}}^{n,{\bm{\pi}} _{t}}_{h|r^{n}+u^{n}_{t}}(s,\cdot)),$ $$

Note that the projection with Euclidean distance is 1-Lipschitz, Assump. C is satisfied with $\mu=1$.

###### Definition D.1 (Policy Mirror Descent) .

###### Assumption C .

###### Lemma D.2 .

###### Proof.

###### Example D.3 (Natural Policy Gradient) .

###### Example D.4 (Online Gradient Ascent (Zinkevich,, 2003 ) ) .

###### Definition D.5 .

##### Other Notations and Remarks

In the following, we use $\Pi^{+}$ to be the “feasible policy set” (for NPG in Def. 4.1, $\Pi^{+}$ refers to be set of policies bounded away from 0), such that for any ${\bm{\pi}}\in\Pi^{+}$, there exists a dual variable $\theta$ corresponding to ${\bm{\pi}}$, i.e.,

$$ $\displaystyle\forall n\in[N],h\in[H],s_{h}\in\mathcal{S},\quad\pi^{n}_{h}( \cdot|s_{h})\leftarrow\operatorname*{arg\,min}_{z\in\Delta(\mathcal{A}^{n})}D_ {\phi^{n}}(z,(\nabla\phi^{n})^{-1}(\theta^{n}_{h}(\cdot|s_{h}))).$ $$

In the following Lem. D.6, we show that constant shift in $\theta^{n}_{t,h}(\cdot|s_{h})$ does not change the projection result.
Therefore, when we say the dual variable $\theta$ associated with a given policy ${\bm{\pi}}$, we only consider those $\theta$ satisfying
$\mathbb{E}_{a_{h}^{n}\sim\pi^{n}_{h}}[\theta^{n}_{h}(a_{h}^{n}|s_{h})]=0$.

###### Lemma D.6 (Constant Shift does not Change the Projection) .

For any $n\in[N]$, regularizer $\phi^{n}$ satisfying conditions in Assump. C, and any $\theta\in{\mathbb{R}}^{|\mathcal{A}^{n}|}$, consider the constant vector $c\mathrm{\textbf{1}}$, where $c\in{\mathbb{R}}$ is a constant and $\mathrm{\textbf{1}}=\{1,1,...,1\}\in{\mathbb{R}}^{|\mathcal{A}^{n}|}$, we have:

$$ $\displaystyle\operatorname*{arg\,min}_{z\in\Delta(\mathcal{A}^{n})}D_{\phi^{n} }(z,(\nabla\phi^{n})^{-1}(\theta))=\operatorname*{arg\,min}_{z\in\Delta( \mathcal{A}^{n})}D_{\phi^{n}}(z,(\nabla\phi^{n})^{-1}(\theta+c\mathrm{\textbf{ 1}}))$ $$

###### Proof.

$$ $\displaystyle\arg\min_{z\in\Delta(\mathcal{A}^{n})}D_{\phi^{n}}(z,(\nabla\phi^ {n})^{-1}(\theta+c\mathrm{\textbf{1}}))$ $\displaystyle=$ $\displaystyle\arg\min_{z\in\Delta(\mathcal{A}^{n})}\phi^{n}(z)-\langle\theta+c \mathrm{\textbf{1}},z\rangle$ $\displaystyle=$ $\displaystyle\arg\min_{z\in\Delta(\mathcal{A}^{n})}\phi^{n}(z)-\langle\theta,z \rangle+c$ (we have constraints that $z\in\Delta(\mathcal{A}^{n})$ ) $\displaystyle=$ $\displaystyle\arg\min_{z\in\Delta(\mathcal{A}^{n})}\phi^{n}(z)-\langle\theta,z\rangle$ $\displaystyle=$ $\displaystyle\operatorname*{arg\,min}_{z\in\Delta(\mathcal{A}^{n})}D_{\phi^{n} }(z,\theta).$ $$

∎

###### Lemma D.6 (Constant Shift does not Change the Projection) .

###### Proof.

### D.2 Proofs for the Existence of Desired Steering Strategy

We first formally introduce the Lipschitz condition that Thm. 4.2 requires.

###### Assumption D ( $\eta^{\text{goal}}$ is $L$ -Lipschitz) .

For any ${\bm{\pi}},{\bm{\pi}}^{\prime}\in\Pi$, $|\eta^{\text{goal}}({\bm{\pi}})-\eta^{\text{goal}}({\bm{\pi}}^{\prime})|\leq L
\|{\bm{\pi}}-{\bm{\pi}}^{\prime}\|_{2}$.

In the following, in Appx. D.2.1, as a warm-up, we start with the exact case when the estimation ${\widehat{A}}^{\bm{\pi}}$ is exactly the true advantage value $A^{\bm{\pi}}$ (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 as a special case of PMD.

###### Assumption D ( η goal superscript 𝜂 goal \eta^{\text{goal}} italic_η start_POSTSUPERSCRIPT goal end_POSTSUPERSCRIPT is L 𝐿 L italic_L -Lipschitz) .

#### D.2.1 Special Case: PMD with Exact Advantage-Value

###### Lemma D.7 (Existence of Steering Path between Feasible Policies) .

Consider two feasible policies ${\bm{\pi}},{\widetilde{\bm{\pi}}}$ which are induced by dual variables $\{\theta^{n}_{1,h}\}_{h\in[H],n\in[N]}$ and $\{\widetilde{\theta}_{h}^{n}\}_{h\in[H],n\in[N]}$, respectively.
If the agents follow Def. D.1 with exact Q value and start with ${\bm{\pi}}_{1}={\bm{\pi}}$, as long as $U_{\max}\geq 2H+\frac{2}{\alpha T}(\max_{n,h,s_{h},a^{n}_{h}}|\widetilde{
\theta}_{h}^{n}(a^{n}_{h}|s_{h})-\theta_{h}^{n}(a^{n}_{h}|s_{h})-\mathbb{E}_{
\bar{a}_{h}^{n}\sim\pi^{n}_{t,h}(\cdot|s_{h}^{n})}[\widetilde{\theta}_{h}^{n}(
\bar{a}^{n}_{h}|s_{h})-\theta_{h}^{n}(\widetilde{a}^{n}_{h}|s_{h})]|)$, there exists a (history-independent) steering strategy $\psi:=\{\psi_{t}\}_{t\in[T]}$ with $\psi_{t}:\Pi^{+}\rightarrow\mathcal{U}$, s.t., ${\bm{\pi}}_{T+1}=\widetilde{\bm{\pi}}$.

###### Proof.

For agent $n\in[N]$, given a ${\bm{\pi}}_{t}$, we consider the following steering reward functions

$$ $\displaystyle u^{n}_{t,h}(s_{h},a^{n}_{h})=$ $\displaystyle\nu^{n}_{t,h}(s_{h},a^{n}_{h})-A^{n,{\bm{\pi}}_{t}}_{h|r^{n}}(s_{ h},a^{n}_{h})-\mathbb{E}_{\widetilde{a}^{n}\sim\pi^{n}_{t,h}(\cdot|s_{h})}[\nu ^{n}_{t,h}(s_{h},\widetilde{a}^{n}_{h})-A^{n,{\bm{\pi}}_{t}}_{h|r^{n}}(s_{h}, \widetilde{a}^{n}_{h})]$ $\displaystyle-\min_{\bar{s}_{h},\bar{a}^{n}_{h}}\{\nu^{n}_{t,h}(\bar{s}_{h}, \bar{a}^{n}_{h})-A^{n,{\bm{\pi}}_{t}}_{h|r^{n}}(\bar{s}_{h},\bar{a}^{n}_{h})- \mathbb{E}_{\widetilde{a}^{n}\sim\pi^{n}_{t,h}(\cdot|s_{h})}[\nu^{n}_{t,h}( \bar{s}_{h},\widetilde{a}^{n}_{h})-A^{n,{\bm{\pi}}_{t}}_{h|r^{n}}(\bar{s}_{h}, \widetilde{a}^{n}_{h})]\},$ $$

where $\nu^{n}_{t,h}:\mathcal{S}\times\mathcal{A}^{n}\rightarrow{\mathbb{R}}$ will be defined later. By construction, we have:

$$ $\displaystyle\mathbb{E}_{a^{n}_{h}\sim\pi^{n}_{t,h}(\cdot|s_{h})}[u^{n}_{t,h}( s_{h},a^{n}_{h})]$ (2) $\displaystyle=$ $\displaystyle-\min_{\bar{s}_{h},\bar{a}^{n}_{h}}\{\nu^{n}_{t,h}(\bar{s}_{h}, \bar{a}^{n}_{h})-A^{n,{\bm{\pi}}_{t}}_{h|r^{n}}(\bar{s}_{h},\bar{a}^{n}_{h})- \mathbb{E}_{\widetilde{a}^{n}\sim\pi^{n}_{t,h}(\cdot|s_{h})}[\nu^{n}_{t,h}( \bar{s}_{h},\widetilde{a}^{n}_{h})-A^{n,{\bm{\pi}}_{t}}_{h|r^{n}}(\bar{s}_{h}, \widetilde{a}^{n}_{h})]\},$ (3) $$

which is a constant and independent w.r.t. $s_{h},a^{n}_{h}$.
Besides, by definition, we can ensure the non-negativity of $u^{n}_{t,h}$.
As a result,

$$ $\displaystyle\forall t\in[T],\quad$ $\displaystyle Q^{t,{\bm{\pi}}_{t}}_{h|r^{n}+u^{n}_{t}}(s_{h},a^{n}_{h})$ $\displaystyle=$ $\displaystyle A^{t,{\bm{\pi}}_{t}}_{h|r^{n}}(s_{h},a^{n}_{h})+u^{n}_{t,h}(s_{h },a^{n}_{h})+C_{h}(s_{h})$ (Eq. ( 3 )) $\displaystyle=$ $\displaystyle\nu^{n}_{t,h}(s_{h},a^{n}_{h})+C^{\prime}_{h}(s_{h}).$ (4) $$

where we use $C_{h}(s_{h})$ and $C_{h}^{\prime}(s_{h})$ to denote some state-dependent but action-independent value.
According to Lem. D.6, under the above steering reward design, the dynamics of ${\bm{\pi}}_{1},...,{\bm{\pi}}_{t},...,{\bm{\pi}}_{T}$ can be described by the following dynamics:

$$ $\displaystyle\forall t\in[T],~{}\forall n\in[N],h\in[H],s_{h}\in\mathcal{S}:\quad$ $\displaystyle\theta^{n}_{t+1,h}(\cdot|s_{h})\leftarrow\theta^{n}_{t,h}(\cdot|s _{h})+\alpha\nu^{n}_{t,h}(s_{h},a^{n}_{h})$ (5) $\displaystyle\pi^{n}_{t+1,h}(\cdot|s_{h})\leftarrow\operatorname*{arg\,min}_{z \in\Delta(\mathcal{A}^{n})}D_{\phi^{n}}(z,\theta^{n}_{t+1,h}(\cdot|s_{h})),$ (6) $$

Now we consider the following choice of $\nu^{n}_{t,h}$:

$$ $\displaystyle\nu^{n}_{t,h}(s_{h},a^{n}_{h})=\frac{\widetilde{\theta}_{h}^{n}(a ^{n}_{h}|s_{h})-\theta_{h}^{n}(a^{n}_{h}|s_{h})}{\alpha T},$ $$

which implies $\theta_{T+1}=\widetilde{\theta}$, and therefore, ${\bm{\pi}}_{T+1}={\widetilde{\bm{\pi}}}$.
Besides, the steering reward function can be upper bounded by:

$$ $\displaystyle u^{n}_{t,h}(s_{h},a^{n}_{h})\leq$ $\displaystyle 2\max_{\bar{s}_{h},\bar{a}^{n}_{h}}|\nu^{n}_{t,h}(\bar{s}_{h}, \bar{a}^{n}_{h})-A^{n,{\bm{\pi}}_{t}}_{h|r^{n}}(\bar{s}_{h},\bar{a}^{n}_{h})- \mathbb{E}_{\widetilde{a}^{n}\sim\pi^{n}_{t,h}(\cdot|s_{h})}[\nu^{n}_{t,h}( \bar{s}_{h},\widetilde{a}^{n}_{h})-A^{n,{\bm{\pi}}_{t}}_{h|r^{n}}(\bar{s}_{h}, \widetilde{a}^{n}_{h})]|$ $\displaystyle\leq$ $\displaystyle 2H+\frac{2}{\alpha T}(\max_{n,h,s_{h},a^{n}_{h}}|\widetilde{ \theta}_{h}^{n}(a^{n}_{h}|s_{h})-\theta_{h}^{n}(a^{n}_{h}|s_{h})|),$ $$

which implies the appropriate choice of $U_{\max}$.

∎

###### Theorem D.8 .

Under Assump. D, given the initial ${\bm{\pi}}_{1}:={\bm{\pi}}\in\Pi^{+}$, for any $T\geq 1$ and $\varepsilon>0$, if the agents follow Def. 4.1 with exact Q value, then $\Psi^{\varepsilon}_{T,U_{\max}}\neq\emptyset$ if the following conditions are satisfied:

- •
There exists feasible ${\widetilde{\bm{\pi}}}\in\Pi^{+}$ such that $\eta^{\text{goal}}({\widetilde{\bm{\pi}}})\geq\max_{\bm{\pi}}\eta^{\text{goal}
}({\bm{\pi}})-\varepsilon$
- •
Denote $\theta$ and $\widetilde{\theta}$ as the dual variables associated with ${\bm{\pi}}$ and ${\widetilde{\bm{\pi}}}$, respectively. We require $U_{\max}\geq 2H+\frac{2}{\alpha T}(\max_{n,h,s_{h},a^{n}_{h}}|\widetilde{
\theta}_{h}^{n}(a^{n}_{h}|s_{h})-\theta_{h}^{n}(a^{n}_{h}|s_{h})|)$

###### Proof.

The proof is a directly application of Lem. D.7.
∎

###### Lemma D.7 (Existence of Steering Path between Feasible Policies) .

###### Proof.

###### Theorem D.8 .

###### Proof.

##### NPG as a Special Case

For NPG, we have the following results.

###### Lemma D.9 .

Given $\forall{\bm{\pi}},\widetilde{\bm{\pi}}\in\Pi^{+}$, $T\geq 1$, if the agents follow Def. 4.1 with exact adv-value and start from ${\bm{\pi}}_{1}={\bm{\pi}}$, by choosing $U_{\max}$ appropriately,
there exists a (history-independent) steering strategy $\psi:=\{\psi_{t}\}_{t\in[T]}$ with $\psi_{t}:\Pi^{+}\rightarrow\mathcal{U}$, s.t., ${\bm{\pi}}_{T+1}=\widetilde{\bm{\pi}}$.

###### Theorem D.10 .

Under Assump. D, given any initial ${\bm{\pi}}_{1}\in\Pi^{+}$, for any $T\geq 1$ and $\varepsilon>0$, if the agents follow Def. 4.1 with exact Q value, by choosing $U_{\max}$ appropriately, we have $\Psi^{\varepsilon}\neq\emptyset$.

###### Lemma D.9 .

###### Theorem D.10 .

##### 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 ${\bm{\pi}},{\widetilde{\bm{\pi}}}\in\Pi^{+}$, we consider the dual variables $\theta,\widetilde{\theta}$ such that:

$$ $\displaystyle\theta^{n}_{h}(\cdot|s_{h})=\log\pi^{n}_{h}(\cdot|s_{h})-\mathbb{ E}_{a_{h}^{n}\sim\pi^{n}_{h}}[\log\pi^{n}_{h}(a_{h}^{n}|s_{h})],\quad \widetilde{\theta}^{n}_{h}(\cdot|s_{h})=\log\widetilde{\pi}^{n}_{h}(\cdot|s_{h })-\mathbb{E}_{a_{h}^{n}\sim\pi^{n}_{h}}[\log\widetilde{\pi}^{n}_{h}(a_{h}^{n} |s_{h})].$ (7) $$

##### Choice of U max subscript 𝑈 U_{\max} italic_U start_POSTSUBSCRIPT roman_max end_POSTSUBSCRIPT in Lem. D.9

By applying Lem. D.7 and Thm. D.8, we consider the following choice of $U_{\max}$

$$ $\displaystyle U_{\max}\geq 2H+\frac{2}{\alpha T}(\max_{n,h,s_{h},a_{h}}|\log \frac{{\widetilde{\pi}}^{n}_{h}(s_{h},a^{n}_{h})}{\pi^{n}_{h}(s_{h},a^{n}_{h}) }-\mathbb{E}_{\widetilde{a}^{n}_{h}\sim\pi^{n}_{h}}[\log\frac{{\widetilde{\pi} }^{n}_{h}(s_{h},\widetilde{a}^{n}_{h})}{\pi^{n}_{h}(s_{h},\widetilde{a}^{n}_{h })}]|).$ (8) $$

##### Choice of U max subscript 𝑈 U_{\max} italic_U start_POSTSUBSCRIPT roman_max end_POSTSUBSCRIPT in Thm. D.10

We denote ${\bm{\pi}}^{*}\in\operatorname*{arg\,max}_{{\bm{\pi}}\in\Pi}\eta^{\text{goal}}
({\bm{\pi}})\not\in\Pi^{+}$.

When ${\bm{\pi}}^{*}\in\Pi^{+}$, we can directly apply Thm. D.8 with ${\widetilde{\bm{\pi}}}\leftarrow{\bm{\pi}}^{*}$, and choosing $U_{\max}$ correspondingly following Eq. (8).

However, in some cases, ${\bm{\pi}}^{*}\not\in\Pi^{+}$ because it takes deterministic action in some states.
In that case, since $\eta^{\text{goal}}$ is $L$-Lipschitz in ${\bm{\pi}}$, we can consider the mixture policy ${\widetilde{\bm{\pi}}}:=(1-O(\frac{\varepsilon}{L})){\bm{\pi}}^{*}+O(\frac{
\varepsilon}{L}){\bm{\pi}}_{\text{Uniform}}$, where ${\bm{\pi}}_{\text{Uniform}}$ is the uniform policy.
As a result, we have ${\widetilde{\bm{\pi}}}\in\Pi^{+}$ as well as $\eta^{\text{goal}}({\widetilde{\bm{\pi}}})\geq\max_{{\bm{\pi}}\in\Pi}\eta^{
\text{goal}}({\bm{\pi}})-\varepsilon$.
Then the $U_{\max}$ 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. D and Assump. C, given the initial ${\bm{\pi}}_{1}:={\bm{\pi}}\in\Pi^{+}$, for any $\varepsilon>0$, if the agents follow Def. 4.1 under the Assump. B, then $\Psi^{\varepsilon}_{T,U_{\max}}\neq\emptyset$ if the following conditions are satisfied:

- •
There exists feasible ${\widetilde{\bm{\pi}}}\in\Pi^{+}$ such that $\eta^{\text{goal}}({\widetilde{\bm{\pi}}})\geq\max_{\bm{\pi}}\eta^{\text{goal}
}({\bm{\pi}})-\frac{\varepsilon}{2}$
- •
Denote $\theta$ and $\widetilde{\theta}$ as the dual variables associated with ${\bm{\pi}}$ and ${\widetilde{\bm{\pi}}}$, respectively. We require $U_{\max}\geq 2(H+\frac{\lambda_{\min}}{\alpha\lambda_{\max}^{2}}(1+\frac{
\lambda_{\min}}{\lambda_{\max}})^{T}\|\widetilde{\theta}-\theta\|_{2})$ and $T=\Theta(\frac{\lambda_{\max}^{2}}{\lambda_{\min}^{2}}\log\frac{L\|\widetilde{
\theta}-\theta\|_{2}}{\mu\varepsilon})$.

###### Remark D.12 .

In Thm. D.2.2, our bound for $U_{\max}$ here is just a worst-case bound to handle the noisy updates in the worst case.
With high probability, the dual variable $\theta_{t}$ will converge to $\widetilde{\theta}$ and the steering reward does not have to be as large as $U_{\max}$.

###### Proof.

Given a ${\bm{\pi}}_{t}$, we consider the following steering reward $u_{t}$:

$$ $\displaystyle u^{n}_{t,h}(s_{h},a^{n}_{h})=$ $\displaystyle\nu^{n}_{t,h}(s_{h},a^{n}_{h},{\bm{\pi}}_{t})-A^{n,{\bm{\pi}}_{t} }_{h|r^{n}}(s_{h},a^{n}_{h})-\mathbb{E}_{\widetilde{a}^{n}\sim\pi^{n}_{t,h}( \cdot|s_{h})}[\nu^{n}_{t,h}(s_{h},\widetilde{a}^{n}_{h},{\bm{\pi}}_{t})-A^{n,{ \bm{\pi}}_{t}}_{h|r^{n}}(s_{h},\widetilde{a}^{n}_{h})]$ $\displaystyle-\min_{\bar{s}_{h},\bar{a}^{n}_{h}}\{\nu^{n}_{t,h}(\bar{s}_{h}, \bar{a}^{n}_{h},{\bm{\pi}}_{t})-A^{n,{\bm{\pi}}_{t}}_{h|r^{n}}(\bar{s}_{h}, \bar{a}^{n}_{h})-\mathbb{E}_{\widetilde{a}^{n}\sim\pi^{n}_{t,h}(\cdot|s_{h})}[ \nu^{n}_{t,h}(\bar{s}_{h},\widetilde{a}^{n}_{h},{\bm{\pi}}_{t})-A^{n,{\bm{\pi} }_{t}}_{h|r^{n}}(\bar{s}_{h},\widetilde{a}^{n}_{h})]\},$ $$

Here we choose $\nu^{n}_{t,h}(s_{h},a_{h}^{n},{\bm{\pi}}_{t}):=\frac{1}{\gamma}\cdot(
\widetilde{\theta}^{n}_{h}(a_{h}^{n}|s_{h})-\theta^{n}_{t+1,h}(a_{h}^{n}|s_{h}))$, where $\widetilde{\theta}$ denotes the dual variable of policy $\widetilde{\bm{\pi}}$ and $\gamma$ will be determined later.
Comparing with the design in the proof of Thm. D.8, here the “driven term” $\nu^{n}_{h}$ need to depend on ${\bm{\pi}}_{t}$ because of the randomness in updates.

As we can see, $u^{n}_{t,h}(s_{h},a^{n}_{h})\geq 0$, and for each $t$, we have:

$$ $\displaystyle\mathbb{E}[\|\widetilde{\theta}-\theta_{t+1}\|_{2}^{2}]=$ $\displaystyle\mathbb{E}[\|\widetilde{\theta}-\theta_{t}\|_{2}^{2}]-2\mathbb{E} [\langle\widetilde{\theta}-\theta_{t},\theta_{t+1}-\theta_{t}\rangle]+\mathbb{ E}[\|\theta_{t+1}-\theta_{t}\|_{2}^{2}]$ $\displaystyle=$ $\displaystyle\mathbb{E}[\|\widetilde{\theta}-\theta_{t}\|_{2}^{2}]-2\alpha \mathbb{E}[\langle\widetilde{\theta}-\theta_{t},{\widehat{A}}^{{\bm{\pi}}_{t}} _{|{\bm{r}}+{\bm{u}}_{t}}\rangle]+\mathbb{E}[\|{\widehat{A}}^{{\bm{\pi}}_{t}}_ {|{\bm{r}}+{\bm{u}}_{t}}\|_{2}^{2}]$ $\displaystyle\leq$ $\displaystyle(1-2\lambda_{\min}\frac{\alpha}{\gamma}+\lambda_{\max}^{2}\frac{ \alpha^{2}}{\gamma^{2}})\mathbb{E}[\|\widetilde{\theta}-\theta_{t}\|_{2}^{2}],$ $$

which implies

$$ $\displaystyle\mathbb{E}[\|\widetilde{\theta}-\theta_{T+1}\|_{2}^{2}]\leq(1-2 \lambda_{\min}\frac{\alpha}{\gamma}+\lambda_{\max}^{2}\frac{\alpha^{2}}{\gamma ^{2}})^{T}\|\widetilde{\theta}-\theta\|_{2}^{2}.$ $$

We consider the choice $\gamma=\frac{\lambda_{\max}^{2}\alpha}{\lambda_{\min}}$, which implies,

$$ $\displaystyle\mathbb{E}[\|\widetilde{\theta}-\theta_{T+1}\|_{2}^{2}]\leq(1- \frac{\lambda_{\min}^{2}}{\lambda_{\max}^{2}})^{T}\|\widetilde{\theta}-\theta \|_{2}^{2}.$ $$

When $T=2c_{0}\frac{\lambda_{\max}^{2}}{\lambda_{\min}^{2}}\log\frac{2L\|\widetilde{
\theta}-\theta\|_{2}}{\mu\varepsilon}\geq c_{0}\log_{1-\frac{\lambda^{2}_{\min
}}{\lambda_{\max}^{2}}}(\frac{\nu^{2}\varepsilon^{2}}{2L^{2}\|\widetilde{
\theta}-\theta\|_{2}^{2}})$ for some constant $c_{0}$, we have:

$$ $\displaystyle\mathbb{E}[\|\widetilde{\theta}-\theta_{T+1}\|_{2}]\leq\frac{\mu \varepsilon}{2L},$ $$

which implies,

$$ $\displaystyle\mathbb{E}[\eta({\bm{\pi}}^{*})-\eta^{\text{goal}}({\bm{\pi}}_{T+ 1})]\leq\frac{\varepsilon}{2}+L\mathbb{E}[\|{\widetilde{\bm{\pi}}}-{\bm{\pi}}_ {T+1}\|_{2}]\leq\frac{\varepsilon}{2}+\frac{L}{\mu}\mathbb{E}[\|\widetilde{ \theta}-\theta_{T+1}\|_{2}]=\varepsilon.$ $$

Next, we discuss the choice of $U_{\max}$, by Assump. B, we know,

$$ $\displaystyle\|\widetilde{\theta}-\theta_{t+1}\|_{2}=$ $\displaystyle\|\widetilde{\theta}-\theta_{t}-\alpha{\widehat{A}}^{{\bm{\pi}}_{ t}}_{|{\bm{r}}+{\bm{u}}_{t}}\|_{2}\leq\|\widetilde{\theta}-\theta_{t}\|_{2}+ \alpha\|{\widehat{A}}^{{\bm{\pi}}_{t}}_{|{\bm{r}}+{\bm{u}}_{t}}\|_{2}$ $\displaystyle\leq$ $\displaystyle\|\widetilde{\theta}-\theta_{t}\|_{2}+\alpha\lambda_{\max}\|A^{{ \bm{\pi}}_{t}}_{|{\bm{r}}+{\bm{u}}_{t}}\|_{2}$ $\displaystyle\leq$ $\displaystyle(1+\frac{\lambda_{\min}}{\lambda_{\max}})\|\widetilde{\theta}- \theta_{t}\|_{2}$ $$

where we use the fact that $\|A^{{\bm{\pi}}_{\tau}}_{|{\bm{r}}+{\bm{u}}_{\tau}}\|_{2}=\frac{1}{\gamma}\|
\widetilde{\theta}-\theta_{\tau}\|_{2}$ and our choice of $\gamma$.
Therefore, for all $t\in[T]$, $\|\widetilde{\theta}-\theta_{t}\|_{2}\leq(1+\frac{\lambda_{\min}}{\lambda_{
\max}})^{T}\|\widetilde{\theta}-\theta\|_{2}$.
To ensure our design of $u^{n}_{t,h}$ is feasible, we need to set:

$$ $\displaystyle U_{\max}=$ $\displaystyle 2(H+\frac{1}{\gamma}(1+\frac{\lambda_{\min}}{\lambda_{\max}})^{T }\|\widetilde{\theta}-\theta\|_{2})$ $\displaystyle=$ $\displaystyle 2(H+\frac{\lambda_{\min}}{\alpha\lambda_{\max}^{2}}(1+\frac{ \lambda_{\min}}{\lambda_{\max}})^{T}\|\widetilde{\theta}-\theta\|_{2}).$ $$

∎

###### Theorem D.11 (Formal Version of Thm. 4.2 for the general PMD) .

###### Remark D.12 .

###### Proof.

##### Proof for Thm. 4.2

As we discuss in Example. D.3, Assump. C is satisfied with $\mu=1$.
The proof is a direct application of Thm. D.8 with the same choice of dual variables as Eq. (7).

## Appendix E Missing Proofs for Existence when the True Model f ∗ superscript 𝑓 f^{*} italic_f start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT is Unknown

In the following, we establish some technical lemmas for the maximal likelihood estimator.
Given a steering dynamics model class $\mathcal{F}$ and the true dynamics $f^{*}\sim p_{0}$ and a steering strategy $\psi:\Pi\rightarrow\mathcal{U}$, we consider a steering trajectory $\tau_{T_{0}}:=\{{\bm{\pi}}_{1},{\bm{u}}_{1},...,{\bm{\pi}}_{T_{0}},{\bm{u}}_{T
_{0}},{\bm{\pi}}_{T_{0}+1}\}$ generated by:

$$ $\displaystyle\forall t\in[T_{0}],\quad{\bm{u}}_{t}\leftarrow\psi({\bm{\pi}}_{t }),~{}{\bm{\pi}}_{t+1}\sim f^{*}(\cdot|{\bm{\pi}}_{t},{\bm{u}}_{t}),$ (9) $$

where ${\bm{\pi}}_{t+1}$ is independent w.r.t. ${\bm{\pi}}_{t^{\prime}}$ for $t^{\prime}<t$ conditioning on ${\bm{\pi}}_{t}$.
In the following, we will denote $\tau_{t}:=\{{\bm{\pi}}_{1},{\bm{u}}_{1},...,{\bm{\pi}}_{t},{\bm{u}}_{t},{\bm{
\pi}}_{t+1}\}$ to be the trajectory up to step $t$.

For any $f\in\mathcal{F}$, we define:

$$ $\displaystyle p_{f}(\tau_{T_{0}}):=\prod_{t=1}^{T_{0}}f({\bm{\pi}}_{t+1}|{\bm{ \pi}}_{t},{\bm{u}}_{t}).$ (10) $$

Given $\tau_{T_{0}}$, we use $\bar{\tau}_{T_{0}}$ to denote the “tangent” trajectory $\{({\bm{\pi}}_{t},{\bm{u}}_{t},\bar{{\bm{\pi}}}_{t+1})\}_{t=1}^{T_{0}}$ where $\bar{{\bm{\pi}}}_{t+1}\sim f^{*}(\cdot|{\bm{\pi}}_{t},{\bm{u}}_{t})$ is independently sampled from the same distribution as ${\bm{\pi}}_{t+1}$ conditioning on the same ${\bm{\pi}}_{t}$ and $u_{t}$.

###### Lemma E.1 .

Let $l:\Pi\times\mathcal{U}\times\Pi\rightarrow{\mathbb{R}}$ be a real-valued loss function.
Define $L(\tau_{T_{0}}):=\sum_{t=1}^{T_{0}}l({\bm{\pi}}_{t},{\bm{u}}_{t},{\bm{\pi}}_{t
+1})$ and $L(\bar{\tau}_{T_{0}}):=\sum_{t=1}^{T_{0}}l({\bm{\pi}}_{t},{\bm{u}}_{t},\bar{{
\bm{\pi}}}_{t+1})$. Then, for arbitrary $t\in[T_{0}]$,

$$ $\displaystyle\mathbb{E}[\exp(L(\tau_{t})-\log\mathbb{E}_{\bar{\tau}_{T_{0}}}[ \exp(L(\bar{\tau}_{t}))|\tau_{t}])]=1.$ $$

###### Proof.

We denote $E^{i}:=\mathbb{E}_{\bar{{\bm{\pi}}}_{i+1}}[\exp(l({\bm{\pi}}_{i},u_{i},\bar{{
\bm{\pi}}}_{i+1}))|{\bm{\pi}}_{i},u_{i},f^{*}]$. By definition, we have:

$$ $\displaystyle\mathbb{E}_{\bar{\tau}_{t}}[\exp(\sum_{i=1}^{t}l({\bm{\pi}}_{i},u _{i},\bar{{\bm{\pi}}}_{i+1}))|\tau_{t}]=\prod_{i=1}^{k}E^{i}.$ $$

Therefore,

$$ $\displaystyle\mathbb{E}_{\tau_{T_{0}}}[\exp(L(\tau_{T_{0}})-\log\mathbb{E}_{ \bar{\tau}_{T_{0}}}[\exp(L(\bar{\tau}_{T_{0}}))|\tau_{T_{0}}])]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{\tau_{T_{0}-1}\cup\{{\bm{\pi}}_{T_{0}},{\bm{u}}_{T_{0 }}\}}[\mathbb{E}_{{\bm{\pi}}_{T_{0}+1}}[\frac{\exp(\sum_{t=1}^{T_{0}}l({\bm{ \pi}}_{t},{\bm{u}}_{t},{\bm{\pi}}_{t+1}))}{\mathbb{E}_{\bar{\tau}_{T_{0}}}[ \exp(\sum_{t=1}^{T_{0}}l({\bm{\pi}}_{t},{\bm{u}}_{t},{\bm{\pi}}_{t+1}))|\tau_{ T_{0}}]}|\tau_{T_{0}-1}\cup\{{\bm{\pi}}_{T_{0}},{\bm{u}}_{T_{0}}\}]]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{\tau_{T_{0}-1}\cup\{{\bm{\pi}}_{T_{0}},{\bm{u}}_{T_{0 }}\}}[\mathbb{E}_{{\bm{\pi}}_{T_{0}+1}}[\frac{\exp(\sum_{t=1}^{T_{0}}l({\bm{ \pi}}_{t},{\bm{u}}_{t},{\bm{\pi}}_{t+1}))}{\prod_{t=1}^{T_{0}}E^{t}}|\tau_{T_{ 0}-1}\cup\{{\bm{\pi}}_{T_{0}},{\bm{u}}_{T_{0}}\}]]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{\tau_{T_{0}-1}\cup\{{\bm{\pi}}_{T_{0}},{\bm{u}}_{T_{0 }}\}}[\frac{\exp(\sum_{t=1}^{T_{0}-1}l({\bm{\pi}}_{t},{\bm{u}}_{t},{\bm{\pi}}_ {t+1}))}{\prod_{t=1}^{T_{0}-1}E^{t}}\cdot\mathbb{E}_{{\bm{\pi}}_{T_{0}+1}}[ \frac{l({\bm{\pi}}_{T_{0}},{\bm{u}}_{T_{0}},{\bm{\pi}}_{T_{0}+1})}{E^{T_{0}}}| \tau_{T_{0}-1}\cup\{{\bm{\pi}}_{T_{0}},{\bm{u}}_{T_{0}}\}]]$ $\displaystyle=$ $\displaystyle\mathbb{E}_{\tau_{T_{0}-1}}[\frac{\exp(\sum_{t=1}^{T_{0}-1}l({\bm {\pi}}_{t},{\bm{u}}_{t},{\bm{\pi}}_{t+1}))}{\prod_{t=1}^{T_{0}-1}E^{t}}]=...=1.$ $$

∎

###### 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 $\psi:\Pi\rightarrow\mathcal{U}$, define $f_{\text{MLE}}\leftarrow\arg\max_{f\in\mathcal{F}}\sum_{t=1}^{T_{0}}\log f({
\bm{\pi}}_{t+1}|{\bm{\pi}}_{t},{\bm{u}}_{t})$, where the trajectory is generated by:

$$ $\displaystyle\forall t\in[T_{0}],\quad{\bm{u}}_{t}\leftarrow\psi({\bm{\pi}}_{t }),~{}{\bm{\pi}}_{t+1}\sim f^{*}(\cdot|{\bm{\pi}}_{t},{\bm{u}}_{t}),$ $$

then, for any $\delta\in(0,1)$, w.p. at least $1-\delta$, we have:

$$ $\displaystyle\sum_{t=1}^{T_{0}}{\mathbb{H}}^{2}(f_{\text{MLE}}(\cdot|{\bm{\pi} }_{t},{\bm{u}}_{t}),f^{*}(\cdot|{\bm{\pi}}_{t},{\bm{u}}_{t}))\leq\log(\frac{| \mathcal{F}|}{\delta}).$ $$

###### Proof.

Given a model $f\in\mathcal{F}$, we consider the loss function:

$$ $\displaystyle l_{M}({\bm{\pi}},u,{\bm{\pi}}^{\prime}):=\begin{cases}\frac{1}{2 }\log\frac{f({\bm{\pi}}^{\prime}|{\bm{\pi}},u)}{f^{*}({\bm{\pi}}^{\prime}|{\bm {\pi}},u)},&\text{if}~{}f^{*}({\bm{\pi}}^{\prime}|{\bm{\pi}},u)\neq 0\\ 0,&\text{otherwise}\end{cases}$ $$

Considering the event $\mathcal{E}$:

$$ $\displaystyle\mathcal{E}:=\{-\log\mathbb{E}_{\bar{\tau}_{T_{0}}}[\exp L_{M}( \bar{\tau}_{T_{0}})|\tau_{T_{0}}]\leq-L_{M}(\tau_{T_{0}})+\log(\frac{|\mathcal {F}|}{\delta}),\quad\forall f\in\mathcal{F}\}.$ $$

where we define $L_{M}(\tau_{T_{0}}):=\sum_{t=1}^{T_{0}}l_{M}({\bm{\pi}}_{t},{\bm{u}}_{t},{\bm{
\pi}}_{t+1})$ and $L_{M}(\bar{\tau}_{T_{0}}):=\sum_{t=1}^{T_{0}}l_{M}({\bm{\pi}}_{t},{\bm{u}}_{t}
,\bar{{\bm{\pi}}}_{t+1})$.
Besides, by applying Lem. E.1 on $l_{M}$ defined above and applying Markov inequality and the union bound over all $f\in\mathcal{F}$, we have $\Pr(\mathcal{E})\geq 1-\delta$.
On the event $\mathcal{E}$, we have:

$$ $\displaystyle-\log\mathbb{E}_{\bar{\tau}_{T_{0}}}[\exp L_{f_{\text{MLE}}}(\bar {\tau}_{T_{0}})|\tau_{T_{0}}]$ $\displaystyle\leq$ $\displaystyle-L_{f_{\text{MLE}}}(\tau_{T_{0}})+\log(\frac{|\mathcal{F}|}{ \delta})$ $\displaystyle\leq$ $\displaystyle l_{\text{MLE}}(f^{*})-l_{\text{MLE}}(f_{\text{MLE}})+\log(\frac{ |\mathcal{F}|}{\delta})$ $\displaystyle\leq$ $\displaystyle\log(\frac{|\mathcal{F}|}{\delta}).$ ( $f_{\text{MLE}}$ maximizes the log-likelihood) $$

Therefore,

$$ $\displaystyle\log(\frac{|\mathcal{F}|}{\delta})\geq$ $\displaystyle-\sum_{t=1}^{T_{0}}\log\mathbb{E}_{{}_{\bar{\tau}_{T_{0}}}}[\sqrt {\frac{f(\bar{{\bm{\pi}}}_{t+1}|{\bm{\pi}}_{t},{\bm{u}}_{t})}{f^{*}(\bar{{\bm{ \pi}}}_{t+1}|{\bm{\pi}}_{t},{\bm{u}}_{t})}}|{\bm{\pi}}_{t},{\bm{u}}_{t},f^{*}]$ $\displaystyle\geq$ $\displaystyle\sum_{t=1}^{T_{0}}1-\mathbb{E}_{\bar{{\bm{\pi}}}_{t+1}}[\sqrt{ \frac{f(\bar{{\bm{\pi}}}_{t+1}|{\bm{\pi}}_{t},{\bm{u}}_{t})}{f^{*}(\bar{{\bm{ \pi}}}_{t+1}|{\bm{\pi}}_{t},{\bm{u}}_{t})}}|{\bm{\pi}}_{t},{\bm{u}}_{t},f^{*}]$ ( $-\log x\geq 1-x$ ) $\displaystyle=$ $\displaystyle\sum_{t=1}^{T_{0}}{\mathbb{H}}^{2}(f(\cdot|{\bm{\pi}}_{t},{\bm{u} }_{t}),f^{*}(\cdot|{\bm{\pi}}_{t},{\bm{u}}_{t})).$ $$

∎

See 4.4

###### Proof.

Consider the steering strategy $\psi({\bm{\pi}})=u_{\bm{\pi}}$.
Given any $f\in\mathcal{F}$, and the trajectory sampled by $\psi$ and $f$, by Lem. E.2, w.p. $1-\frac{\delta}{|\mathcal{F}|}$, we have:

$$ $\displaystyle 2\log(\frac{|\mathcal{F}|}{\delta})\geq\sum_{t=1}^{T_{0}}{ \mathbb{H}}^{2}(f(\cdot|{\bm{\pi}}_{t},{\bm{u}}_{t}),f_{\text{MLE}}(\cdot|{\bm {\pi}}_{t},{\bm{u}}_{t}))\geq T_{0}\zeta.$ $$

By union bound, if $T_{0}=\lceil\frac{4}{\zeta}\log\frac{|\mathcal{F}|}{\delta}\rceil+1$, with probability at least $1-\delta$,

$$ $\displaystyle\max_{f\in\mathcal{F}}\mathbb{E}_{f,\psi}\left[\mathbb{I}[f=f_{ \text{MLE}}]\right]=\max_{f\in\mathcal{F}}\mathbb{E}_{f,\psi}\left[\mathbb{I}[ f=\operatorname*{arg\,max}_{f^{\prime}\in\mathcal{F}}\sum_{t=1}^{T_{\delta}} \log f^{\prime}({\bm{\pi}}_{t+1}|{\bm{\pi}}_{t},{\bm{u}}_{t})]\right]\geq 1-\delta.$ $$

∎

See 4.5

###### Proof.

We denote $\psi_{\text{Explore}}:=\{\psi_{\text{Explore},t}\}_{t\in[T]}$ to be the exploration strategy to identify $f^{*}$.
Given a ${\bm{\pi}}_{\widetilde{T}}$, we denote $\psi_{{\bm{\pi}}_{\widetilde{T}}}^{\varepsilon/2}:=\{\psi_{{\bm{\pi}}_{
\widetilde{T}},t}^{\varepsilon/2}\}_{t\in[T]}\in\Psi^{\varepsilon/2}_{T-
\widetilde{T}}({\bm{\pi}}_{\widetilde{T}})$ to be one of the steering strategy with $\varepsilon$-optimal gap starting from ${\bm{\pi}}_{\widetilde{T}}$.

We consider the history-dependent steering strategy $\psi:=\{\psi_{t}\}_{t\in[T]}$, such that for $t\leq\widetilde{T}$, $\psi_{t}=\psi_{\text{Explore},t}$, and for all $t>\widetilde{T}$, we have $\psi_{t}=\psi_{{\bm{\pi}}_{\widetilde{T}},t}^{\varepsilon/2}$.

As a result, for any $f\in\mathcal{F}$, the final gap would be:

$$ $\displaystyle\Delta_{\psi,T}(f)=\Pr(f_{\text{MLE}}=f)\cdot\frac{\varepsilon}{2 }+\Pr(f_{\text{MLE}}\neq f)\cdot\eta_{\max}\leq\varepsilon,$ $$

which implies $\psi\in\Psi^{\varepsilon}_{T}(\mathcal{F};{\bm{\pi}}_{1})$.
∎

###### Lemma E.1 .

###### Proof.

###### Lemma E.2 .

###### Proof.

###### Proof.

###### Proof.

## Appendix F Generalization to Partial Observation MDP Setup

### F.1 POMDP Basics

##### Partial Observation Markov Decision Process

A (finite-horizon) Partial-Observation Markov Decision Process (with hidden states) can be specified by a tuple $M:=\{\nu_{1},T,\mathcal{X},\mathcal{U},\mathcal{O},{\mathbb{T}},\eta,{\mathbb{
O}}\}$. Here $\nu_{1}$ is the initial state distribution, $L$ is the maximal horizon length, $\mathcal{X}$ is the hidden state space, $\mathcal{U}$ is the action space, $\mathcal{O}$ is the observation space. Besides, ${\mathbb{T}}:\mathcal{X}\times\mathcal{U}\rightarrow\mathcal{X}$ denotes the stationary transition function, ${\mathbb{O}}:\mathcal{X}\rightarrow\Delta(\mathcal{O})$ denotes the stationary emission model, i.e. the probability of some observation conditioning on some state.
We will denote $\mathcal{H}_{h}:=\mathcal{O}_{1}\times\mathcal{U}_{1}...\times\mathcal{O}_{h}$ to be the history space, and use $\tau_{h}:=\{o_{1},u_{1},...,o_{h}\}$ to history observation up to step $h$.
We consider the history dependent policy $\psi:=\{\psi_{1},...,\psi_{H}\}$ with $\psi_{h}:\mathcal{H}_{h}\rightarrow\Delta(\mathcal{U})$.
Starting from the initial state $x_{1}$, the trajectory induced by a policy $\psi$ is generated by:

$$ $\displaystyle\forall h\in[H],\quad o_{h}\sim{\mathbb{O}}(\cdot|x_{h}),\quad u_ {h}\sim\psi_{h}(\cdot|\tau_{h}),\quad\eta_{h}\sim\eta_{h}(o_{h},u_{h}),\quad x _{h+1}\sim{\mathbb{T}}(\cdot|x_{h},u_{h}).$ $$

### F.2 Steering Process as a POMDP

Given a game $G$, we consider the following Markovian agent dynamics:

$$ $\displaystyle\forall t\in[T],\quad\tau_{t}\sim{\bm{\pi}}_{t},\quad{\bm{\pi}}_{ t+1}\sim f(\cdot|{\bm{\pi}}_{t},\tau_{t},r),$ $$

where $\tau_{t}:=\{s_{1}^{t,k},{\bm{a}}_{1}^{t,k},,...,s_{H}^{t,k},{\bm{a}}_{H}^{t,k}
\}_{k=1}^{K}$ is several trajectories generated by the policy ${\bm{\pi}}_{t}$.

In each step $t$, we assume the agents first collect trajectories $\tau_{t}$ with policy ${\bm{\pi}}_{t}$, and then optimize their policies following some update rule $f(\cdot|{\bm{\pi}}_{t},\tau_{t},r)$.
Comparing with the Markovian setup in Sec. 3, here $f$ has additional dependence on the trajectories $\tau_{t}$.

Based on this new formulation, the dynamics given the steering strategy is defined by:

$$ $\displaystyle\forall t\in[T],\quad$ $\displaystyle\tau_{t}\sim{\bm{\pi}}_{t},\quad{\color[rgb]{1,0,0}u_{t}}\sim\psi _{t}(\cdot|\tau_{1},u_{1},...,\tau_{t-1},u_{t-1},{\bm{\pi}}_{t}),\quad{\bm{\pi }}_{t+1}\sim f(\cdot|{\bm{\pi}}_{t},r+{\color[rgb]{1,0,0}u_{t}}),$ $$

In Fig. 4, we illustrate the steering dynamics by Probabilistic Graphical Model (PGM).
Here we treat the joint of ${\bm{\pi}}_{t}$ and $\tau_{t}$ as the hidden state at step $t$, and the trajectory $\tau_{t}$ is the partial observation $o_{t}$ 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 ( $m$ -Decodable POMDP) .

Given a POMDP $M$, we say it is $m$-decodale, if there exists a decoder $\phi$, such that, $x_{h}=\phi(o_{h-m},u_{h-m},...o_{h-1},u_{h-1},o_{h})$,

In our steering setting, if for any $f\in\mathcal{F}$, $f$ is $m$-decodable, we just need to learn a steering strategy $\psi:=(\mathcal{O}\times\mathcal{U})^{m}\times\mathcal{O}\rightarrow\mathcal{U}$, which predicts the steering reward given the past $m$-step history.
This is 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 for the current policy, and use them as input of the steering strategy (see Appx. G.2.2 for more details).

Figure: Figure 4: Probabilistic Graphic Model (PGM) of the POMDP formulation of the steering process. Starting with the initial state $x_{1}:=(\pi_{1},\tau_{1})$, for all $t\geq 1$, the mediator receives observation $o_{t}\sim{\mathbb{O}}(\cdot|x_{t})$ and output the steering reward given the history $u_{t}\sim\psi(\cdot|o_{1},u_{1},...,o_{t})$. The agents then update their policies following the dynamics $f$ and the modified reward function $r+u_{t}$.
Refer to caption: x7.png

###### Definition F.1 ( m 𝑚 m italic_m -Decodable POMDP) .

## Appendix G Missing Experiment Details

### G.1 About Initialization in Evaluation

In some experiments, we will evaluate our steering strategies with multiple different initial policy ${\bm{\pi}}_{1}$, in order to make sure our evaluation results are representative.

Here we explain how we choose the initial policies ${\bm{\pi}}_{1}$. We will focus on games with two actions which is the only case we use this kind of initialization.
For each player, given an integer $i$, we construct an increasing sequence with common difference $\text{Seq}_{i}:=(\frac{1}{2i},\frac{3}{2i},...,\frac{2i-1}{2i})$.
Then, we consider the initial policies ${\bm{\pi}}_{1}$ such that $\pi^{1}(a^{1})=1-\pi^{1}(a^{2})\in\text{Seq}_{i}$, $\pi^{2}(a^{1})=1-\pi^{2}(a^{2})\in\text{Seq}_{i}$.
In this way, we obtain a set of initial policies uniformly distributed in grids with common difference $\frac{1}{i}$.
As a concrete example, the initial points in Fig. 1-(b) marked in color black is generated by the above procedure with $i=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. 1-(b).

##### Choice of η goal superscript 𝜂 goal \eta^{\text{goal}} italic_η start_POSTSUPERSCRIPT goal end_POSTSUPERSCRIPT

We consider the total utility as the goal function. But for the numerical stability, we choose $\eta^{\text{goal}}({\bm{\pi}})=\sum_{n\in[N]}J^{n}_{|{\bm{r}}}({\bm{\pi}})-10$ where we shift the reward via the maximal utility value 10.

##### The Steering Strategy

The steering strategy is a 2-layer MLP with 256 hidden layers and tanh as the activation function.
Given a time step $t$ and the policy ${\bm{\pi}}_{t}:=\{\pi^{1}_{t},\pi^{2}_{t}\}$ with $\pi^{n}_{t}(\texttt{H})+\pi^{n}_{t}(\texttt{G})=1$ for $n\in\{1,2\}$, the input of the steering strategy is

$$ $\displaystyle(\log\sqrt{\frac{\pi^{1}_{t}(\texttt{H})}{\pi^{1}_{t}(\texttt{G}) }},-\log\sqrt{\frac{\pi^{1}_{t}(\texttt{H})}{\pi^{1}_{t}(\texttt{G})}},\log \sqrt{\frac{\pi^{2}_{t}(\texttt{H})}{\pi^{2}_{t}(\texttt{G})}},-\log\sqrt{ \frac{\pi^{2}_{t}(\texttt{H})}{\pi^{2}_{t}(\texttt{G})}},\frac{T-t}{100}).$ (11) $$

Here the first (second) two components correspond to the “dual variable” of the policy $\pi^{1}_{t}(\texttt{H})$ and $\pi^{1}_{t}(\texttt{G})$ ($\pi^{2}_{t}(\texttt{H})$ and $\pi^{2}_{t}(\texttt{G})$), respectively; the last component is the time embedding because our steering strategy is time-dependent.

The steering strategy will output a vector with dimension 4, which corresponds to the steering rewards for two actions of two players.
Note that here the steering reward function $u^{1}:\mathcal{S}\times\mathcal{A}^{1}[0,U_{\max}]$ (for agent 1) and $u^{2}:=\mathcal{S}\times\mathcal{A}^{2}\rightarrow[0,U_{\max}]$ (agent 2) 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^{n}:\mathcal{S}\times\mathcal{A}\rightarrow[0,U_{\max}]~{}\forall n\in[N]$, which is defined on the joint of state space and the entire action space.

##### Training Details

The maximal steering reward $U_{\max}$ is set to be 10, and we choose $\beta=25$.
We use the PPO implementation of StableBaseline3 (Raffin et al.,, ).
The training hyper-parameters 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 we adopt in our experiments is that, we strengthen the learning signal of the goal function by including $\eta^{\text{goal}}({\bm{\pi}}_{t})$ for each step $t\in[T]$. In another word, we actually optimize the following objective function:

$$ $\displaystyle\psi^{*}\leftarrow$ $\displaystyle\arg\max_{\psi\in\Psi}\frac{1}{|\mathcal{F}|}\sum_{f\in\mathcal{F }}\mathbb{E}_{\psi,f}\Big{[}\beta\cdot\eta^{\text{goal}}({\bm{\pi}}_{T+1})+ \sum_{t=1}^{T}\beta\cdot\eta^{\text{goal}}({\bm{\pi}}_{t})-\eta^{\text{cost}}( {\bm{\pi}}_{t},{\bm{u}}_{t})\Big{]}.$ (12) $$

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, we investigate the trade-off between steering gap and the steering cost when choosing different coefficients $\beta$. In general, the larger $\beta$ can result in lower steering gap and higher steering cost.

Figure: Figure 5: Trade-off between Steering Gap (Left) and Steering Cost (Right). (averaged over 5x5 uniformly distributed grids as initializations of ${\bm{\pi}}_{1}$, see Appx. G.1).
Refer to caption: x8.png

#### G.2.2 Experiment Details in Grid-World Version of Stag Hunt Game

We recall the illustration in LHS of Fig. 2.
We consider a 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-left and bottom-right blocks, respectively.

For each time step $h\in[H]$, every agent can take four actions {up,down,left,right} to move to the blocks next to their current blocks.
But if the agent hits the wall after taking the action (e.g. the agent locates at the most right column and takes the action right), it will not move.
As long as one 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.
- •
If 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, it will get reward 0.2 and the other get reward 0.
- •
In other cases, the agents receive reward 0.

We choose $H=16$. The best strategy is that all the agents move together towards the block with Stag, so within one episode, the agents can reach the Stag 16 / 2 = 8 times, and the maximal total return would be 8 * 0.25 = 4.0.

In the following, we 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.,, ).

##### Agents Learning Dynamics

The agents will receive a 3x3x4 image encoding the position of all objects to make the decision.
The agents adopt a 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 each steering iteration $t$, we ask the agents to 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 8-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 more concrete, the 8 rewards correspond to the additional reward for blue and red agents for the following 4 scenarios: (1) both agents reach stag together (2) 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.

The steering strategy is also trained by PPO.
We choose $\beta=25$ and learning rate 0.001.
We consider the total utility as the goal function, and we adopt the similar empirical trick as the normal-form version, where we include $\eta^{\text{goal}}$ into the reward function for every $t\in[T]$ (Eq. (12)).
The results in Fig. 2 is the average of 5 steering strategies trained by different seeds for 80 iterations.
The two-sigma error bar is shown.

#### G.2.3 Experiments in Matching Pennies

Matching Pennies is a two-player zero-sum game with two actions H=Head and T=Tail and its payoff matrix is presented in Table 2.

**Table 2: Payoff Matrix of Two-Player Game Matching Pennies. Two actions H and T stand for Head and Tail, respectively.**
|  | H | T |
| --- | --- | --- |
| H | (1, -1) | (-1, 1) |
| T | (-1, 1) | (1, -1) |

##### Choice of η goal superscript 𝜂 goal \eta^{\text{goal}} italic_η start_POSTSUPERSCRIPT goal end_POSTSUPERSCRIPT

In this game, the unique Nash Equilibrium is the uniform policy ${\bm{\pi}}^{\text{NE}}$ with $\pi^{n,\text{NE}}(\texttt{H})=\pi^{n,\text{NE}}(\texttt{T})=\frac{1}{2}$ for all $n\in\{1,2\}$.
We consider the distance with ${\bm{\pi}}^{\text{NE}}$ as the goal function, i.e. $\eta^{\text{goal}}=-\|{\bm{\pi}}-{\bm{\pi}}^{\text{NE}}\|_{2}$.

##### Experiment Setups

We follow the same steering strategy and training setups for Stag Hunt Game in Appx. G.2.1.
The agents follow NPG to update the policies with learning rate $\alpha=10$.

##### Experiment Results

As shown in Fig. 6-(a), we can observe the cycling behavior without steering guidance (Akin and Losert,, ; Mertikopoulos et al.,, ).
In contrast, our learned steering strategy can successfully guide the agents towards the desired Nash.
In Fig. 6-(b), we also report the trade-off between steering gap and steering cost with different choice of $\beta$.

Figure: (a) Dynamics of Agents Policies.
Refer to caption: x10.png

### G.3 Experiments for Unknown Model Setting

#### G.3.1 Details for Experiments with Small Model Set ℱ ℱ \mathcal{F} caligraphic_F

The results in Table 1 is averaged over 5 seeds and the error bars show 95% confidence intervals.

##### Training Details for ψ 0.7 ∗ superscript subscript 𝜓 0.7 \psi_{0.7}^{*} italic_ψ start_POSTSUBSCRIPT 0.7 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT and ψ 1.0 ∗ superscript subscript 𝜓 1.0 \psi_{1.0}^{*} italic_ψ start_POSTSUBSCRIPT 1.0 end_POSTSUBSCRIPT start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT

The training of $\psi_{0.7}^{*}$ and $\psi_{1.0}^{*}$ follow the similar experiment setup as Appx. G.2.2, except here the agents adopt random learning rates.
For the choice of $\beta$, we train the optimal steering strategy with $\beta\in\{10,20,30,40,50,60,70,80,90,100\}$ for both $f_{0.7}$ and $f_{1.0}$, and choose the minimal $\beta$ such that the resulting steering strategy can achieve almost 100% accuracy (i.e. $\Delta_{\psi,f}\leq\varepsilon$ for almost all 5x5 uniformly distributed initial policies generated by process in Appx. G.1).
As we reported in the main text, we obtain $\beta=70$ for $f_{0.7}$ and $\beta=20$ for $f_{1.0}$.

##### Training Details for ψ Belief ∗ subscript superscript 𝜓 Belief \psi^{*}_{\text{Belief}} italic_ψ start_POSTSUPERSCRIPT ∗ end_POSTSUPERSCRIPT start_POSTSUBSCRIPT Belief end_POSTSUBSCRIPT

For the training of $\psi_{\text{Belief}}^{*}$, the input of the steering strategy is the original state (Eq. (11)) appended by the belief state of the model.
In each steering step $t\in[T]$, we assume the mediator can observe a learning rate sample $\alpha$, and use it to update the model belief state correspondingly.
The regularization coefficient $\beta$ for the training of $\psi_{\text{Belief}}$ is set to be the expected regularization coefficient over the belief state $\beta=b(f_{0.7})\cdot 70+b(f_{1.0})\cdot 20$.
In 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.
$\psi_{\text{Belief}}^{*}$ is trained the PPO algorithm.

During the training of $\psi^{*}_{\text{Belief}}$, we find that the train is not very stable, possibly because the chosen $\beta$ for two models are quite different.
Therefore, we keep tracking the steering gap of the steering strategy during the training and save the model as long as it outperforms the previous ones in steering gap.
Our final evaluation is based on that model.

#### G.3.2 Details for Experiments with Large Model Set ℱ ℱ \mathcal{F} caligraphic_F

We set $U_{\max}=1.0$, and the random exploration strategy (red curve in the left sub-plot in Fig. 3) will sample the steering reward uniformly from the interval $[0,U_{\max}]$.
We use the PPO (Raffin et al.,, ) to train of exploration policy and also the steering strategy given hidden model.
To amplify the exploration challenge, we set $\beta^{n}=1$ when $\pi^{n}(\texttt{A})\leq 0.5$ and increase to $\beta^{n}=10$ when $\pi^{n}(\texttt{A})\leq 0.5$.
As a result, if the mediator follows first-explore-then-exploit 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 $\mathbb{I}[f=f_{\text{MLE}}]$ in Proc. 2 is supported by theory, it contains much less information than the posterior probability $[\Pr(f|{\bm{\pi}}_{1},u_{1},...,{\bm{\pi}}_{T},u_{T},{\bm{\pi}}_{T+1})]_{f\in
\mathcal{F}}$.
Therefore, empirically, we instead train a history-independent steering strategy to maximize the posterior probability of $f$:

$$ $\displaystyle\psi^{\text{Explore}}\leftarrow\arg\max_{\psi}\frac{1}{|\mathcal{ F}|}\sum_{f\in\mathcal{F}}\mathbb{E}_{\psi,f}[\sum_{n\in[N]}\Pr(\lambda^{n}|{ \bm{\pi}}_{1},u_{1},...,{\bm{\pi}}_{\widetilde{T}},u_{\widetilde{T}}{\bm{\pi}} _{\widetilde{T}+1})].$ (13) $$

Here we use the sum of posteriors of $\lambda^{n}$s since the $\lambda^{n}$s are independent for all $n\in[N]$.
We observe it results in better performance, and it is doable by keep tracking the model belief state of each agent.
Besides, similar to Stag Hunt games, we observe that using the posterior $\Pr(\lambda^{n}|{\bm{\pi}}_{1},u_{1},...,{\bm{\pi}}_{t},u_{t},{\bm{\pi}}_{t+1})$ as rewards in the non-terminal steps $t<T$ increase the performance, and we use the same trick (Eq. (12)).

To plot the results in the middle and right sub-plots in Fig. 3, for each model $f^{*}\in\{f_{1},f_{2},f_{3}\}$, we train three steering strategies (with the same state design in Eq. (11)). The first one is the oracle strategy, which starts with ${\bm{\pi}}_{1}$ and steering for $T=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 $\widetilde{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 is the same as FETE except we just use random policy as the exploration policy, and estimate the model by interaction samples generated by that.
During the evaluation, for FETE and FETE-RE, we 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 of the Consistency of the Adaption

We first want to highlight it is not easy to have an apples-to-apples comparison with (Canyakmaz et al.,, ).
First, because the experiment setting in (Canyakmaz et al.,, ) does not present significant exploration challenges, we design and decide to evaluate both methods in the “avaricious agents” setting (Fig. 3).
Second, SIAR-MPC 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 SIAR-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 to 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 (Canyakmaz et al.,, ) is the impact of different exploration strategies on the final steering gap and steering costs.
This is 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.,, ) in terms of both the model estimation strategy and exploitation strategy. The main distinction and improvement of our FETE compared with (Canyakmaz et al.,, ) is our strategic exploration strategy.

### G.5 A Summary of the Compute Resources by Experiments in this Paper

##### Experiments on Two-Player Normal-Form Games

For the experiments in ‘Stag Hunt’ and ‘Matching Pennies’ (illustrated in Fig. 1, 5, 6), we only use CPUs (AMD EPYC 7742 64-Core Processor). It takes less than 5 hours to finish the training.

##### 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 𝑁 N italic_N -Player Normal-Form Cooperative Games

For the experiments in cooperative games (illustrated in Fig. 3), we only use CPUs (AMD EPYC 7742 64-Core Processor).
It takes less than 10 hours to finish the training.

## Appendix H Discussion on Limitations and Societal Impact

##### Discussion on Limitations

The main limitation of this paper is that we only focus on Markovian agents, whose dynamics $f$ only depends on their current policy profiles and the (modified) reward function.
Although this model can already capture lots of learning dynamics, not all the theoretical results and methodology can be generalized to non-Markovian settings.

Besides, we can not guarantee how the optimal steering strategy regarding our Objective (1) performs in terms of the steering cost. We leave it to the future works.

Moreover, for the large model class setting, the strategy obtained by running proposed FETE framework may not have guarantees on the steering cost.
It is also unclear if there are better algorithm designs for this setting.

##### Discussion on Societal Impact

Although this work are not directly applicable to real-world applications, but we believe it may have positive societal impact.
The steering problem we study matches the requirement of many real-world scenarios (e.g. the social planner may incentivize technology companies by individual financial subsidies).
We believe the theoretical and algorithmic contributions in this paper can provide useful insights for those applications.

## Peer Reviews

confidence: 3
contribution: 2
initial_rating: 5
presentation: 3
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.

- 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.
soundness: 3
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.

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

- The paper is well-written and very easy to follow, with justification and explanation whenever needed in most places.
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.
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:

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

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

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 1
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?
2. 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?
3. 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?
4. Why steering is necessary in multi-agent systems? Can existing algorithms find the equilibrium or approximated equilibrium for MAS?
soundness: 3
strengths: Strengths:

1. The authors introduce a new objective function that balances the goal of steering agents toward a target policy while minimizing the overall steering cost.
2. 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.
3. The paper includes experimental results in different environments, demonstrating the algorithms' performance under varying model uncertainty conditions.
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.
weaknesses: Weakness:

1. 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.
2. 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.

---

confidence: 4
contribution: 3
initial_rating: 8
presentation: 3
questions: 1. What will happen if the model set $\mathcal{F}$ is uncountably infinite?

2. What will happen for a non-tabular MDP setup?
soundness: 3
strengths: *Conceptual Novelty and Relevance*: The paper introduces an approach to steering agents by focusing on Markovian agents with limited cognitive resources.

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

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

Meta-review: This paper presents a framework for steering Markovian agents in multi-agent systems using reinforcement learning under model uncertainty, with strong theoretical guarantees and empirical validations. Despite some concerns about scalability to more complex and realistic settings, the work is conceptually novel. It provides a solid foundation for advancing research in this area.

Decision: Accept (Poster)