MERMADE: $K$-shot Robust Adaptive Mechanism Design via Model-Based Meta-Learning
Authors: Arundhati Banerjee
Soham Rajesh Phade
Stefano Ermon
Stephan Zheng
Venue: Submitted to ICLR 2023 (2023)
Keywords: Mechanism design
Robustness
Meta-learning
Adaptive agents
Simulation based learning

Abstract: Mechanism design (MD) studies how rules and rewards shape the behavior of intelligent agents, e.g., in auctions or the economy. Simulations with AI agents are powerful tools for MD, but real-world agents may behave and learn differently than simulated agents under a given mechanism. Also, the mechanism designer may not fully observe an agent's learning strategy or rewards, and executing a mechanism may be costly, e.g., enforcing a tax might require extra labor. Hence, it is key to design robust adaptive mechanisms that generalize well to agents  with unseen (learning) behavior, are few-shot adaptable, and are cost-efficient. Here, we introduce MERMADE, a model-based meta-learning framework to learn mechanisms that can quickly adapt when facing out-of-distribution agents with different learning strategies and reward functions. First, we show that meta-learning allows adapting to the theoretically known and appropriate Stackelberg equilibrium in a simple matrix game at meta-test time, with few interactions with the agent. Second, with bandit agents, we show empirically that our approach yields strong meta-test time performance against agents with various unseen explore-exploit behaviors. Finally, we outperform baselines that separately use either meta-learning or agent behavior modeling to learn a cost-effective mechanism that is $K$-shot adaptable with only partial information about the agents.

Under review as a conference paper at ICLR 2023
MERMAIDE: LEARNING TO ALIGN LEARNERS US- ING MODEL-BANE META-LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
Designing mechanisms like auctions or taxation policies can be formulated as a general-sum game between principal and self-interested learning agent. The principal aims to induce desirable outcomes in such games and may do so, for example, by dynamically intervening on the agent's learning objective. The inter- vention policy should generalize well to agents with unseen learning behaviors; in the real world, the principal may not know the agent's learning algorithm nor its rewards. Moreover, interventions may be costly, e.g., enforcing tax might require extra labor; hence, interventions should be few-shot adaptable (only needs to retrain on few agents at test-time) and cost-efficient (uses few interventions). Here, we introduce a model-based meta-learning framework to train principal that can quickly adapt when facing out-of-distribution agents with different learn- ing strategies and reward functions. First, in a simple Stackelberg game between the principal and greedy agent, show that meta-learning allows adapting to the theoretically known and appropriate Stackelberg equilibrium at meta-test time, with few interactions with the agent. Second, we show empirically that our approach yields strong meta-test time performance against bandit agents with var- ious unseen explore-cxploit behaviors. Finally, we outperform basclines that sepa- rately use either neta-learning or agent behavior modeling to learn a cost-effective intervention policy that is K-shot adaptable with only partial agent information.
INTRODUCTION
General-sum games provide framework to study diverse applications involving a principal that aims to incentivize an adaptive agent (both are learners) to achieve the principal's goal, e.g., maxi- mizing revenue in auctions (Milgrom & Milgrom 2004), optimizing social welfare with economic policy (Zheng et al., 2022), or optimizing skill acquisition in personalized education (Maghsudi et al. 2021). In this work, we focus principal that directly intervenes agent. For instance, a government may want to incentivize the use of anvironmentally-frieee ("clean") products by levying green taxes, but needs understand how people (strategically) change their consumption behavior as taxes change. Here, existing models of human adaptation that assume rational learning (or use simplified models of bounded rationality) often do not suffice. Hence, teracting with the agents is required to learn (how they change) their behavior, but such interactions are not "free". For example, tax policy may require effort to apply it fairly and to measure its impact on consumers.
the rewards of the
To mitigate the need for costly real-world interactions, we can use simulations with deep reinforce- ment learning (RL) agents. This is attractive solution framework: deep neural network behavioral models are expressive enough emulate real-world entities and simulations can run safely and as often as needed. Morcover, even in the face of complex agent behaviors in sequential general-sum games.
use deep RL to learn intervention policies that are effective
However, this approach also faces several challenges. When deploying the learned policies in the real world, interventions can typically only be applied a few times, due to implementation costs, and rarely under identical cireumstances; in contrast to simulations, though principals may adapt their policies to new conditions, they cannot realistically know the true rewards or learning strategy of the agent. Hence, our goal is to learn policies in general-sum games
cannot reset the real world. Even

---

Under review as a conference paper at ICLR 2023
that 1) perform well even when agents learn, 2) can be quickly adapted, 3) are robust distribution shifts in agent behaviors, and 4) are effective despite having only partial information.
Contributions. To address these challenges, we propose MERMAIDE (Meta-learning for Model- based Adaptive Incentive Design), deep RL approach that 1) learns a world model and 2) uses gradient-based meta-learning to learn a principal policy that can be quickly adapted to perform well on unseen test agents. We consider two-player general-sum games between a principal and an agent wherein the principal intervenes at cost on the agent's 's learning process to incentivize the agents to learn to act to achieve the principal's 's objective. We assume that the agent behaves in a first-order strategic manner and the principal in a second-order strategic manner. Here, the agents optimize their experienced rewards and minimize their regret, but do not account for their influence on the principal's 's actions. In contrast, the principal intervenes explicitly as to influence the agent's 's actions.
We first analyze the one-shot adaptation performance of a meta-learned principal in matrix game setting, under both perfect and noisy observations for the agent and the principal. We show that meta-trainin tett-ttrinnin reliably finds solutions that one-shot adapt well, and characterize how the principal's dittr--dittrittiion performance depends on its observable information about the agent.
We next develop and empirically verify these insights with more adaptive agents and propose MER- MAIDE which finds well- sell-performing reward intervention policies in the sequential bandit setting. Here, MERMAIDE performs well against out-of-distribution bandit learners, with test-time perfor- mance and robustness depending on the agents' level of exploration and their pessimism in the face of uncertainty, con confirming and extending the analysis and conclusions from the single-round setting.
RELATED WORK
Bilevel optimization. Learning a mechanism with agents who also learn bilevel optimiza- tion problem, which is NP-hard (Ben-Ayed & Blair 1990; Sinha et al., 2017). Possible solution techniques include branch-and-boun ing bilevel optimization using joint learning of the mechanism and the agents can be unstable, as the agents continuously adapt their behavior to changes in the mechanism. This can be stabilized using curriculum learning (Zheng et al., 2020), but generally bilevel problems remain challenging, especially with nonlinear objectives or constraints.
and trust regions (Colson et al. 2007). In particular, solv-
Meta-learning and distribution shift. In recent years, gradient-based meta-learning has proven effective in learning initializations for complex policy models that generalize well to unseen tasks (Finn et al. 2017a Nagabandi et al. 2018). Luketina et al. (2022) showed that context-conditione veea--gaddeens are effective for adapting in environments with controlled sources of non-stationarity. but they do not account for non-stationarity from interactions between strategic agents that learn. Prior works imitation learning (Argall et al.) 2009) and inverse RL (Abbeel & Ng 2004) as- sume access to expert demonstrations with fixed policy that the (RL) agent wants to emulate. In contrast, our principal aims to learn a policy that can strategically alter the behavior of such demon- strators (our agents), who are themselves learning during episode of the demonstration. Recently, Boutilier et al. (2020) studied meta-learning for bandit policies, while Guo et al. (202I) introduced the inverse bandit setup for learning from low-regret demonstrators. However, these works do not consider shifts in the bandit learning algorithm between training and test time.
Modeling agents. A key challenge in multi-agent learning is that each agent experiences a non- stationary environment if other agents are learning. As such, agents can benefit from having world model, e.g., to know what the policy or value function of the other agents are. World models can stabilize multi-agent RL (Lowe et al. 2017) and enable higher-order learning methods (Foerster) et al., 2018). and can be seen as a form of model-based RL. However, this may require a large amount of observational data or prior knowledge, which may be hard acquire
Adaptive incentive design. Principal-Agent problems (Eisenhardt, 1989) involve design of in- centive structures, often under information asymmetry, but are usually not concerned with learning how to learn to incentivize across agents of different types. Pardoe et al. (2006) found that a form of meta-learning that adapts the learning process itself can design English auctions (sequential bidding)
2

---

Under review as a conference paper at ICLR 2023
that perform better with adaptive bidders who are avesee,, and is still effective when the distri- bution of bidder behaviors (slowly) shifts. Our work expands on this theme by explicitly modeling agents that learn, considering shifts in the learning algorithm of the agents, and using deep RL with gradient-based meta-learning. The combination of these techniques enable learning incentivization policies that generalize well across more complex tasks.
LEARNING TO ALIGN AGENTS BY REWARD INCENTIVIZATION
Overview. We model principal who aims to incentivize agent (learn to) execute the prin- cipal's preferred action. To do so, the principal can intervene and change the agent's 's rewards at a cost. Without interventions, the agent may learn prefer action different than the principal's.
For example, consider consumers who can use either environmentally "clean" or "dirty" goods. Indifferent first, consumers may gradually learn prefer dirty goods if those are consistently cheaper than clean ones, whereas the government may want them to prefer clean goods. Here, the agent's 's reward is the negative of the cost of consumption, for instance, and an intervention changes the price of goods through taxes or subsidies. If we have access to simulation, the principal can compute an optimal intervention. However, the simulation might be inaccurate and real-world agents might behave differently. As an example of such test-time distribution shift, simulated agents may be fast to change their consumption preferences, while real agents may be slow. A "good" principal (trained in simulation) could quickly be fine-tuned to intervene more in the latter case and adapt quickly if such behavior observed during deployment.
In particular, we focus on learning principal policy that needs to be adapted quickly following single round of test-time game play (e.g., taxes and subsidies are deployed in the real world), and that is effective when the agent's 's learning algorithm differs from that seen during train-time
We now formalize this setting. this work, we focus on agents in a stateless environment for ease of exposition. For all variables and their meaning, see Tables 2 and in the Appendix.
The agent. The agents are characterized by their action space A and a base reward function r A R. We call it the base reward because the agent experiences an intervened reward
Rg (at) = r (a.) + + (a:),
(1)
where the intervention r is provided externally (by the principal) for the agent action ae. We index time as f. = ,,...,7 T. At each time step f, the agent's 's policy म, computes a distribution over its actions based the observations for the agent up timestep and executes d₂ we- We assume that the principal has preferred action a* that the agent should execute, whereas the agent's 's optimal policy can prefer a different action than a" without intervention. Finally, time t, the agent learns using an update rule f : (Te, dz, Fz) + Te+1 to maximize the agent's intervened rewards, e.g., under UCB (Lai et al. 1985). f updates the confidence bounds for the action selected at time t.
The principal. In this work, from the principal's point of view, the world (environment) consists of the agent who maximizes F. A standard assumption is that agents are rational and they may have private state (referred to as its type) which the principal cannot see. Although the agent faces stateless problem, the principal faces a stateful problem with partial observability. The full state S includes the principal's 's internal state hy (e.g., the principal's 's belief about the value of the private agent information). and all information about the agent, including its past actions, reward function, and policy model; often, the latter are private.
More formally, the principal can be modeled as a POMDP (S, OS, "o",," AP, 7; P). The observation function o" determines what part of world state is visible to the principal, AP is its action space of interventions, r" is its reward, is discounting factor, and P are the environment dynamics, c.g., as caused by the agent's 's actions. At time i, the principal samples an action af 7 (af h
which determines its intervention on each possible agent action a, i.e. a. rr...... .
Adaptive intervention policy learning To model distribution shift at test time, we follow the meta-learning terminology (Finn et al. (017b) and view each distinct agent as a task 7'. The princi- pal has access to meta-train set of agents 7" E Tiain 1, ..... Prrain and is evaluated on mela-fest
3

---

Under review as a conference paper at ICLR 2023
set of agents 7¹ E Tessi ,..... Phest- We emphasize that during task, both the principal and agent may learn and adapt, both at meta-train and meta-test time.
Here, focus two key challenges: K K-shot adaptation and distribution shift. First, the principal gets only K cpisodes for fine-tuning for each meta-test task (but can train indefinitely for each meta- train task). Second, the principal faces two types of distribution shift: 1) across tasks and 2) intra- task non-stationarity. The meta-train and meta-test tasks may differ (significantly) in their temporal distribution of actions, e.g., due different agent updates f or the agent rewards 7r being centered around different values (e.g.. average price levels are higher in the real world vs in the simulation). Within a task, the agent's 's learning affected by the principal's interventions that change its reward ñ. This gives rise to non-stationarity in the agent's 's environment, as its learning objective may shift over time. These forms of distribution shift distinguish our adaptive intervention policy learning setting from most prior work in meta-learning, which often assume stationarity within task and also assume similar task distributions meta-train and meta-test times.
The principal's objective is to maximize how often meta-test time agents choose a' during learning and have them converge to policy that always chooses a", To do the principal aims to maximize the cost-adjusted test-time return Pest (TT X²) = ET... Einn" - ac))
Objectives.
where the agent executes its (optimal) policy xr [x*) in response to nP:
T Σ
Ex-10r (r? 108--ca)) -
arg max maxEx ET Eny E [sT9]
-0
a >>00 0,
(2)
where the principal incurs a cost if intervenes. A simple cost function is 1 (r/ / 0J. i... the cost constant across non-trivial interventions, where a >> 0 is constant, Note that if intervention were free (c, 0), trivial solution is to always add large r' (a*) >> 0 for its preferred action a", such that it always yields the highest reward. Hence, we focus on learning non-trivial strategies when intervention is costly, which forces the principal strategically alter the agent's learning behavior.
During an episode of T time steps, each agent í starts with a uniformly initialized action probability distribution m. and optimizes zद subject interventions Tº to maximize its return:
Eg DT Pt (a), a.) Here, assume that T and y are sufficiently large so the agent con- verges to its optimal policy under F, using its learning algorithm f. That is, we assume that the objective in EEq. (2) sufficient describe the principal's objective of ensuring the agent converges to preferring a" at some & < T.
In the K-shot adaptation setting, at meta-test time, the principal gets K episodes interact with any agent, each episode of length T steps. The principal has fixed policy during an episode and it can update its policy at the end of an episode. The agent reset across episodes, and within each episode, the agent follows its own learning strategy in response to the principal' 's interventions. On the K + th episode, the principal evaluates its K-shot adapted policy on the agent. Note this assumes that the principal has separate copy of the meta-test time agent for evaluation.
ANALYSIS IN THE MATRIX GAME SETTING
We first study robust adaptive intervention policy learning with strategic agents using a simple 2- player game between a principal and agent. The agent's actions are "cooperate" and "defect", while the principal can choose whether or not to intervene. Assuming the row player is the agent and the column player is the principal, the 2 x 2 payoff matrix is given by
No intervention
Intervene + ++1,1
Cooperate Defect
(
1 11u,00 u. 0
- U, - 9
where u E (0, 1) and ci the cost of intervention (c 1). The principal prefers cooperation: it gets the agent cooperates and if the agent defects (minus the cost it intervenes). The agent's 's base payoff is its type. Notice that an intervention incentivizes the agent cooperate (u > uu)
4

---

Under review as a conference paper at ICLR 2023
3.
U+0.93
Intoyyenoonn grobability
Um0
intevventon geobaoliity 200
U=0007
Rune robel
MoNure rotul
MoNowwhh rateed
MinLirs neirat Moliin notes
WAHLITS robal
MAMLIwt notrs
0.6g
Trininn spects
Thaining spacis
Thiining spociss
(c)
Figure/ 1: Single round game. REINFORCE (RL) does not adapt to expected Stackelberg equilib-
rium during evaluation. MAML's adaptability suffers under observation noise.
It is natural to consider the Stackelberg setting where the principal is the leader and acts first (inter- not), and the agent acts second (Von Stackelberg. 201O). Our goal is to learn intervention policy that can adapt to different agent types and find the Stackelberg equilibrium. We now analyze three scenarios with increasing difficulty:
1. First, we assume that the principal knows u. Here, there a unique Stackelberg equilibrium at (Cooperate, No Intervention) when u 2 and at (Cooperate, Intervene) when u < 2'
2. Second, the principal can observe noisy version of u. In both these cases. the agent first observes the principal's 's action and plays the best response according to its payoff matrix.
3. Finally, we consider a repeated multi-stage game where the agent cannot observe the princi- pal's 's action. Instead, we assume that the agent keeps a running average for the experienced payoffs for each of its actions. cipal committing to mixed action and then the agent choosing its best response. When u 2 1.4 the Stackelberg equilibrium occurs at (Cooperate, No Intervention). When u < 1. at the Stackelberg equilibrium for this game the principal has a mixed action where it chooses to intervene for 20-1 fraction of times and the agent chooses to always cooperate.
single-round setting this would correspond to the prin-
2
Given this equilibrium analysis, we learn a neural network policy for the principal that predicts its probability of intervention and compare the behavior of the learned policy when trained using standard policy gradients (RL) versus meta-learning (MAML, (Finn et al. 20175)). We set = 0.75.
With perfect observability. Here, we study whether meta-learning finds better initialization Ometta for adaptation on unseen agents. In this setting, we assume that the principal observes an agent's 's exact payoff parameter It learns stochastic policy n. (u) which determines its probability of intervening in a single-rount game with an agent type u. Given a set of training agents with different types u ~ U (0, 1). for each u, the principal learns the optimal policy parameters 0" (u) arg max9 (ar-=y(()) [rP (aP)), where rp (a²) is the principal's payoff for action a² with agent u.
The planner then learns meta using the meta-learning algorithm in inAppennix B and one-shot adapts on a meta-test set of agents with different us than training. Note that we're studying the quality of the initialization, not the generalization performance of an already trained policy. Fig. I shows the principal's 's meta-test time probability of intervening with different agents from the test set, across training epochs. The principal and agent should be at different Stackelberg equilibria depending on the type u, as discussed above. We see that principal trained from scratch on the test agents using standard policy gradients is unable to adapt to different agents in a single-shot adaptation setting. In contrast, with meta-learning, the principal learns a better policy that is one-shot adaptable to agents of different types and converges to the correct Stackelberg equilibrium at meta-test time.
With noisy observations for the principal. Here, we emulate a principal with partial observabil- ity of the agent, by letting the principal observe with added i.i.d. Gaussian noise. The agent can see all payoffs and chooses the best response to achieve a Stackelberg equilibrium. Fig. shows that with noisy observations, the meta-learned principal policy requires more training time to be one-shot adaptable to the optimal intervention policy. This empirically indicates the increased difficulty of learning adaptive intervention policy due to incomplete information about the agent, especially under limited adaptation time with unseen agents. It therefore motivates us to adopt a model-basee approach for the principal better estimate the agent type and learn adaptive intervention policy.
5

---

Under review as a conference paper at ICLR 2023
Sire hook
Number of Intevvnttnn
MAPL
Number
200
1st PC: 19.01
Training spachs
Training spocts
(a)
(h)
(c)
Figure 2: Multi-round game. (a) Principal's optimization trajectory in the expected payoff land- scape during training. Axes PCA directions in the policy parameter space. (b)(c) MAMI adapts
(single shot) to Stackelberg equilibrium with best response agent in a simplified form MD.
[+1
Intervention policy
N
θ
Psos
6
World model
Af
14
M
de
of
Figure 3: Overview of MERMAIDE. Left: Flow of principal and agent observables, rewards, and actions. Right: The principal's world model and intervention policy. Also see Algorithm T
Comparing Fig. and Fig. lc we also see that when < J. the difference in unintervened payoffs between the principal's 's preferred action (u) and the agent's preferred action - u) also impacts the one-shot adaptability of the principal receiving noisy observations. This observation informs our analysis of the bandit setting in Section
Multi-round repeated game with noisy rewards. In this setting, the principal and agent repeat- edly play an iterated game over T 100 steps. In each round, the principal observes the agent's type u with added i.i.d. Gaussian noise. The agent cannot observe the principal's 's actions, and plays best response for its current estimate of the action payoffs. Whenever the agent selects tion, it receives a noisy observation of the true payoff and updates its estimate. Compared to the single-round setting, here the agent's best response behavior may change across rounds in the game depending on its observed payoff', giving rise to non-stationarity in the principal's environment. The plamner, turn, has to learn intervene that the agent's 's best response is cooperate.
Fig. 2a compares the optimization trajectory followed using 1) standard policy gradients and 2) meta-learning for the principal. Starting from the same initialization, the meta-lcarned policy's parameters lie in region of the payoff landscape with a higher expected value over the training agents. Moreover, FFg.. 2bjandFFi.. 2c|show the one-shot adaptability of the principal's policy for two different agent types at meta-test time. Meta-learning helps learn better intervention strategy that robust to the principal's 's observation noise as well as the agent's 's evolving best response strategy.
5 MERMAIDE: LEARNING TO ALIGN LEARNERS
Motivated by findings from Section 4 now present MERMAIDE Fig. 3 consisting of:

---

Under review as a conference paper at ICLR 2023
Algorithm 1 MERMAIDE (Notations also in Table 3)
Initialize principal (0g. wg), and hidden states hj. hg.
2:
for meta-train epoch e = L..... Euain do
3: Update world model parameters w = we using lq.. (4)
4: for agents (tasks) = =1,.... ..... Mrrain do
5: Initialize agent: (u², T.). task specific principal policy parameter (7h) = -c. > Inner loop for K episodes. & For each episode with T principal-agen interactions
6: for k = ., miin do
7:
for time t= ... T ; do Predict a; = arg max,; Ae (ajla)_,,,f h4-1) using the world model.
8:
9:
Intervention: f = n² + af, of ~ T (((=)) 11 ai (,,.
Agent acts: af ~ क. and receives reward ri N (f², T/ + M|+1-
11:
Locally update 0 (Tk) + 0 (Ti+1).
Using REINFORCE.
12:
for t= 1,...... T do
b Rollout for meta-update; Dment (r') =
13:
Predict aj = arg a th (a/la)- af1 h/11) using the world model.
Intervention: jr = μ¹ af. of xp o (Thm
(a (o]la/_1, oi_ ai, h2-1).
15:
Agent acts: ot Tí, receives reward rf N (it,0²) Updates πद + π441-
16:
Collect Dmsta (7') U o of Th
17:
Meta-update 0g + 0e+1 using Dinct U, D Deeea (7*).
> Using MAML.
recurrent world model parameterized by that outputs distribution over agent i's actions at the next time step I: f. [a]lat-1r a"-1, k(-1). conditioned on the planner's ' in- tervention and the observed agent action at - 1. h2-1 is the hidden world model state.
a recurrent intervention policy which outputs a distribution over interventions its previous intervention, the
a" z0 [a]aaa-;;"" "f,, at, h2 h(-1), conditioned observed agent action and the world model's predicted next agent action af max, th
h)-1). he_, is the hidden state of the policy network.
We train this using gradient- based meta-learning and RL, see Algorithm maximizes the meta-train objective Ji similar to the objective in Eq. (2) The base RL algorithm is REINFORCE (Williams) 1992) and the meta-learning update uses MAMI. (Finn et al. 201 7b).
Here, the principal
The agent optimizes its cumulative intervened reward, see (Section 6) for details. The world model
fw trains by maximizing the log- ligliikeldoood of the observed a,, using Adam (Kingma & Ba 2014):
arg max ENPAEP Eatro PorT
Σ log t. (aglai-1, (
Note that the principal's parameters O are updated after each T T-step episode, while the agent contin- uously learns during each episode. Also, the agent reset between episodes. At time 0, the world model makes prediction based on zero initialization. We use single world model for all agents. At meta-test time, only the intervention policy is updated by one-shot adaptation to a new agent.
EXPERIMENTAL VALIDATION IN THE BANDIT SETTING
We now study a sequential general-sum game between the principal and an adaptive no-regret learner agent, modeled by an IAl-armed bandit instance with action set A having base reward r = [rI...., [ri....,[A]]] At each time step t. the agent chooses an arm a and gets a reward sampled from N (ra, We assume ra E (0, Va. The agent aims to maximize its cumulative reward over a horizon of T steps. The agent can only observe the reward for the chosen action, and hence faces explore-exploit dilemma addressed by bandit algorithms like UCB (Lai et al. 1985). We assume there unique arm à with the highest base reward: à arg max, Fas L.C., the agent's preferred action without any intervention.
7

---

Under review as a conference paper at ICLR 2023
Costly interventions. To analyze the effect of the cost of intervention C the principal's learnt policy, we assume that the principal decides among three different intervention levels Ir'l e {0, 0.5, 1} such that C Ir'|- Across different bandit agent tasks r' with distinct base rewards r' and reward gaps 5 = m r [a] r r'(a"), the principal should learn to appropriately incentivize the agent while minimizing the total cost of intervening. We then define the experienced reward as:
Fr Fr(a"] = r [a" + r/ss
P.[a] = r'la] r
Va + a", (a, a" E A).
(5)
Note that this ensures the agent always experiences an intervention, no matter which action chooses. During each episode, the agent learns but the principal's policy is fixed; the principal can update its policy only at the end of each episode [Algorithm 1.. Also, we assume that the prin- cipal can only observe the agent's 's actions of but not its base reward r' or policy update function f¹. We measure the performance of the principal using (2) with y
World model. The world model predicts the agent's next action (given the principal's prior ob- servations) to characterize the agent's behavior. We do not train the principal's 's world model to estimate the base rewards, because bandit agents with distinct base rewards could still execute the same sequence of actions, depending the agent's explore-exploit algorithm and its observations.
Challenges in the sequential setting. Compared to the simple game setting in Section princi- pal's s intervention policy learning with sequential (bandit) learners creates additional challenges:
Bandit agents may follow different strategies for action selection maximize their expe- rienced reward. The agent's 's rate of exploration may be constant (e.g., e-gredyy) or it can reduce with time (e.g.. UCB) within an episode. depending on its observations. This creates a highly non-stationary environment for the principal wherein its decision to intervene must adapt to different explore-exploit behaviors for the same agent within an episode. When the agent explores a larger action space, it further exacerbates the challenges in estimating the agent's behavior since the principal only has partial information about the agent.
Bandit agents are sequential learners and feedback (at, it) can update the policy n² dif- ferently at different steps L. The update may depend how optimistic (e.g.. UCB) or pessimistic (e.g., EXP3) the bandit agents are about their reward estimates. Hence, an in- tervention a" may not equally incentivize the agent at different t. Since the principal's interventions have different costs, a strategic principal must decide when to intervene and how much ((r') depending on its observations of the agent's actions.
Results. In the following experiments, use 15 bandit agents for training and 10 bandit agents for testing, each with different base rewards (both within and across train and test sets). |A| = 10. We consider two agent learning algorithms (UCB and e-greedy). In each experiment, the train and test agents use the same algorithm. but with different tendencies for exploration vs exploitation, de- termined by their exploration coefficients: 3 E f0.117 0.42, 0.5, 0.67] for UCB (higher 3 gives more exploration) and e E {0.1, 0.2, 0.3, 0.4, 0.5) for e-greedy (higher e gives more exploration). These constants were chosen such that they afford, on the average, the same number of exploratory actions when following either UCB or e-greedy strategy without any intervention (see (Appendx B).
In Table I we show the one-shot adapted principal's 's score on each test set over = 200 time steps. We compare MERMAIDE against 1) model-free baselines (MF-RL using REINFORCE and MF- MAMI. using MAML), as well as 2) REINFORCE with world model (WM-RL) (see [Appendix B for details). We also include "No Intervention" bascline show how agents behave by default.
Oft-of-distribution performance. Table 1 shows the principal's 's score when evaluated on test agents having a different exploration constant than train agents. Using meta-learning for the inter- vention policy (MF-MAML) and using world model to predict the agent's 's behavior (WM-RL. both have advantages for training a robust and one-shot adaptable intervention policy. A world model is advantageous when 1) the test agent is more exploratory than the train set (e.g..
0.1 at training, e = 0.4 at test), or 2) the agent explores throughout an episode and is likely to often select actions other than the one with its current maximum mean reward estimate (e.g.. e 0.5 at training). Be- cause we evaluate on K = 1, fine-tuning on only a single best-time episode, a trained world model provides useful prior belief representation for the principal. Indeed, the MF-RI. results show the
8

---

Under review as a conference paper at ICLR 2023
Train on UCB, 0.17
Test on = 0.17
8 0.27
= 0.42
8 0.5
3 0.67
No intervention
(
(
(()
10
12(0)
MF-L
119
(29
98 (2)
(0
77(1))
ME-MAML
133 (2)
125 (3)
107 (1)
97(1)
77 (0)
WM-RI.
(23
112.66
100 (4)
(2
(5())
MERMAIDE (ours)
184 (2)
141 (1)
115 (1)
103 (0)
(0)
Train on r-greedy, 0.1
0.1
0.2
0.3
0.4
0.5
No Intervention
3(0)
4(1)
7.0))
9())
11
MF-R
115
94 (4)
(49)
39
22
MF-MAML
122 (4)
(3)
58 (5)
40
12
WM-RL
(3)
MERMAIDE (ours)
134
108 (1)
85 (1)
(7)
(1)
Train UCB, 0.67
= 0.17
B 0.27
0.42
8 0.5
B 0.67
No Intervention
(
5 (0)
(())
10
12
ME-RL RL
(03
101
(2)
(5(())
74
MF-MAMI.
124 (2)
(1)
(02
94 (1)
80
WM-RL
89
85
MERMAIDE (ours)
131 (2)
125 (2)
109 (1)
101 (I)
85
Train o-greedy, 0.5
0.2
0.4
0.5
No intervattion
3(0)
(1)
7(0))
(
(1
ME-RL
4(5)
2.(3)
(
(1
7(1)
MF-MAML
(
4 (0)
6(0))
(1)
11(())
WM RL
(10)
MERMAIDE (ours)
87 (42)
102 (3)
78 (6)
69 (1)
(2)
Table 1: Test-time principal mean and standard
across random seeds. Left
column: Principal's algorithm (e.g.. MERMAIDE), training agent type (e.g., UCB with 3 = 0.17).
Other columns: Test-time scores on agents with the same algorithm, but different hyperparameters.
hidden state representation of the model-free principal might be unable to adapt to high environment non-stationarity without a trained next-agent-action world model.
Compared to an e-greedy agent, the UCB agent explores mostly at the start of an episode, for all 3. Hence, with UCB agents, the principal learns an effective one-shot adaptable intervention pol- icy using meta-learning (MF-MAML) only (even without world model), as the agents cause less distribution shift across different c. further emphasizes the effectiveness of meta-learning for adaptive policy learning: unlike MF-MAML, neither the world model nor the intervention policy is meta-learned in WM-RL. Moreover, it also shows that for the same amount of distribution shift (characterized in Appendix B), the relative benefit of world model meta-learning the principal's policy depends on the nature of the agent's 's exploration strategy (which is unknown to the principal).
In all, these results show that MERMAIDE combines the best of both techniques: the principal obtains a higher score across agents with different learning algorithms and explore-exploit behaviors.
Agent exploration vs intervention cost. order to intervene effectively, the principal should learn when to intervene and how much to incentivize the agent while minimizing its incurred cost. This challenging learning problem for the principal not just during meta-training, but more so during one-shot adaptation meta-test time. Bandit algorithms like EXP3 (Auer et al.) 2002) use pessimism the face of uncertainty, and encourage continued exploration. This increases the non-stationarity for the principal. In order to effectively incentivize such agents to prefer a" the principal needs to accurately predict the agent's policy from its observations; otherwise it can incur high cost for intervening ineffectively and lowering its score, and learn stop intervening. Indeed, our results when training on e = 0.5-greedy agents show that the ME-RL and MF-MAML principal stop intervening. In contrast, in that setting, MERMAIDE learns an effective intervention policy that outperforms all baselines, even under distribution shift between meta-train and meta-test agents.
7 DISCUSSION AND FUTURE WORK
We have shown that MERMAIDE is an effective framework to learn principal intervention policies that generalize well to agents with unseen learning behavior. Future work could extend MERMAIDE combination thereof.
to settings with multiple learning agents who may coordinate, compete, Moreover, is interesting to extend MERMAIDE to agents that adapt adversarially to the principal's intervention policy, which poses challenging non-stationary problem for the principal.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Pieter Abbeel and Andrew Y Ng. Apprenticeship learning via inverse reinforcement learning. In
Proceedings of the twenty-first international conference on Machine learning, pp. 1, 2004.
Brenna D Argall, Sonia Chernova, Manuela Veloso, and Brett Browning. A survey of robot learning from demonstration. Roboties and autonomous systems, 4765):499-48,, 2009.
Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire. The nonstochastic multi- armed bandit problem. SIAM journal on computing, 32(():48 2002.
Omar Ben-Ayed and Charles E Blair. Computational difficulties of bilevel linear programming. Operations Research, 38(3):556-500, 1990.
Craig Boutilier, Chih-wei Hsu, Branislav Kveton, Martin Mladenov, Csaba Szepesvari, and Manzil Zaheer. Differentiable meta-learning of bandit policies. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 2122-21344 Curran Associates, Inc., 2020. URL httpps:/pprocee:: ngs. neurips. CC/ httpppper/222//f1le///0
Benoit Colson, Patrice Marcotte, and Gilles Savard. An overview of bilevel optimization. Annals of operations research, 153(1):235-256, 2007.
Kathleen M Eisenhardt. Agency theory: An assessment and review. Academy of management
review, 14(1):57-74, 1989.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-agnostic meta-learning for fast adaptation of deep networks. In International conference on machine learning, pp. 1126-1135. PMLR, 2017a.
Chelsea Finn, Pieter Abbeel, and Sergey Levine. Model-Agnostic Meta-Learning for Fast Adap- tation Deep Networks. urXiv:/703.03444 [cs], July 2017b. URL http:://axxi...... orgg
abs 0bs/17033 111.11103300000 03400
Jakob N. Foerster, Richard Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mordatch. Learning with Opponent-Learning Awareness. arXhv:1709.0436 [cs], September 2018. URL
Wenshuo Guo, Kumar Krishna Agrawal, Aditya Grover, Vidya Muthukumar, and Ashwin Panan- jady. Learning from an exploring demonstrator: Optimal reward estimation for bandits, 2021. URL https:
org/
14866 14866
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization, arXiv preprint arXiv: 1412.6980, 2014.
Tze Leung Lai, Herbert Robbins, et al. Asymptotically efficient adaptive allocation rules. Advances in applied mathematics, 6(1):4-22, 1985.
Ryan Lowe, YI WU, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi- Agent Actor-Critic for Mixed Dooperative-Competiii Environments. I. Guyon, V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnet (eds.), Advances in Neural Information Processing Systems 30, pp. 6390. Curran Associates, Inc., 2017.
Jelena Luketina, Sebastian Flennerhag, Yannick Schroecker, David Abel, Tom Zahavy, and Satinder Singh. Meta-gradients in non-stationary environments. In ICLR Workshop on Agent Learning in Open--indedness, 2022.
Setareh Maghsudi, Andrew Lan, Jie Xu, and Mihaela Der Schaar. Personalized education in the artificial intelligence era: what to expect next. IEEE Signal Processing Magazine, 38(3):77-50, 2021.
Paul Milgrom and Paul Robert Milgrom. Putting auction theory to work. Cambridge University Press, 2004.
10

---

Under review as a conference paper at ICLR 2023
Anusha Nagabandi, Ignasi Clavera, Simin Liu, Ronald S Fearing, Pieter Abbeel, Sergey Levine, and Chelsea Finn. Learning to adapt in dynamic, real-world environments through meta- reinforcement learning. In International Conference Learning Representations, 2018.
David Pardoe, Peter Stone, Maytal Saar-Tsechansky, and Kerem Tomak. Adaptive mechanism de- sign: A metalearning approach. In Proceedings of the 8th International Conference on Elec- tronic Commerce: The New e-Commerce: Innovations for Conquering Current Barriers, Obsta- cles and Limitations to Conducting Successful Business on the Internet, ICEC '06, pp. 92-102, New York, NY, USA, 2006. Association for Computing Machinery. ISBN 1595933921, doi: N0.1145/11514544 1151480, htRttt/t::///ttt. wrgg10.gg1oooo 1ttp///111111111111111
Ankur Sinha, Pekka Malo, and Kalyanmoy Deb. A review bilevel optimization: from classical to cvolutionary approaches and applications. IEEE Transactions on Evolutionary Computation, 22 (2):276-295, 2017.
Richard S Sutton and Andrew G Barto. Introduction to reinforcement learning, 1998.
Heinrich Von Stackelberg. Market structure and equilibrium. Springer Science & Business Media, 2010.
Ronald J Williams. Simple statistical gradient algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-256 1992.
Stephan Zheng, Alexander Trott, Sunil Srinivasa, Nikhil Naik, Melvin Gruesbeck, David C. Parkes, and Richard Socher. The Al Economist: Improving Equality and Productivity with Al-Driven Tax Policies. arXiv:2004.13322 [cs, econ, q-fin, stat), April 2020. URL http:://rxxil
13332
Stephan Zheng, Alexander Trott, Sunil Srinivasa, David Parkes, and Richard Socher. The ai economist: Taxation policy design via two-level deep multiagent reinforcement learning. Sci- ence Advances, 8188)22bb32667, 2022. doi: 10. 10.11226sciaavvab22207..
URL https: :/ww::
science..rggooi//bbeoooo. 1126 001/26//ciiai sciadv. 122b/scladvaaab2200 abk2607

---

Under review as a conference paper at ICLR 2023
Variable
Symbol
Time
Principal
p
Agent
State
State vector
State space
S
Agent's action space
A
Principal's action space
AP
Action sequence
d1:7
{01,
02
0T)
Agent i's reward sequence
7 1.
Principal's 's reward sequence
1.
Transition function
P
Agent i's policy
n
Principal's 's intervention policy
Agent's mean estimate of intervened rewards for action a
Po
Number of adaptation steps Number of meta-tasks for the planner
K
N
Principal's 's history of interventions and observed agent actions upto time &
{op, ai a2
aj
Agent's history of actions taken and rewards ob- served upto time
Hi = (a], az
Table 2: Overview of notation.
Principal's policy parameter
0
Agent i's learning algorithm
f F
Agent i's true action mean rewards
n¹ ~u
Agent i's intervened action mean rewards
A
Principal's action at time
df Ty (o H
Hidden state space of the principal's recurrent world model Agent's action at time t Agent's reward at time 6 Principal's world model estimate of the agent's action probability distribution
af ~ म| (ailH)) it I....,T N (īt'
A AP H - (A), A E
Principal's world model estimate of the latent state of the environment
gh
A
H, gú.o E E (H)
Principal's s world model hidden state embeding in the LSTM architecture
h = giو (a h( t t= 2.... hj gw.o
Table 3: Notation for MERMAIDE See Section Section 5 for their use.
A NOTATION
For an overview of all symbols and variables used in this work, see Table 2 and Table 3
12

---

Under review as a conference paper at ICLR 2023
B ADDITIONAL RESULTS
B.1 DESCRIPTION OF THE BANDIT ALGORITHMS
We provide a brief overview of the learning algorithms referred to in Section 6
UCB. This is an Upper Confidence Bound based exploration-exploittii algorithm that follows the principle of optimism in the face of uncertainty, At each time step the bandit agent selects an action
logt
arg max Poo + PV
(6)
nh
where na is the number of steps until in which it previously selected the action a, Ma is its corre- sponding mean estimate for the experienced rewards F for action a and 9 is the exploration constant that balances the amount of exploration vs. exploitation across time horizon T.. A higher value of 3 makes the agent less optimistic and explore its action space more. The UCB agent's ten- dency explore is also affected by the difference in the mean reward estimates of its actions. In the context of our mechanism design problem formulation, the UCB agent has a larger value of 5 max, Fa Tat without any intervention at the beginning of episode, its confidence bounds would quickly converge to exploiting the action arg max, Ta- So a principal that intervenes only towards the later stages of an episode with this agent would have to provide much more incentives (higher r') to alter the agent's preferred action to be a", thus incurring larger cost as compared to principal that intervenes more the beginning of an episode when the UCB agent still ex- ploring its action space. This is also illustrated in /Section 4 with a simpler best response agent in the single round game setting. As shown in Fig. 1b and Fig. Ic, under observation noise (partial information), the meta-trained principal has better one-shot meta-test-time performance when the agent's ' base payoff has a higher difference between the principal's 's preferred action and the agent's intrinsic preference without any intervention.
e-greedy. A simple exploration-explee exploitation strategy in the bandit setting is the e-greedy rule (Sut- ton & Barto 1998) wherein the agent selects with probability 1 1-6 e the action a, = arg max, Pa and with probability it selects random action. In setting, consider episode, which results in a uniform exploration rate throughout. In contrast to the UCB agent, the e- greedy algorithm simulates less optimistic, more exploratory agent for which the principal requires a robust belief representation of the agent's predicted behavior conditioned on the principal's I'ss past observations Table I). Since there is a uniform exploration rate for the agent, the principal has to continue intervening intermittently throughout an episode, especially when 8 is large and the agent could obtain a higher reward for an action a o by exploring its action space when the principal does not intervene.
be constant during an
EXP3. The Exponential-weighh algorithm for Exploration and Exploitation (EXP3) (Auer et al.) 2002] follows a more pessimistic approach to explorationeexplotatiio the bandit setting. It main- tains set of weights for each agent action E A which are updated using the experienced rewards i as follows:
1eepp (Sar.)
Te(a))
+ (1 w)
|A]
Σ Ea.lA 17 exp (Sur.t)
where
Sa,
Σ 1 [aj = at} 1=1
Fai. mt
W
(8)
[
Here, is the variable that determines the extent of uniform random exploration in the action space. This presents a very challenging problem to learn a suitable belief representation for such agents that can be utilized by principal to guide its intervention policy. In /Section 6 we exclude EXP3 from TTable since it is primarily designed for an adversarial bandit setup, whereas we do not consider an agent have such biases under our current problem formulation.
13

---

Under review as a conference paper at ICLR 2023
UCB
e-greedy
0.17
33 (0)
33 (0)
0.10
0.27
47 (0)
47 (4)
0.20
0,42
70 (0)
68 (9)
0.30
0.50
80 (0)
81 (3)
0,40
0.67
99 (0)
99 (1)
0.50
Table 4: Experiment design choice. Frequeney of agent selecting a, * arg max, ta with UCB and e-greedy algorithms on the same set of base rewards (without any intervention) with a horizon T = 200, averaged across 3 random seeds.
B.2 CHARACTERIZING THE DISTRIBUTION SHIFT IN OUR EVALUATION SETUP
Bandit agents having the same base reward r make different explore-exploit decisions depending on their algorithm (eg. UCB, e-greedy) and also their prior observations. In [Section 6 we consider agents with the same set of base rewards, but following different bandit algorithms. Both UCB and e-greedy have tunable parameters that determine their explore-explon tradeoff. In order measure the robustness of the leartt principal policy to different agent behavior (leading to different levels of non-stationarity in the principal's environment between training and test agents), we vary the amount of exploration performed by the agent by varying the respective parameters: /3 for the UCB agent and e for the e-greedy agent. Table shows the average (and standard error) frequency of exploration by the agents for our choices of 3 and in (Section 6 We vary 8 and such that they are pairwise comparable in Table aand would lead to similar change in exploration frequency for both UCB and e-greedy agents. In other words, following Table I principal trained with UCB agents having 3 = 0.17 when evaluated with UCB agents having 3 E {0.17, 0.27, 0.42, 0.50, 0.67] will encounter similar shift in the agent's exploration frequency in the case of training with e-greedy agents with e = 0.1 and evaluating on e-greedy agents having e E (0.1, 0.2, 0.3, 0.4, 0.5,. In that case, the difference in achieved scores between the UCB and e-greedy agents can be attributed to the way in which they distribute their exploratory actions: UCB agent being more optimistic focuses most of exploration at the beginning of an episode, whereas the c-greedy agent more stochastic with uniform random exploration throughout.
B.3 DESCRIPTION OF BASELINES
We now describe the details of our evaluated baselines in Section 6 along with their variations that assume access to an agent state oracle.
Rule based mechanism with an agent state oracle (RB): Given an oracle that correctly identifies the action 0; to be taken by an agent in the next time step, simple rule based approach is for the principal to intervene at time when at * a". We assume that the principal always intervenes with fixed incentive (r' = 0.5 1) and we compute the principal's maximum possible score. Note that this is not a realistic solution for the principal since it is impractical to expect the availability such an oracle, especially for out of distribution test agents.
Model-free learning based mechanism: In this framework, we assume that the plan- ner has a recurrent intervention policy that outputs a distribution over interventions af Th (of |a |a]- h(_1); conditioned on the planner's 's intervention and observed agent action at f 1. The policy network is trained using REINFORCE for the MF-RL baseline and using MAMI. for the MF-MAMI. baseline.
Learning based mechanism with agent state oracle: In this setting, the principal learns recurrent intervention policy that outputs a distribution over interventions of ~ m (aElai, 1[1) conditioned on the true agent action at time provided by oracle. The policy network trained using REINFORCE for the SB-RL. baseline and MAML for the SB-MAML. baseline.
Learning based mechanism with a world model without meta-lea (WM-RL): In this setting, we our proposed recurrent world model with recurrent intervention policy trained
14

---

Under review as a conference paper at ICLR 2023
Train on UCB, _ = 0.17
Test on = 0.17
8 == 0.27
8 = 0.42
$ = 0.5
== 0.67
No intervention
(
166 (
8(0)
10
12(0)
RB
173
(54
(4)
126 (0)
SB-RL
168 (3)
138 (27)
128 (26)
122 (24)
107 (22)
SR-MAMI.
169 (3)
169
(2)
(48
(28
Train on c-greedy,
No intevvation
3
4(1)
7 (()
9
11
RB
(3)
(1)
(4)
(7
62
SB-RL
148 (2)
(3)
87 (4)
(6)
50
SB-MAML
152 (1)
126 (2)
105 (3)
(3
30
Train on UCB, / = 0.67
= 0.17
#
0.27
0.42
# 0.5
B 0.67
No Intervention
(
166 (0)
(0)
10.00)
12
RB
173
154
146 (0)
126 (0)
SB-RL
166 (3)
163 (2)
150
146 (2)
128 (2)
SB MAML
(7)
(70
159 (0)
152
13)
Train e-greedy, 0.5
0.4
No intervationn
3())
(())
7(0)
(1)
11 (1)
(3)
(1)
(4)
(4)
SB RL SR-MAMI.
49 (46)
51 (35)
64
61 (15)
(17)
93 (45)
62 (32)
(13)
58 (25)
247(17)
Table 5: Principal (with oracle agent state input) scores across 3 random seeds. These baselines are not applicable in practice since they cheat by assuming access to an oracle that always informs them of the agent's next action. We include them here form of standardization with respect to (perfect) system that does not face the challenges of partial observability or out-of-distribution generalization for mechanism design.
using REINFORCE. Here, the policy network outputs distribution over interventions af To (o, [at, 11-1) where aj arg max, fw a
We would like to highlight an implementation detail our baselines indicated 'RL' in Section 6 Since we evaluate our learnt principal policy in the K-shot adaptation setting which is common in the meta-learning literature, we ensure that the principal policies that are not meta-traines are also allowed to K-shot adapt test time. This means that the 'RL' policies time, before evaluation, using K rounds of principal-agent interactions. This is contrast to |Section 4 where 'RI'' was trained from scratch during test time adaptation. It further shows that with pre-training (on the same set of train agents as used by 'MAMI'), standard policy gradient update does not lead test time K-shot adaptation on test agents.
also updated test
In Table 5
we compare the test time scores for the principal policy having access to state based oracle. We observe that overall, the meta-trained principal policy (SB-MAML) achieves higher score even with distribution shift across different bandit algorithms and different levels of explo- ration, compared to the SB-RL baseline. The rule based baseline also shows strong performance but we note its scores do not reflect adaptation to distribution shift. However, none of these baselines that assume the principal has access an oracle that correctly predicts the agent's action at the next time step are realistic. We can only treat the scores in Table 5) as gold standards in a perfect system that does not account for the challenges faced by a principal in practice.
Training details. Section 4 the principal policy nº a fully connected neural network (MLP) with one hidden layer and ReLU activation. Given an (noisy) observed value of the agent type as input, it predicts the probability of intervention: n.. The principal's action time is of ~ Bern (x²))
For the 'RI'' principal, trained on the test agents starting from scratch over K episodes before evaluation. For the MAML principal. it is meta-trained to learn initial parameterization with different set of training agents and evaluated with shot adaptation on the test agents.
In Section 6. the recurrent world model and policy networks are GRUs with 2 layers and hidden state dimension 128. For meta-training, the inner gradient update loop uses SGD optimizer with a learning rate of 7 x 10-4 whereas the meta-update step uses Adam with learning rate of 0.001. The world model is trained only with the set of training agents, it is not adapted at test time: only the policy network is K-shot adapted.
15

---

Under review as a conference paper at ICLR 2023
Algorithm 2 MERMAIDE (K-shot Adaptation)
Initialize principal with trained parameters (m Wrain), and hidden states h hig
2: for agents (tasks)
.. Tesst do
3: Initialize agent: (n²,, m(). task specific intervention policy parameter (T0) = meta-
4:
for k = .....,.......................... K do for time = .,,..., do
Inner loop for K episodes. >. For each episode with 7 principal-agen interactions Predict 0j arg mäx;; Turn (ailai- a h1-1) using the world model.
5:
6:
7:
Intervention: zi' = μ¹ + a. of ~ x (T2)) (at aaaaa.i....... h (
8:
Agent acts: of मं and receives reward ry N ("',0") o + +
9:
Locally update 0 (T)) + (Th+2)-
Using REINFORCE.
10:
for 1= 1..... T do
Rollout for evaluation
11:
Predict a arg m Auran (ajla)-1: n/11; h1_)) using the world model.
12:
Intervention: jL Ju' + of' of T ((rk) (aflai_1, df at. M1-1)
Agent acts: af ~ o/. receives reward rf ~ N (fr oif, Updates oh #241-
14:
Update principal's 's score.
B.4 OVERVIEW OF K-SHOT ADAPTATION WITH MERMAIDE:
Algorithm 2 outlines our framework for K-shot adaptation of the meta-trained principal test agents. In our experiments, K = 1.
16

---

Under review as a conference paper at ICLR 2023
Train on UCB, 8 0.17
Test on 3
0.17
0.27
8 0.42
= 0.5
0.67
Intervention
(0)
(())
8 (0)
(0
(2
MI-RL
119
109 (2)
98
77 (1)
ME-MAML.
133 (2)
125 (3)
107 (1)
97(1)
77 (0)
WM-RI.
123 (7)
112 (6)
100
75
MERMAIDE (ours)
154 (2)
141 (1)
115 (1)
103 (0)
(0
MERMAIDE (ours)- 2nd
MERMAIDE (K
148 (2)
138(1)
120(1)
103(2)
89())
WM-RL
109 (1)
92 (-)
Train on e-greedy, 0.1
= 0.1
0.2
= 0.3
0.4
0.5
ME-RL
115
94 (4)
(49)
39 (6)
(9)
MI MAMM..
12(1)
WM-RL.
115 (4)
94 (5)
70 (1)
(3)
38)
MERMAIDE (ours)
(34-(1)
108 (1)
29)
MERMAIDE (ours)- 2nd
132 (3)
111
89 (1)
(1)
MERMAIDE (K
133 (2)
109 (3)
86 (2)
65 (3)
(1)
Train on U
0.67
8 0.17
0.27
8
0.42
@ 0.5
0.67
No Intervention
(0)
101 (0)
(0)
(0)
(2
MF-RL
103 (3)
(2)
(4)
MAML.
124 (2)
116(1)
102 (1)
(1)
(1)
WM-RI. RI.
100 (4)
85
(1())
74
MERMAIDE (ours)
131 (2)
125 (2)
109 (1)
101 (1)
83 (I)
MERMAIDE (ours)- 2nd
(2)
MERMAIDE (K
115
(3)
103 (4)
100 (3)
89 (3)
WM-RL
104
(-)
Train on e-greedy, 0.5
= 0.1
0.2
0.3
0.4
0.5
3
MI-RL
((5)
(3)
(U)
(1(55)
7(1)
MAML.
(0)
8())
WM-RI.
102 (6)
(10)
68 (3)
(7)
30 30)
MERMAIDE (ours)
(42)
(3)
(6)
46 (2)
MERMAIDE (ours) 2nd
(17)
(1.(12)
(20)
(15)
MERMAIDE (K =
113.(20)
(15(
71 (16)
48 (14)
(15)
Table 6: Test-time principal mean and standard error scores. Left column: Principal's algorithm (e.g.. MERMAIDE), training agent type (e.g., UCB with 3 = 0.17). Other columns: Test-time scores on agents with the same algorithm, but different hyperparameters. Gold-colored values rep- resent testing with a principal that not updated during test-time, i.e., K = 0-shot generalization. perform par when trained on B 0.17 and
We see that the principal O-shot generalization does not work so well when the principal was trained on more exploratory hyperparameter values, i.e., B 0.67 and 0.5. To compare the levels of exploration between different hyperparameter settings, please refer to Appendix B.2 and Table 4. All results are based on random seeds. Note that the results in blue rows above; as such, there are two sets of random seeds for MERMAIDE. We see that the results are similar between the two sets of random seeds.
0.1, but that
random seeds with the same settings as the
C ADDITIONAL EXPERIMENTAL RESULTS WITH BANDIT AGENTS
We ran the same set of experiments for MERMAIDE from Section with 3 additional results. At the time of the rebuttal deadline, some of the runs have not converged reporting these additional results in the marked in blue in Table We will update these with final converged values and more seeds if requested for the camera ready version the paper accepted. On the basis of current results, do not expect a significant variation from the values originally reported in Table I even with more seeds.
Additional seeds seeds for
Table 1
Zero-shot evaluation results with MERMAIDE. MERMAIDE in the zero-shot setting iee the policy is not updated at meta-test time (K = 0). Table shows the preliminary results for these experiments in gold. Some these experiments have not coverged yet, but we do not expect lot of improvement compared to the reported scores. 0.17 and e = 0.1, but that 0-shot generalization does not work well when the principal was trained on more exploratory hyperparameter values, ie.. 3 = 0.67 and e = 0.5. To compare the levels of exploration between different hyerrparameter settings, please refer Appendix B.2 and Table 4.
requested by reviewer 4J8Y, we evaluated
We see that the principal can perform on par when trained on
17

---

Under review as a conference paper at ICLR 2023
Train on UCB, , = 0.42 No intervention WM-RL
Test on 0.1
0.2
0.3
< 0.4
<= 0.5 11 (1)
(()
4(1)
7())
9
91 (4)
62 (8)
68 (1)
28 (4)
MERMAIDE (ours)
103 (1)
(2)
30 (2)
(
Train on e-greedy, 0.3 No
Test on / = 0.17
| 0.27
= 0.42
B 0.5
B 0.67
(0)
WM-RI.
127 (7)
95 (2)
80
(5)
61 (4)
MERMAIDE (ours)
(2)
102
(2)
96
(2)
Table 7: Test-time principal mean and standard error scores across random seeds, K = 0. Left column: Principal's algorithm (e.g., MERMAIDE), training agent type (e.g., UCB with 3 = 0.42). Other columns: Test-time scores on agents with different algorithm and different hy- perparameters. We see that MERMAIDE generalizes well when tested on agents that explore the same amount or less than the train-time agents. For clarity, note that higher 3 and lead to more exploration. More generally, principal that is trained on a stochastic agent generalizes well to an equal or less stochastic agent, e.g., training that the behavior of UCB is less stochastic than e-greedy.
0.3 and testing UCB with 3 0.5, 0.67; note
Cross algorithm evaluation. Table indicates the mean and standard scores for evalua- tion in the K = 0-shot generalization setting when the training agent and test agents are of dif- ferent types. Note that the behavior of UCB agents is less stochastic than e-greedy agents. We observe that when trained with UCB agents, MERMAIDE outperforms WM-RL for generalizing to c-greedy agents that have a lower exploration coefficient with c-greedy agents, MERMAIDE outperforms WM-RL for generalizing to UCB agents with both higher and lower levels of exploration. More generally, a meta-learning principal that trained on stochastic agent generalizes well to equal or less stochastic agent in the zero shot setting.
0.1 or 0.2. In contrast, when trained
18


Reviews:
[{"review_id": "rqor5A-YDDs", "reviewer": "Reviewer_C92e", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper presents a MAML approach to meta-training a model based RL policy which will learn to \"nudge\" no-regret bandit learning algorithms into cooperating in a single-player prisonners dilemma. Experimental evaluation shows that the model based method allows \"level-2\" reasoning about the \"level-1\" decision and adaption rule of the bandit algorithm.", "summary_of_the_review": "Overall, I'd say this paper *barely* misses the threshold to being accepted. If the additional experiment on 2 players can be added I think it would be a clear accept, if not it would depend on the quality of discussion on why this is justified.\n\n---\n\nPost-rebuttal edit: the reframing of narrowing of scope from \"mechanism design\" to \"learning to align learners\" done by the authors after our discussion and the additional cross-algorithm experiments made me change my score from 5 to 6", "strength_and_weaknesses": "Strengths:\n\n- I think this is an interesting first step towards learning best mechanism design. Nudging two agents playing prisoners dilemma towards cooperating and being able to identify the minimal number of interventions *dynamically* by meta-adapting is an intuitive \"minimal\" mechanism design\n- the experiments are well thought out, explained and reasoned for\n- it is interesting to see that the model based mechanism can learn to recognise agent behaviour and \n\nWeaknesses:\n\n- the biggest problem I have with the paper is that as of now, it isn't really mechanism design, it's simply curriculum learning for bandit algorithms. For it to truly be mechanism design, I would expect there to be a *game* between no-regret learners (as above, nudging *two* players, making for a three player game). As of right now, one uncharitable way of characterising the paper would be \"empirical evaluation that MAML vs no-regret bandit algorithm games converge\" (which, I must emphasise, is still a fine and nontrivial contribution). I think this can be alleviated by discussing the limitations the choice to focus on single agent poses, or even better, by evaluating the system in the 2-players, 1 planner setting, with \"no planner\" being a natural baseline. To be honest, I expect this to be *much* more difficult, but even a negative result would strengthen the contribution of this paper by establishing that a single adaptive algorithm (albeit simple) is \"steerable\" while a game might not be anymore", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "eygRo-VDuz", "reviewer": "Reviewer_9dtX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposed MERMADE, a deep RL approach to mechanism design that fuses model-based methods and gradient-based meta-learning methods to design a mechanism with fast adaptability. The authors analyze the one-shot adaptation performance of a meta-learned planner in a matrix game setting, under both perfect and noisy observations for the agent and the planner. They show that meta-training reliably finds solutions that one-shot adapt well, and characterize how the planner’s out-of-distribution performance depends on its observable information about the agent.", "summary_of_the_review": "This paper proposes a mechanism design algorithm based on the model-based method and meta-learning, and learns the adaptive mechanism, but lacks theoretical analysis, insufficient experimental design, insufficient chart production, and lack of graphics to illustrate the overall structure of the algorithm.", "strength_and_weaknesses": "a)\tStrength:\nDifferent from the way of mechanism design in traditional game theory, this paper combines model-based and meta-learning theory in reinforcement learning to design a mechanism with good robustness and adaptability.\nb)\tWeaknesses: \nIn model-based reinforcement learning, the author lacks sufficient analysis of model error and policy shift and lacks a detailed description of how the model is established. The experimental results are not fully displayed graphically, and the paper is not very easy to understand. Experimental results do not have multiple sets of seeds to eliminate probabilistic errors.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "TPY1p4tCN4o", "reviewer": "Reviewer_2WWc", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "Mechanism design studies the problem of constructing a game that elicits a desired behavior from its' players. Often players adapt their policy with feedback through a learning algorithm to improve their future performance. This raises the question of how to design a mechanism that elicits a specified behavior while being agnostic to its' players' learning algorithms. This manuscript proposes an algorithm that learns to modify a single-agent player's behavior by altering said agent's reward function. \n\nThe authors claim the following contributions:\n - A model-based meta-learning mechanism designing algorithm for few-shot games with unknown agents.\n - Empirically demonstrate their algorithm on single-stage matrix games with perfect and noisy observation.\n - Empirically demonstrate their algorithms on multi-stage matrix games with learning agents.\n", "summary_of_the_review": "Overall, I'm excited to see work in this area, but the lack of discussion of inverse reinforcement learning makes it hard to understand where this paper fits into the literature. Moreover, without IRL baselines and narrative, it's unclear if this work contributes a new idea or one that is competitive in this domain. As these are major scientific concerns with this work I would not recommend publishing this work in its current state, but encourage the author's to continue to pursue this topic. ", "strength_and_weaknesses": "**Strengths**\n - The exposition following their framing of intervened rewards and the planner was very clear.\n - Inclusion of the per-opponent generalization in Table 1 provides better insights into generalization, and the contribution of the model-based additions to their algorithm. \n - Mechanism Design is an understudied field within multiagent reinforcement learning methods and the area needs more attention.\n\n**Weaknesses**\n - Meta-learning appears to be an exceptionally complex approach for mechanism design in the provided experiments. It would embolden the author's work to either show analytic solutions and how their algorithm offers an advantage, and/or demonstrate their algorithm on a game where we cannot compute analytic or Bayesian solutions. \n - The authors only investigate a single-agent environment and analyze repeated interactions between the agent's behavior and implementation of mechanisms derived from a co-learner independently. This is strange for a piece on mechanism design, because the incentives of both \"players\" (the agent and mechanism designer) are aligned. There is no strategic component present such as an agent not being truthful about their policy. I am curious if the authors have invested applying this method to general-sum games with >1 player  and if their mechanism selects equilibrium that are strategy-proof, efficient, or balanced?\n - Furthermore, as this work focuses on single-agent environments, this work is effectively in inverse reinforcement learning. I was hoping the authors could comment on how their algorithm differs from the existing work in this space? I would also ask that they include this discussion in their paper. They should also include baselines from this field in this work. \n - A major point in their claims is that their algorithm can quickly adapt to unseen test agents. As a result, it's surprising to me that the results all assume that the train and test agents are using the same underlying algorithm (with different exploration coefficients). Could the authors comment on the generalization performance of their algorithm compared to baselines _across_ algorithms? Moreover, comment on the diversity of the population exhibited by the coefficients are chosen, it's not clear to me if beta=0.17 or beta=0.27 create meaningfully different behaviors in such a simple game.\n - I found their usage of test/train/meta-test/meta-train and its relation with varying k-shot regimes to be confusing. Perhaps that's just me, but for example \".... adapted quickly on a single test-time trajectory\", is ambiguous as if the adaptation must occur within the trajectory, or if the adaptation is conditioned on a single trajectory. Moreover, if either is the problem setting, then why is there commentary about K-shots?\n - The name of the algorithm is never explained?", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "FOUSMd09Ym", "reviewer": "Reviewer_4J8Y", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper explores the problem of mechanism design which studies how to design reward functions and environmental rules defining mathematical games. The applications of mechanism design spans across many domains from optimizing social welfare with economic policies to designing governmental policies. The conventional problem in this space is that it is often expensive to understand the effect of changes to a mechanism design in the real world. Thus, it is often convenient to study the mechanisms in simulations before deploying them in real world. \n\nThe paper presents a deep RL approach to mechanism design that learns a world model and uses meta-learning to learn a mechanism that can be adapted quickly to unseen test agents. The approach called MERMADE consists of a planner that has an associated cost for intervening an agent and the goal of this planner is to achieve the designer’s objective. The learning agents maximize the rewards they experience from an environment. \n\nThe approach is evaluated on one-shot adaptation performance of the planner in matrix game setups. \n\n", "summary_of_the_review": "\nMERMADE is interesting because it merges meta-learning with mechanism design. The idea looks very promising. \nHow do these ideas scale to larger/challenging domains (for example, in MDPs with continuous state spaces, with multi-agents environments)? What kind of research questions need to be addressed to make this idea to scale?\n\nHow about including a baseline that is not adapted at test time? What does the performance of the baseline look like when it is evaluated in a zero-shot manner at test time? How large is the gap between MERMADE and this baseline? This will be useful to understand the contribution made by MERMADE over a baseline that is trained similarly but held fixed at test time.\n\nThe experiment results seem to be averaged across 3 random seeds. The experiment setup should run fast and should not be a challenge to report results from many more random seeds. Have the authors considered looking into reporting results from more seeds?\n\nHow are the hyperparameters tuned for MERMADE and for the baseline methods? \n\nIn the experiments, it seems like it is possible to measure the optimal performance of an oracle in mechanism design. It would be interesting to see the difference between MERMADE and such an oracle in the experiments. \n", "strength_and_weaknesses": "Strengths:\nThe paper is well-written.\nPresents the idea of mechanism design with MERMADE in a clear manner.\nExperiment setups and results are well-presented and the performance of the approach is demonstrably strong wrto baselines. \n\nWeaknesses: \nExperiments are limited to Matrix games and Bandit settings.\nMore random seeds and baselines are needed in the experiments. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject