Learning a Game by Paying the Agents
Authors: Brian Hu Zhang
Tao Lin
Yiling Chen
Tuomas Sandholm
Venue: ICLR 2026 Poster (2026)
Keywords: No-Regret Learning
Inverse Game Theory
Revealed Preference
Steering
Primary area: learning theory
TL;DR: We propose the first algorithm to learn a game from the actions of any no-regret learning agents by paying the agents.

Abstract: We study the problem of learning the utility functions of no-regret learning agents in a repeated normal-form game.
Differing from most prior literature, we introduce a principal with the power to observe the agents playing the game, send agents signals, and give agents *payments* as a function of their actions.
We show that the principal can, using a number of rounds polynomial in the size of the game, learn the utility functions of all agents to any desired precision $\varepsilon > 0$, for *any* no-regret learning algorithms of the agents.
Our main technique is to formulate a zero-sum game between the principal and the agents, where the principal chooses strategies among the set of all payment functions to minimize the agent's payoff. 
Finally, we discuss implications for the problem of *steering* agents. We introduce, using our utility-learning algorithm as a subroutine, the first algorithm for steering arbitrary no-regret learning agents to a desired equilibrium without prior knowledge of their utility functions.

Published as a conference paper at ICLR 2026
LEARNING A GAME BY PAYING THE AGENTS
Brian Hu Zhang
Tao Lin" Microsoft Research & The Chinese University of Hong Kong, Shenzhen lintao@culin edu. cn
Massachusetts Institute of Technology zhangbh@csail mit
Yiling Chen
Tuomas Sandholm
Harvard University yi silingesess harvard.eem edu
Carnegie Mellon University & Strategy Robot, Inc., Strategic Machine, Inc., Optimized Markets, Inc sandholmf es cmu edu
ABSTRACT
We study the problem of learning the utility functions of no-regret learning agents in repeated normal-form game. Differing from most prior literature, we intro- duce a principal with the power to observe the agents playing the game, send agents signals, and give agents payments as a function of their actions. We show that the principal can, using number of rounds polynomial in the size of the game, learn the utility functions of all agents to any desired precision e > 0, for any no-regret learning algorithms of the agents. Our main technique is to formu- late zero-sum game between the principal and the agents, where the principal chooses strategies among the set of all payment functions to minimize the agent's s payoff. Finally, we discuss implications for the problem of steering agents. We introduce, using our utility-learingg algorithm subroutine, the first algorithm for steering arbitrary no-regret learning agents to a desired equilibrium without prior knowledge of their utility functions.
INTRODUCTION
Most literature on game theory aims to understand the behavior of agents in a game given the pref- erences the agents. That is, knowing what the agents want, how will they act? In this paper, we consider the inverse of this problem: if all we can observe is how agents act, can we infer what they want, that is, their utility functions? The problem of infering agents' utility functions from their behavior is known as "learning from revealed preferences" (e.g.. Beigman & Vohra (2006); Zadimoghaddam & Roth (2012)) or "inverse game theory" (e.g., Kuleshov Schrijvers (2015)). Despite long history, these two lines of work have some limitations. First, they often assume that the observed behavior of the agents is (Nash) equilibrium behavior. This is arguably unrealistic, especially because Nash equilibria are PPAD-hard compute (Daskalakis et al., 2006; Chen al., 2009). Second, they mostly focus on passive problems, aiming to learn agents' utility functions from fixed set of behavioral data. Often, this creates trivial impossibility results, stemming from the fact that the behavioral data available is simply not enough to determine the agents' preferences.
In this paper, we consider an active, non-equilirrium inverse game problem. A principal observes the actions of agents playing an unknown repeated game, and seeks to learn the agents' utility functions from those observations. We do not assume the agents to play equilibria. Instead, they can use any no-regrel algorithms to learn to choose actions. The principal can actively modify the unknown game by giving payments to the agents as a function their play, as well as providing signals, in the spirit of correlated equilibria (Aumann, 1974). The signaling scheme and payment scheme can change from round to round, depending on the agents' past actions. Under this setup, we ask:
Can principal learn the utility functions of no-regret learning agents?
"Equal contribution. Order determined randomly.

---

Published as a conference paper at ICLR 2026
We will give positive answer to this question, by designing algorithm for the principal to learn the game via payments and signals. Then, we will apply our algorithm to steering no-regret learning agents toward desirable outcomes, problem introduced by Zhang et al. (2024). Building on their results, we will show that is possible to steer agents to optimal outcomes even without prior knowledge of their utility functions.
1.1 OVERVIEW OF OUR RESULTS
In our model, agents play fixed normal-form game I' repeatedly over I rounds, using arbitrary no- regret learning algorithms. principal, initially knowing nothing about the agents' utility functions, can give non-negative payments to the agents, that get added to the agents' utilities, to influence the agents' behavior. The principal aims to learn the utility functions of all agents to given target precision & > 0, based on the actions taken by the agents.
Learning the utility functions completely impossible, because agents' incentives only depend on relative utilities between their actions, not absolute utilities. Thus, we only demand that the principal output utility functions that yield a pprategialll--eqivale relative utilities are identical to those in the true game. Equivalently, identify each agent's utility function up to a term that does not depend on that agent's 's action.
game, that is, one in which all agents'
Our main result is efficient algorithm for the principal to learn the game by paying the agents. Let n be the number of agents, m, be the number of actions of each agent i, and M = II, m, be the total number of action profiles. Assume that each agent's 's regret in T rounds is at most O(v (satisfied by typical no-regret algorithms). Our algorithm learns the game polynomially many rounds:
Theorem 1.1 (Informal version of Theorems 4.3 and 4.4). There exists principal algorithm that learns a game to precision & in MO(1) / rounds. This light up to the exponent hidden by the O.
The main idea of our algorithm is surprisingly simple but powerful. In the single-agent case, we let the principal play zero-sum game with the agent, where the agent chooses actions to maximize its reward, which is utility plus payment, while the principal chooses payments to minimize the agent's reward. This game admits a unique equilibrium where the principal's payment function is equal to the negation of the agent's 's utility function. By running no-regret algorithms against each other, the principal and agent can reach such an equilibrium, so the negative average payment function will be an accurate estimate of the agent's utility function. In the multi-agent case, separate the learning problems for different agents, reducing the problem to the single-agent case.
signals to
We then turn to motivating application, which is the problem of steering no-regret learners to desirable outcomes, introduced by Zhang et al. (2024). Departing from them, we do not require the principal to have prior knowledge of the agents' utility functions. We define solution concept called correlated equilibrium with payments (CEP), in which the principal has utility function, and wishes to optimize its utility minus the amount of payment that must give. Departing from Zhang et al. (2024) again, it is possible for the total amount of payment to be nonzero in equilibrium (i.e., linearly increasing in T), so long as the corresponding increase in principal utility is large enough to justify the payments. We then show that the princilal-optimal CEP exactly characterizes the value (averaged across timesteps) that the principal can achieve in the limit T + oo:
Theorem 1.2 (Informal version of Theorems 5.2 and 5.3). Let F (I) be the objective value for the principal in the principal-optimal CEP in game I. Then, against no-regret agents,
even knowing the game I exactly, the principal cannot achieve time-averaged value better than (T) - poly(M) 112, and
with no prior knowledge of the agents' utilities, there exists an algorithm for the principal to achieve time-averaged value at least F (T) po) 1/44
All our algorithms are implementable by the principal in coly(M) rumning time. To our knowledge, our Result is the first positive result for -uility-larming with arbitrary no-regret agents. Our Result 2 is the first in steering any no-regret agents without prior knowledge of their utilities, and the first exact characterization of the optimal value achievable by the principal in the steering problem.
2

---

Published as a conference paper at ICLR 2026
1.2 RELATED RESEARCH
Steering agents to achieve desirable outcomes is an important subject of study in economics, com- puter science, and control theory (e.g., Monderer & Tennenholtz (2003); Zhang et al. (2024); Canyakmaz et al. (2024); Yao et al. (2025)). In particular, Zhang et al. (2024) introduced the prob- lem of steering no-regret learners via payments. Critically, most prior works on steering assume that the principal knows the agents' utility functions. We study how the agents' utility functions can be learned, the solution to which will serve for any downstream applications including steering.
Besides the aforementioned works, another literature about learning agents' utility functions from their behavior is learning Stackelberg games, where the principal cannot pay the agents but can in- fluence the agents' actions by changing its own strategy, and the agents respond myopically (Letch- ford et al., 2009; Peng et al., 2019) or by learning algorithms (Haghtalab et al., 2022). Strong impossibility results are known for this problem: without regularity conditions without knowing the details of the agents' learning algorithms, the principal cannot learn the agent's 's utility function (Zhang et al., 2025). In contrast, we consider setting where the principal gives payments but does not take actions. We show that the use of payment makes a significant difference: the principal can now learn the utility functions of any no-regret agents without knowing their behavioral details.
Even with payment, the problem of learning from learning agents is still challenging. As we will discuss more Section 4, key obstacle the oonfforgessulness of agents' no-regret algorithms. The payment given to the agents in the past affect their future behavior. Non-forgetfulness is a known issue in aggent learning dynamics (Wu al., 2022: Cai al., 2024; Scheid et al., 2024). We overcome this obstacle by designing a zero-sum game- based learning algorithm for the principal and using signals to influence agents, without requiring the agents' algorithms to be forgetful.
Our use of signals to influence agents is inspired by information design (e.g., Kamenica & Gentzkow (2011)). In fact, Feng et al. (2022); Bacchiocchi et al. (2024); Alanqary et al. (2026) studied how to learn agents' utility functions by providing signals to shape agents' beliefs and behaviors in repeated games. While they consider myopically best-responding agents, we allow any no-regret learning agents, a more challenging setting necessitating the combination of signals and payments.
The literature on playing against no-regret agents studies how the principal should play game if they know the agents' utilities and some properties of the agents' algorithms (e.g., Braverman et al. (2018); Deng et al. (2019); Mansour et al. (2022); D' Andrea (2023); Lin Chen (2025); Arunachaleswaran al. (2025)). For example, Deng al. (2019) show that, if agents run based no-regret algorithms, then the principal can gain more than the Stackelberg value in a Stack- elberg game. Our algorithms and setting, on the other hand, consider worst-case no-regret agent behaviors. While most of the cited papers consider principal-agent problems with a single agent and with no payment, we consider arbitrary payment-argumeented multi-agent games.
2 PRELIMINARIES
Notations. Throughout this paper, Ô and 5 hide factors logarithmic in their argument. The symbol [n] denotes the set of positive integers (1....,n} n). The notation S& y means f s O(g), and f ス means f 2 2gg). For a vector v E Ih" its i-th component is denoted by v|i] or u, Vector of ones and zeros 1 (1,.... 1) and 0 (0, (O.....O) 0). I(-) is the indicator function, ie.. for statement p, [(pp = 1 if p is true and 0 if p is false.
Normal-form games. A normal-form game r = (n, A, U) consists of set of n agents, or players, which we will identify with the set of integers [n]. Each agent i has an action set A, of size m, 2 2.
We will let m == max; m, and M = II, m,- A tuple a E A == Ai x ... x An is an action profile. Each agent has a utility function U, - [0, 1]. denoting the utility for agent i when the agents play action profile a E A. A mixed strategy of agent is distribution æ; E (AA)). We will overload the utility function U, to accept mixed strategies, so that U.(xI..... 2n.) is the expected utility for agent i when every agent j E [n] independently samples aj ~ Ez. As is standard in game theory, we use -i to refer to the tuple of all agents except i. For instance, U,(a,, a.)) is the utility of agent when agent i plays action af E A; and other agents play a A_ Xzzi Az.
3

---

Published as a conference paper at ICLR 2026
No-regret learning. In no-regret learning, learner has convex compact strategy set X' and interacts with a possibly adversarial environment. On each timestep t. the learner selects a strat- egy x' E X. Simultancously, the environment, possibly adversarially, selects a linear utility vector u' E RR", which we assume to be bounded: (u', .z) S 1. The learner's regret after 7 timesteps is R(T)- maX Et= (u', =²). We say that the learner is running a no-regret algorithm if its average regret R(T)/T - 0 in the limit T + xo for all possible sequences (u'....,u")
I"",
well-known no-regret algorithm for general strategy set X' projected gradient descent/ascent (Zinkevich, 2003). Projected gradient ascent selects x² E X arbitrarily, and for every timestep t > 1 sets x² = =xx[='=1__ + "yu' 1 where 1Ix the -2-projection operator into X. With step size = B/VT),, where B is the fz-diameter of X' and bounds the f--norm of u', the algorithm achieves a regret of R(T) S BGVT.
To apply no-regret learning games, each agent runs no-regret algorithm over their mixed strat- egy set X = (m.). For this special case, the most common algorithm is the multiplicatiie weights update (MWU) algorithm (e.g., Freund & Schapire (1999)), which sets x' x exp(1) E.s, u²), where 7 / /oggmm)))))/mommm is appropriately-chosen step size and exp(-) is the element-wise expo- nential function. Multiplicative weights achieves regret bound R(T)) S Volog m..
3 OUR PROBLEM: LEARNING FROM LEARNING AGENTS
We study a setting where the principal does not initially know anything about the agents' utility functions U; except for boundedness. The principal knows the number of agents and their action sets A,, oversees the agents playing the game repeatedly over T rounds, and can provide payments and signals influence the agents' behavior, order to learn the utility functions of the agents. More formally, in each round t 1, I....T, T, the following events happen in order:
1. The principal selects payment function P. A + [0, B] for each agent i, where B is large constant.' The payment (a:) ) is added to agent i's reward, creating new game r with utility functions given by (f(()) == U:(a) + P (a:).
2. The principal sends signal s E S; each agent i.
3. Observing of (but not P.), each agent i selects mixed strategy ot E A(A.).
4. The principal observes the joint mixed strategy x'. Each agent i gets reward U. (xx).
Agents' contextual no-regret learning We assume that each agent selects of using a no-regret learning algorithm, or more precisely, contextual no-regret learning algorithm where signals are contexts and agents achieve no regret given any signal/context. Formally, there a (possibly game- dependent) constant C' < poly(M) such that, for every agent i, every signal s; S,, every time step t ts T.
Rt = max o,EA,
Σ TSES =
-T) s CVT.
(1)
One way to achieve this guarantee is for each agent to run |S independent no-regret algorithms, one for each signal. However, we do restrict to any specific algorithms: agents can run any algorithms satisfying the above no-regret property, such as projected gradient ascent, MWU, Exp3, and so on. particular, agents can run full-feedback or bandit-feedback no-regret algorithms; our results are unaffected. Indeed, the agents' learning algorithms need not even be independent; they could choose their actions using a centralized algorithm. As typical no-regret algorithms require knowledge of the utility functions (they operate on the feedback received after each round), the agents can also be initially ignorant of their own utility functions U,, just as the principal is.
not
our positive results will only require B = 2, since utility functions are bounded by 1. A nytime no-regret is not strong requirement. We show in Appendix B. that any algorithm with the usual no-regret guarantce under adversarial environments automatically satisfies anytime no-regret.
4

---

Published as a conference paper at ICLR 2026
Mixed strategies and agent randomization Our model stipulates that the principal observes the full joint mixed strategy x', instead of a sampled pure strategy profile a' ~ x'. This stipulation, however, is not at all vital and could be removed with only minimal effect on the results. In particular, suppose that each agent i, instead of announcing a mixed strategy x; in each round, samples an action of ax and announces the "mixed strategy" that assigns all mass af- Then the principal only observes a. The difference now is that, since the agents are randomizing, the regret bound (I) cannot hold deterministically; there will be some stochastic approximation error term that can be bounded by one can think of the results of this paper as conditional on the gegh-prbabiility event that (1) holds.
Hoeffding inequality, so (1) only holds with high probability. In that setting,
In particular, lower bounds that apply to the setting where the principal only observes the realized action profile also apply to the setting where the principal observes the mixed strategy profil. We will use this fact freely to prove lower bounds, in Theorem 4.4.
Our goal We aim to design algorithms for the principal to learn the agents' utility functions U; by designing the payment functions P and signals st for any no-regret learning agents. However, this goal as currently stated is impossible, because agents" regrets are only affected by the utility differences between actions, namely, U; a_;) - U2 (a( a-i), and the behaviors of typical no- regret algorithms (such as MWU) only depend on those differences. In other words, if we create another game I' with Ü (a; a-;) = (2 a-1) + (a-a)) for all E A, where W; A-; + R is an arbitrary function not depending on agent i's action, there is no way to distinguish I from I using only agents' behavioral data that is, games I' and I' are strategically equivalent. Thus, can only determine utility functions up to strategic equivalence.
Formally, given a game I and precision E, we say that the principal's 's algorithm g-learns the game r if it outputs utility functions U; A - IR such that there exist functions W; A_ - R satisfying
Ui((a) W.(a..) -.((a) Se, Vi [m], Va A.
The goal of the principal is to e-learn I' in few rounds possible. Learn game up strategic equivalence is sufficient for most practical purposes. For example, the sets of s-Nash equilibria and e-correlated equilibria invariant under strategic equivalence. Learning under strategic equiva- lence also enables steering the learners toward certain outcomes, an application in Section 5.
While our paper focuses on the problem of minimizing the number of rounds it takes to learn the game, an alternative goal might be to minimize the total payment to do so. However, we show in Appendix A that the minimal achievable payment upper-bounded and lower-bounded by the minimal number of rounds up to constant factors, so these two problems are quantitatively similar.
4 LEARNING GAME BY PAYING NO-REGRET LEARNERS
We design efficient algorithms for the principal s-learn a game by paying no-regret learning agents. We will start with the single-agent case to illustrate the main ideas of our algorithms, before proceeding to the multi-agent case.
4.1 THE SINGLE-AGENT CASE
In the single-case case (n 1), it is more convenient view the single agent's utility function as a vector u E [0, 11m and similarly the payment p [m]] - R as vector p' E R and total utility subtract the average utility of all actions from the utility of u' := u + p². To simplify notations,
each action: u <- u (1,m] 1, so that u. E [-1,1]] and (1, u) = By the discussion before (2), this does not change the principal's 's learning problem. Our algorithm will not need signaling in the single-agent case, so it will be enough to set [S,] = 1.
The main challenge of learning game from no-regret agent is the history-dependency of the agent's 's behavior. To fix ideas, suppose the agents has two actions A and with unknown utility gap UA ug A 0. A straightforward attempt to learn the gap A is to try different payments for action B (while paying for action A) in a binary-search manner: the payment at which the agent just starts to play action B should reveal the value of A. However, that approach does not work for
5

---

Published as a conference paper at ICLR 2026
no-regret learning agent because no-regret algorithms may not respond instantaneously to changes to the payment function. Historical payments affect the agent's 's future behavior. Moreover, the agent may incur negative regret over time, making it difficult to learn anything from the agent's behavior on subsequent rounds. For example, an agent has regret - K for all actions, then one cannot say anything all about how the agent will behave in the next K rounds.
The key idea of our algorithm to imagine the principal and the agent as playing a zero-sum game where the principal selects the payment function p from some set to be specified later, the agent selects mixed strategy æ E A (m), the agent's utility is given by (u + 2), and the principal's utility is (u + p. x). Call this game o. In particular, by setting = {p [0, (1. m), the gero-sum game To has the following property:
Lemma 4.1. In the zero-sun game To, every e-Nash equilibrium strategy for the principal has the form
u 2, where || I 4ms.
Proof. Setting p = 1 - u guarantees (u + p, x) = (1. x) for every a E (m)) Thus, in every e-Nash equilibrium, the agent's 's utility is at most 1 + Now suppose for contradiction that (p, x) is an e-Nash equilibrium with |pp + u - 1 > 4ms. Then since (p- + u - 1) = 0 by construction, there must be action for which (p agent has an e-profitable deviation to action a.
[a] > 2s, iee, (u + p)([]] + 2s. But then the
well known that no-regret learning algorithms converge on average Nash equilibria zero- sum games. In particular, if both principal and agent run no-regret algorithms, and Rg is the regret after T timesteps for the principal, then the average principal strategy + E p' is e-Nash cquilibrium for E X (Ro + CVT)/T. Here, we use the projected gradient descent algorithm for the principal. Note that, although the principal's utility function p + (u + p, x) depends (which the principal does not know), the gradient of the principal's utility function is =x, which does not depend of u. The resulting algorithm is formalized in Algorithm 1.
Thus, the principal can run projected gradient descent without the knowledge
A Algorithm Principal's learning algorithm for single no-regret agent
1: p² <-1
2: for each time 1,..., do
3: principal selects payment vector p' E P. observes strategy æ' played by the agent
4: principal sets p IIppp' no'l > /m/T is the step size
5: return- -4 -
Theorem 4.2. Algorithm 1 e-learns any single-agent game in T =m rounds.
Proof. Let II= be the average payment. From the preliminaries, the regret bound of the principal is given by Ro < BGVT where S /m and G 1. By the previous paragraph, the average play between the principal and the agent is Ro+CVT -Nsh equilibrium. Then, by Lemma 4.1, we have
E p + u 111.- S |1 u 1111 S 4m BotCVT m (C + mm).
Solving for T yields the desired result.
The zero-sum-gant idea of Algorithm is surprisingly simple and powerful. The principal moves the payment vector in the opposite direction of the agent's 's mixed strategy every round, and the neg- ative average payment vector ultimately becomes an accurate estimate of the agent's utility vector. This idea works for any no-regret learning algorithm of the agent.
Another possible method to overcome distory-dependee vector is changed, send to implement a binary-searee algorithm to leam the game. However, that would require m log(1/s) signals, one for each step of the binary search, and the total number of rounds would be at least
is to use signals: whenever the payment signal to the agent to disentangle from the history. Signaling allows us

---

Published as a conference paper at ICLR 2026
C2m/E2 log(1/e), whereas our Algorithm 1 achieves the better dependence of 1/E², saving logarithmic term, without using signals.
4.2 THE MULTI-AGENT CASE
We then consider the multi-agent case. Our algorithm for the multi-agent case will combine the single-agent algorithm with signaling. Intuitively, our algorithm uses signals to induce the action profile a-v among other agents without increasing their regret by much. More precisely, the signal set as S, == { where 1 is special signal indicating that i's utility the one being learned at the moment. For every action profile a-i A- we send signal I agent and the desired action új for each agent j # to learn Ui(- a-i). This idea is formalized in Algorithm 2.
set
Algorithm 2 Principal's 's learning algorithm for multiple no-regret agents
f+
2:
for every agent i 1...., do for every action profile a A_; do
3:
4:
p² 1 Rr.
5:
for timestep f = 1, 1,...,,.. do
6:
principal sets P.( p+] and (a = 2I{a, = . for every
7:
principal sends signals se = and s) ag for every j #
8:
principal observes profile x' played by agents
9:
principal sets p < Ip ip narl]
b 1 = v m2 is the step size
10:
1 t ++1
Ú,(, ā-;) + - Et-p
11:
return Ú
Theorem 4.3. For some choice of parameter L,, Algorithm 2 e-learns any game in poly M.C)
rounds.
Proof Sketch. Since the principal always gives large reward to agent who obey signals other than I, agent will almost always obey such signals. Thus, agents other than agent will almost always play profile a-;. This allows the principal to learn U,(, a_;) using the one-player algorithm from Theorem 4.2. The formal proof is deferred to Appendix C.
Signals are vital to this analysis. Without them, it would be possible for players to incur large neg- alive regret, which harms the learning process because it allows the players to "delay" the learning until their regrets once again become non-negative. For example, if we were execute rithm without signals, then by the time T, at which the outer loop reaches agent n, agent n could have (TT,,, x (0)) regret for every action, making it impossible to say anything about how agent n will act for the next Q(T n (0)) rounds. Using signals allows us to separate out the regret of agent n in previous rounds from the regret of agent when its own utility function is being learned.
algo-
4.3 LOWER BOUND
We now turn to lower bounds. particular, we show a lower bound that matches Theorem 4.3 up to the exponent on M.
Theorem 4.4. the no-regret model, any algorithm that e-learss a game must take at least Ca
max(9(nM)) log 1 422 rounds.
Proof sketch. If every agent plays pure action each round, then the principal only observe log(M bits of information at each round. Learning the game requires 2(nM) bits of information, so need least ((nM) log rounds in total. On the other hand, e-learn the game from C agents' behavior, the agents' time-average regret VT must be smaller than 2c, so T is at least 422- The full proof is in Appendix C.2.
C²
n

---

Published as a conference paper at ICLR 2026
Theorem 4.4 shows that it is impossible to exponentially improve the dependence any of the parameters in Theorem 4.2. For example, it implies that there can be no algorithm taking C²/E² M M1-9(1) rounds, because that would contradict the lower bound for constant & and suffficiently large M. We leave it as interesting open question to close the polynomial gaps between the lower and upper bounds presented here.
STEERING NO-REGRET LEARNERS BY LEARNING THE GAME
main motivating application of our result is the problem of steering no-regret learners to desirable outcomes, introduced by Zhang et al. (2024) who assume that the principal knows the game. In this section, we explore the steering problem with unknown agent utilities.
5.1 CORRELATED SIGNALS AND PAYMENTS
In this section, we make two modifications correlated; (2) we allow payments to each agent to depend not only on agent i's action, but also on the signals and actions of other players. These two assumptions are proven to be necessary for the steering problem by Zhang et al. (2024). Formally, each agent has finite signal set S. As with x Sn for the joint signal space. On each round I, the principal
model in Section 3: (1) we allow the signals to be
actions, we will write S S₁ first commits to both signal distribution μ² E A(S) and payment function P. x A + [0, B}. The agents then select their strategies, which are functions of S; + AAA)). Then, the principal draws the joint signal sf = (si,.... s n², and each agent plays æ = (s.). As before, we assume that agents have no regret for each signal: for every signal s; E S,,
(t, (t) = max Σ a;EA; E88
Σ
4 (²(s)
('(s)(T((s (T a, or,,,,,,",,,, d', U7 (7, (s, (s)) CCV..
where now U7(s, = U.(a) as..aa).
We remark that this correlated model gives strictly more power to the principal than the previous model: if restrict the principal to setting μ² to be deterministic distribution and P to be dependent on agent i's action a, only, the two models coincide. Therefore, the previous positive results, particularly Theorem 4.3, apply this model as well.
The reason for the difference in the models is that the correlated signaling model makes clear in what formal sense the signals are private: the agents' strategies of can only depend 8;, not other agents' signals. This will allow us to steer to correlated equilibria.
5.2 WHAT OUTCOME SHOULD WE STEER TO?
The steering problem, defined by Zhang al. (2024), stipulates for their main results that the principal knows in advance, or be able to compute, the desired outcome that we wish to induce. Of course, in our setting, such stipulation is unreasonable: the principal does not initially know the agents' utilities in the game I,, so it cannot know what outcome it wishes to induce. We thus take more direct approach: we try to maximize the average reward, less payments, of the principal. That is, we will assume that the principal has utility function Un A - R, and we will attempt to optimize the principal's 's objective, defined the principal's utility minus payments:
F(T) Σ T 1' Uo(o'(s'))
Σn P! P!(ss)
To analyze the above objective, we introduce solution concept called correlated equilibrium with payments (CEP). A CEP is correlated distribution of signals and payment functions that satisfies the usual incentive compatibility constraints. Formally, we have the following definition.
Definition 5.1. correlated profile with payments is pair (p, P) E A(A) x [o, [m]xAx The vector P consists of payment functions P: A x A + [0, B). where P. a) is the payment to
Herr, let S, A,. This is WLOG due revelation principle argument (Appendix D.
8

---

Published as a conference paper at ICLR 2026
agent i given joint signal A and joint action A. Given (H, P). the objective value for the principal is defined as
(ola) E P(a,a))
F(, := amp
An e-correlated equilibrium with payments (E-CEP) is pair (u, P) satisfying the incentive com- patibility (IC) constraints: for every agent [n] and deviation function di A; + A,,
U a, oi(a,) amp
Uf (a. a)] S..
where U. (8, a) :- U.(a) (i a). An O-CEP is called a CEP.
Let (T) be the principal's objective value under optimal CEP of game
max F (T) P): a CEP of game
F(u, P).
We show that (T) an upper bound on the maximum value attainable by a principal our learning model. Relatedly, Deng al. (2019); Lin & Chen (2025) show that principal cannot achieve more than the Stackelberg equilibrium objective against a single no-regret agent in games with payment. Our result generalizes to multiple no-regret agents and games with payment. The proof of Theorem 5.2 is in Appendix D.3.
Theorem 5.2. Let be any game, and suppose the signal sets have size [S.| I poly(m). Then there exist uncoupled no-regret learning algorithms for the agents such that, for any principal algorithm, the principal's 's objective value (T) is bounded above by F (T) + o(/vTT).
5.3 STEERING TO OPTIMAL CEP
We now show that the principal can achieve the optimal CEP objective F*(() (T) in the limit T oc. The algorithm (Algorithm works in two stages. In the first stage, the principal uses Algorithm to learn the utility functions of the agents. Then, the principal computes an optimal CEP and steers the agents to The steering algorithm is adapted from Zhang et al. (2024), and presented in full here for the sake of self-containment. Notably, since the principal Iearns the game up to an error e > 0, it must give extra payments of least to ensure that agents do not deviate. Theorem 5.3 shows that the principal can learn to steer agents to achieve the optimal objective F (T) at rate of poly(M, /// The proof is given in Appendix D.4.
Algorithm 3 Principal's algorithm for steering without prior knowledge of utilities
1: using Algorithm 2, estimate the utility functions to precision
2: compute optimal CEP (fi", P*) of the estimated game [
3: for remaining rounds do
(a, a) +
if 8 = a if ai i + a_i. otherwise
4: set μ² = n= and (s. = 2
Theorem 5.3. For appropriate choices of parameters L (from Algorithm 2) and p. Algorithm guarantees principal objective F(T)+ 2 F (T) poly(M, CT/L// average in T rounds.
CONCLUSIONS AND FUTURE DIRECTIONS
We showed that a principal can efficiently learn the utility functions of agents in games through pay- ments and signals, and applied our algorithms to achieve optimal steering without prior knowledge of the game We gave upper and lower bounds for both problems. Our results apply to arbitrary no-regret agents. We leave few directions for future research:
We did not optimize the polynomial dependencies on M. so our upper and lower bounds are off by poly(M) factors. We leave it interesting open problem to close these gaps.

---

Published as a conference paper at ICLR 2026
Our techniques specialized to normal-form games, and require, for example, that the principal observe the strategy x' of the agents at every timestep. This may no longer be a reasonable assumption in, e.g. extensive-form games, where may wish instead assume that only observe on-path agent actions. We leave it as future work to extend our results to such settings.
While our single-agent utility-leariing algorithm only uses payments, our mutli-agent algorithm additionally uses signals. The limit of learning agents' utility functions by payments only, without using signals, is worth exploring.
Similarly worth exploring is the problem of steering without utility learning. We proved that agents' utility functions require ((nM)) log rounds to Iearn. Can we avoid this bottleneck by steering agents desirable outcomes without learning their entire utility functions?
ACKNOWLEDGEMENTS
B.H.Z. was supported by the CMU Computer Science Department Hans Berliner PhD Student Fel- lowship. T.L. was supported by a Siebel Scholarship. Y.C. is supported by National Science Founda- tion grant IIS- (IS-2147187 and by Amazon. T.S. is supported by the Vannevar Bush Faculty Fellowship ONR 100014-23-1-2877 National Science Foundation grants RI-231 12342 and RI-1901403, ARO award 1911NF2210266, and NIH award A240108S000
REFERENCES
Arwa Alanqary. Zakaria Baba, Manxi Wu, and Alexandre M Bayen. Learning to recommend in unknown games. arXiv preprint arXiv:2602. 16998, 2026.
Eshwar Ram Arunachaleswaran, Natalie Collina, and Jon Schneider. Learning to Play Against Un- known Opponents. In Proceedings of the 26th ACM Conference on Economics and Computation, pp. 478-504, Stanford University Stanford CA USA, July 2025. ACM.
Robert Aumann. Subjectivity and correlation randomized strategies. Journal of Mathematical Economics, 1(1):67-96, 1974.
Francesco Bacchiocchi, Matteo Bollini, Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Online bayesian persuasion without a clue. In Neural Information Processing Systems (NeurIPS), 2024.
Eyal Beigman and Rakesh Vohra. Learning from revealed preference. In Proceedings of the 7th ACM conference on Electronic commerce, pp. 36-42, Ann Arbor Michigan USA, June 2006.
ACM.
Mark Braverman, Jieming Mao, Jon Schneider, and Matt Weinberg. Selling to No-Regret Buyer. In Proceedings of the 2018 ACM Conference on Economics and Compulation, pp. 523-538, Ithaca NY USA, June 2018. ACM. ISBN 978-1-4503-5822933
Yang Cai, Gabriele Farina, Julien Grand-Clément Christian Kroer, Chung- Wei Lee, Haipeng Luo, and Weiqiang Zheng. Fast last-iterate convergence of learning in games requires forgetful al- gorithms. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024.
layda Canyakmaz, losif Sakos, Wayne Lin, Antonios Varvitsiotis, and Georgios Piliouras. Learning and steering game dynamics towards desirable outcomes. arXiv preprint arXiv:2404.01066, 2024.
Xi Chen, Xiaotie Deng, and Shang-Hua Teng. Settling the complexity of computing two-player Nash equilibria. Journal of the ACM, 56(3):14, 2009.
Maurizio D' Andrea. Playing against no-regret players. Operations Research Letters, 51(2):142-
145, March 2023.
Constantinos Daskalakis, Paul Goldberg, and Christos Papadimitriou. The complexity of computing a Nash equilibrium. In Symposium on Theory of Computing (STOC), 2006.
Yuan Deng, Jon Schneider, and Balasubramanian Sivan. Strategizing against no-regret learners. In Neural Information Processing Systems (NeurIPS), 2019.
10

---

Published as a conference paper at ICLR 2026
Yiding Feng, Wei Tang, and Haifeng Xu. Online Bayesian Recommendation with No Regret. In Proceedings of the 23rd ACM Conference on Economics and Computation, pp. 818-8188111 Boulder CO USA, July 2022. ACM.
Yoav Freund and Robert Schapire. Adaptive game playing using multiplicative weights. Games and Economic Behavior, 29:79-103, 1999.
Nika Haghtalab, Thodoris Lykouris, Sloan Nietert, and Alexander Wei. Learning in stackelberg games with non-myopic agents. In ACM Conference on Economics and Computation (EC), pp. 917-918, 2022.
Emir Kamenica and Matthew Gentzkow. Bayesian Persuasion. American Economic Review, 101 (6):2590-2615, October 2011.
Volodymyr Kuleshov and Okke Schrijvers. Inverse game theory: Learning utilities in succinct games. In International Workshop On Internet And Network Economics (WINE), pp. 413-427. Springer, 2015.
Joshua Letchford, Vincent Conitzer, and Kamesh Munagala. Learning and approximating the opti- mal strategy to commit to. In International Symposium Algorithmic Game Theory, pp. 250- 262. Springer, 2009.
Tao Lin and Yiling Chen. Generalized Principal-Agent Problem with a Learning Agent. In The Thirteenth International Conference Learning Representations, 2025.
Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan. Strategizing against learners in bayesian games. In Conference on Learning Theory (COLT), 2022.
Dov Monderer and Moshe Tennenholtz. k-Implementation. In ACM Conference on Electronic Commerce (ACM-EC), pp. 19-28, San Diego, CA, 2003.
Binghui Peng, Weiran Shen, Pingzhong Tang, and Song Zuo. Learning Optimal Strategies to Com- mit To. Proceedings of the AAAI Conference on Artificial Intelligence, 33(01):2149-11 2156,, July 2019.
Antoine Scheid, Aymeric Capitaine, Etienne Boursier, Eric Moulines, Michael Jordan, and Alain Durmus. Learning to Mitigate Externalities: the Coase Theorem with Hindsight Rationality. In Advances in Neural Information Processing Systems, volume 37, pp. 15149-15183, Curran Associates, Inc., 2024.
Jibang Wu, Haifeng Xu, and Fan Yao. Multi-Agent Learning for Iterative Dominance Elimination: Formal Barriers and New Algorithms. In Proceedings of Thirty Fifth Conference on Learning Theory, volume 178 of Proceedings of Machine Learning Research, pp. 543. PMLR, July 2022.
Fan Yao, Yuwei Cheng, Ermin Wei, and Haifeng Xu. Single-agent Poisoning Attacks Suffice to Ruin Multi-Agent Learning. In The Thirteenth International Conference on Learning Representations, 2025.
Morteza Zadimoghaddam and Aaron Roth. Efficiently Learning from Revealed Preference. In Internet and Network Economics, volume 7695, pp. 114-127. Springer Berlin Heidelberg, Berlin, Heidelberg, 2012. Series Title: Lecture Notes in Computer Science.
Brian Hu Zhang, Gabriele Farina, loannis Anagnostides, Federico Cacciamani, Stephen Marcus McAleer, Andreas Alexander Haupt, Andrea Celli, Nicola Gatti, Vincent Conitzer, and Tuomas Sandholm. Steering no-regret learners to desired equilibrium. ACM Conference on Economics and Computation (EC), 2024.
Yizhou Zhang, Yian Ma, and Eric Mazumdar, Learning to steer learners in games. In Forty-second International Conference Machine Learning, 2025.
Martin Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML-03), pp. 928-939666 936, 2003.
11

---

Published as a conference paper at ICLR 2026
A MINIMIZING PAYMENT
Most of our paper focuses on e-learning a game in as few rounds as possible. This section discusses an alternative goal: e-learning game while minimizing the total payment to the agents. We show that the minimal achievable payment is upper-bounded and lower-bounded by the number of rounds up constant factors, so the payment minimization problem is quantitatively similar round com- plexity minimization.
Formally. we define the payment complexity PC(n, E) to be the minimal total payment required to e-learn a game with agents (in the worst case over all games), and the round complexity RC e) be the minimal number of rounds to so. Then, we have:
Proposition A.1. There exist games and no-regret agents such that
QRCC(n - 1,+)) s FC(n, s 0n(n (C((,))
Proof. The inequality PC s) < (n RC(n, e)) is straightforward because the payment to each agent is bounded by ((1) at each round.
To prove 22 (RC(n-
I PC(n, E), we reduce the utility learning problem with n agents to the problem with n agents. Let I n-1 be an (n 1aageet game with utility functions U1, U1,.... Un- 1- Consider an n-agent game I', where the n-th agent has two actions A, = {0. 1}. If the n-th agent takes 1, then the first n 1 agents all obtain utility regardless of their actions; if the n-th agent takes 0, then the first n - agents have the same utility functions as in game -n Further assume that the n-th agent's utility depends on his own action only, and in particular, (a, 0) = 0 and Un (a,, 1) 1, so the n-th agent takes action 1 by default. Intuitively, in order to learn the utility functions game In. we have to incentivize the ri-h agent to play action by paying him 1 at each round, so that we can learn the first
agents' utility functions. This means that the total payment lower bounded by the number of rounds to learn the (n agegtt game.
Formally, let ALG be algorithm for learning Fn with payment complexity PC(n.s). We use ALG to construct an algorithm to learn -n as follows:
At each round L, do:
Obtain payment functions Pt ... pt n- Pt from ALG.
If (a = 0) < (a, = 1) + 1. then let a = and of argmax (a:) for i (1, [l,.....,T, n - 1}. Return the action profile (a'... af))) to ALG.
If Pf 0) > Pt (a, 1) 1, then let a", 0 and send the payment functions Pf....., Pt n-1 to the first n - agents. Observe their actions a²,, in game Ta-1- Return (a'n dt)) to ALG.
Obtain utility functions Ü.,..., Un from ALG. Output Ú1(5an an = O), Un-1(; -),,..,,nnI(.. 0).
By definition, if ALG outputs Ú,,..., Ün that are E-close to the utility functions of I,, then the outputs Úi(,, an 0). O).... Un ag = 0) are s-close to the utility functions U1, Un- of Tn-1. Each time "P (a, = 0) 2 P (a, = 1) + 1" happens, agent n takes action a; 0, we pay at least 1, and we interact with the first PC(n,)) Z RC(n 1,
agents once. So, the total payment is at least
B DETAILS OMITTED FROM SECTION 3
B. ANYTIME No REGRET
Our condition no-regret learning is that, for every signal 8; (here omitted superscript for notational clarity), the regret R, is bounded by CVT for every timestep t < T, not just at t = T as is conventionally required by adversarial no-regret algorithms. This is not a significantly stronger requirement:
12

---

Published as a conference paper at ICLR 2026
Proposition B.1. If a (possibly randomized) adversarial no-regret algorithu satisfies (T(T) $ B with probability - 6 against any adversary, then with probability 6 it also satisfies Rt(t) _ B simultaneously for all t < T against any adversary.
Proof. Suppose not, i.e., suppose that there is some adversary A such that, with probability > 6, there exists some t < T for which R₂ > B. Then consider the adversary A'' that acts as follows. At every time f, if (t - 1) I B, it copies A. Otherwise, it outputs u* 0 for all remaining timesteps. the latter case, which by definition occurs with probability ò, adversary A' will also achieve (T) > B.
C DETAILS OMITTED FROM SECTION 4
C.1 PROOF OF THEOREM 4.3
As in Theorem 4.2, we will assume without loss of generality that Ea,es, Ui(a;, a-1) 0 for all agents i and opponent profiles a.-i.
We first claim that, for any agent and any given signal s ag A,, the total probability mass that plays actions other than a; is bounded by CVT. see this, note that whenever the principal sends signal a, the payment is always set such that (a,, a_;) 2 1 1+ (2 a-i). Thus, the number of times i does play of a, quantity lower-bounds the regret R(T, o.). The claim follows from the regret guarantee R(T, a;)) S CVT.
We will refer to the iterations of the inner loop over action profiles a as phases. Fix an agent i, and number the phases for that agent using integers {1, ... Mi = IIiy: m;}. corresponding
strategy profiles a!_ i-..... a A-i. Let Ti(k) (T, (K), ..... Tk(k) be the set of timesteps in agent i's ktth phase. The length of each phase is [Tx(k)] L. Let Bx be the total probability mass placed by all agents j * i on strategy profiles other than at throughout phases 1...., K. By the previous claim, we have
BK EE
(I-))))()))
Σ
(1-x)((a))) s umCVT.
(E
jæi
RSKKETT(M))i
By the principal's regret bound each phase, we must have
Σ
(z a",)= = Σ Ul(2), a",))
:) + Σ (x())
(ET((M)
BET((K)
LET((K)
Σ
U,(al,a*,) Σ
[1 U.(WI, am,)] + Ro
(k)(()
(ET.(K)
= L Ro
where the inequality follows from the facts that 1) the principal's regret is bounded, 2) P!()) 1 U,(-, at is valid unilateral deviation for the principal.
Fix some K s M; and a; E Ai. By the anytime regret bound of agent i under signal I, we have
Σ
Σ
U3 x'.) + (TT(k,,,,
KSK,IET,(K))
< 2Bkx +
Σ
Ul(2i, a + (TT())).
kSK,IT((K)
$ 2 K Ro) + nCVT.
Moving K.L the left and writing (ai Ui(ai, (',aa,xx''))) + (a.)).
Σ
-1 1| 1 I (Rok 3nmCvT).
Ulla, x + (((()) -
k=1 (ET.(K)
denoted by (k..a)
13

---

Published as a conference paper at ICLR 2026
The enror need to bound is (k,, -)looo Ee, (k( :) = 0 by definition, it follows that
Since the above inequality holds for any ds, and
K
K Σ R=1
Σ (k
Σ rET((K)
Ui(a; + (a.) - 1 m R 33mCCT)
max a,EA,
L
By triangle inequality, we have
2m S
(l; =
Σ (( Σ s:(K,)))
RRM +3mmCTT)
k=1
Finally, substituting Ro S VmL and T SnML, I,, we arrive at
(k, )l X
VT. m 3/2 M n212m m m CMV/3)
Taking L O( m m to MC²
completes the proof, with 2 nM = O am M8+***++nn +n M²0²
C.2 PROOF OF THEOREM 4.4
We prove both terms in the max separately. For the first term, suppose that U²(1,-) .) 0 for all agents i, and U2(a;, a-i) ~ {0, 2e, 4e, 1) 4e,...,1) uniformly sampled from set of (2(1/)) possible utilities, where
i.i.d. for 2 I a S. my and a-ę E A-5. Thus the utility U is
n.M 2
(m, - 1)
II my j7t
Each utility function differs by 2c, it follows that g-learning a game sampled from this family entails exactly outputting the utility U. Suppose that, discussed in Section the no-regret algorithms always output pure strategies of E A.. Then on each round, the principal only observes a single action profile a E A, which only conveys log M bits of information. Therefore, e-learning the game takes at least
K (log(((()/ log M
n.M log(1/e)
log M
rounds, as desired.
[0 any function, and suppose that every agent plays according to utility function U, + Z; instead of U; using an algorithm with 2 V regret. Such agent incurs at most G + el' < CVT regret with respect to U,. Such an agent completely indistinguishable from an agent who has true utility U; + Zü and runs an algorithm with regret CVT,, and therefore the principal can never distinguish between these two possibilities. Since this is true for any Z,, this means that the principal cannot learn U, to accuracy better than
For the second term, suppose 8 C Let Z,
2VT
E S 2 Thus, T must be least C² for the principal to e-learn the game.
4.2
D DETAILS OMITTED FROM SECTION 5
D.1 REVELATION PRINCIPLE FOR CEPs
In this section, we formulate a general version of the revelation principle for CEPs.
Definition D.I (Non-canonical CEP). (non-canonical, agent-form) e-CEP is distribution ASS P A& for any player i and any map th A, + (AA)), we have
ASn) where P [0, x is the set of payment functions, such that,
UU (s. (ch de) (s U. ((s)) so.
P
The objective value given by
[o(((())) - P(s, (({)))
14

---

Published as a conference paper at ICLR 2026
We say that is canonical if the payment function P ~ is constant, and for every player i, S: = A, and Ø; is the identity map. Note that canonical CEPs are precisely the CEPs according to Definition 5.1.
Proposition D.2 (Revelation principle for CEPS). Every CEP is equivalent to a canonical CEP, in the sense that, for every CEP n, there is canonical CEP (μl P)) achieving the same principal objective value.
Proof. Given CEP n, pl E ((A) be the distribution that samples (s, a and then samples and outputs ~ ((8). Then define P/ A x A + [0, B] by
P. a') (M.
E
Ps(s,a'),
where (s, P) ~ x|a denotes sampling (s, P) with probability proportional to x(s, P) o(als). Then note that, for any v; A, A,, we have
E 1U (a, vh((a),, amp ((t
E U.biia))..==((((ale)))
anp
E
amp'' P>rala
E
a P(6.)
a~o(s)
E (a.P
[U (s, (vs
Thus, if μ. is a profitable deviation for agent in (n', P'), then it is also profitable deviation in π.
But the non-canonical CEP does not have profitable deviations, so (μ', P') is also CEP.
D.2 ADDITIONAL PROPERTIES OF CEPS
We present some additional properties of CEPs.
First, optimal CEPs can be efficiently computed when the game known.
Proposition D.3. Given game I of size M, an optimal CEP (μ²,, P*) and its principal objective F* (T)) can be computed in poly(M))rn by a linear program.
Proof. Define change of variables
Qi(a:) = p(a:).
E
a.(a,a).
amopla;
That is, Qi(a;) the weighte total payment given to agent across all strategy profiles which agent is recommended action ag. Consider the following linear program:
Σ (la)ao(a)
Σ Qi(ai) s.t.
max n.Q.
aEA
1E(n]
a,EA;
Σ G.:EA_:
u(a)lUi(al,aa - - (a(a,) S E((ai)
E [n], , o E A
(3)
Σ (a,))) 50
Vi E [n]
Σ u(a)= =1
Vi [n], a, oj E Ai. This LP is equivalent to computing the optimal O-CEP because for any feasible solution (n. Q) of the LP, the payment functions defined by P, a) Q:(0:) and P( a') 0 a' + a together with a constitute a feasible O-CEP with the same objective value. This LP has (Mly(M) variables and constraints, the proof is complete.
0 0 Q:(a:) S u(a,)
[(a:)
15

---

Published as a conference paper at ICLR 2026
Second, show that the assumption that the payments can be signal-dependent is not innocuous, except when the payment at equilibrium is zero. There exist games where CEP with signal- dependent payment is strictly better than CEP with ugnal-independesn payment.
Proposition D.4 (Correlation does not help when no payments are allowed in equilibrium). The O-CEPs with Earoy P(a, a) 0 are exactly the correlated equilibria.
Proof. In the LP (3), this is equivalent to setting Q:(-) = 0 for every agent i, in which case (3) is just the LP characterizing correlated equilibria.
However, when the payment at equilibrium is positive, it is possible for signal-dependen payments to help the principal.
Proposition D.5 "Signal-dependen payments can help in general). There exists a game r, and principal utility function Uo. such that the optimal value of (3) is greater than the objective value of the optimal CEP in which P(s, a) depends but not
Proof sketch. In the normal-form game below, P1 and P2 play matching pennies, and the principal willing to pay a large amount to avoid a partieular pure profile.
X
00, 0,,0,1
0,1,0
Y
0,1,0 0,0,1
P1 chooses the row, P2 chooses the column. In each cell, the principal's utility is listed first, then Pl's. then P2's. Now consider the following CEP: The principal mixes evenly between recommend- ing (X, Y). X), and (Y, Y). If the principal recommends (Y, also promises a payment of 1 to P2 if P2 follows the recommendation X. This CEP has principal objective value -1/3, and no
sggnal-ndeepnnenn CEP can match that value. The full proof is given Appendix D.2.1.
O
In the language of Monderer & Tennenholtz (2003), a CEP with = Earp P(a) is called k-implementable correlated equilibrium." They show that all correlated equilibria are 0- implementable, but do not show the converse. Our results improve upon theirs by 1) showing the converse (Proposition D.4), and 2) analyzing the k case, in particular, by incorporating principal objective and showing how to compute the optimal CEP.
D.2.1
COMPLETE PROOF OF PROPOSITION D.5
We first show that the claimed CEP is actually CEP.
Conditioned on PI being recommended X, P2's action is deterministically Y. against which X is the best response for Pl.
Conditioned on Pl being recommended Y, P2's action is uniform random, against which Y a best response for P1.
Conditioned on P2 being recommended X, Pl's action is deterministically Y, against
which the principal's ''s promised payment of 1 makes X a best response for P2.
Conditioned on P2 being recommended Y, Pl's action uniform random, against which Y is a best response for P2.
It remains to show that the objective value 1/3 cannot be achieved by any CEP in which payments are signallindependent. We prove by contradiction. Suppose there is a CEP (μ. P) with signal- independent P that achieves objective value at least -1/3. Note that μ E A(A) is correlated
*Instead of our condition of ex-interim IC, Monderer & Tennenholtz (2003) insist on dominant-strategy IC, that is, they insist that U,"(s, (s, S,, a.,a.. 2 U/ (s, a) for every s and a. However, this requirement does not change anything in equilibrium, because one can always set P(s, a.. when S; = a; and * to be so large that playing becomes dominant. Indeed, Monderer & Tennenholtz (2003) do this to establish their results on implementation; Zhang al. (2024) do this in their steering algorithms; and we will do the same in Section 5.
16

---

Published as a conference paper at ICLR 2026
equilibrium of the game with utility function U + P. Because the principal's 's utility without the payment part is always non non-positive, for the objective to be at least -1/3, the expected payment to the two players Ea ((a) cannot exceed 1/3.
-00, we must have xxX, = We then analyze the incentive compatibility constraints for the two players:
Since Up(X,X'
When P2 is recommended X, P2 knows that P1 is recommended Y (because (X, X) is not possible), so in order to ensure P2 has no incentive to deviate from X to Y, we must have
U.5 XY) 2 U2 (Y = 0+ P2(X,X) 2 1+ Y)( = P2(X,X) 2 1.
Since the expected payment is at least μuY, P2 X) but is most 1/3, we must have X(Y, s 1/3.
When P2 is recommended Y, P2 believes that the recommendation to P1 is X and Y with probability μ(X,, Y and YY respectively, so to prevent P2 from deviation Y + X, the expected utilities of P2 under actions and X should satisfy:
xxx, Y)- (U2(X, () P3(X,
Y)) + (Y, (U2(Y,Y) + P2(Y
P2's expected utility when taking action Y given recommendation Y
2 (X,Y)) (U2(X, X) P2(X, X)) + (Y, (U2(Y, x) + (V,
P2's expected usility when taking action given recommeendation Y
((x, Y) ()) + +1+ P2(Y,
2 *(X, Y) (1+ PXX, + ((Y))) (0+ P2(Y,
,(X, Y) +(X,))
2 Y) ((X,)))(1+00)) (xX,,))))) V) -)(Y,))) -Y,,)) (1+
Because payments are non-negative and Xx) 2 1, the above implies M(X, Y) P) ((Y,Y) Pa(Y,Y)
2 (XX (1+ Pa(X,X)) +Y,,Y -(Y,)) > x)
So, the total expected payment P2 at least m(X, (X, Y) + u(Y, Y)P:(Y + (X 2 x(X, Y) XX,
(4)
When P1 is recommended Y. Pl knows that P2's action is X with probability v(Y,X) and Y with probability Y(, Y), so to prevent P1 from deviation Y - X, Pl's expected utilities under actions Y and X should satisfy:
x) (U, + PI + H(Y,Y) (U)( PiX,
P1's expected utility when taking action Y given recommendation Y ()) P((, + ((Y (U, + Pi(Y,)))
2 (Y,X))
(U)
Pl's expected usility when taking action given recommenddaiion Y
- (Y X) (00))(1111)) (1+ PI,Y, + *YYY) P((,Y)
2 (Y,
+ (Y,YY (1+
Since payments are non-negative, the above implies
xYY,x) X), + *YY +
(5)
(Y, PX( ((X,)) + ,(Y,Y) PI(YY) X(Y
- XX.,
Now, adding (4) and (5), the total expected payment to the two players is at least
Σ P(a) 2 ((X, + ,(Y,Y) ,(Y, X)
m(X,Y) + = = + ,Y 2 2/3 > 1/3
because (v X) 1/33, which contradicts the condition that the expected payment is at most 1/3.
17

---

Published as a conference paper at ICLR 2026
D.3 PROOF OF THEOREM 5.2
Suppose that the agents run no contextual swap regrei algorithms. Concretely, an agent has no contextual swap regret if
8c) Pi:A, -A
max E ΣE E (.))) PS-
(i)) U7 s ET.
where E - 0 as
oc. For typical no contextual swap regret algorithms. O C where
VT
C' depends on the game and the number of signals. Clearly, contextual swap regret is a stronger benchmark than the standard (external) notion of regret.
Then, after sufficiently many rounds T, by definition, we have that the correlated strategy profile
T (n', P ,') E A(S [0, BJAxAXX x A x x A
π
)-) J-PE in the sense of Appendix D.I. Therefore, by the revelation principle for CEPs (Proposition D.2), the principal objective value is bounded by that of the best (e maxm; [S; )-CP,, which is then bounded by F*(T) O(e).
is non-canonical (5 max;
D.4 PROOF OF THEOREM 5.3
From the analysis of Theorem 4.3, Algorithm 2 learns a game to precision E = (Ml CV/VI. (Note that we do express as function of I because 7 is the total number of rounds across both learning and steering stages.)
Since U and U differ by only (up to agent-independent terms), every CEP Î is a 2c-CEP of r. The payment function Pf for the steering stage then ensures that, when given signal 8s it is dominant for agent to play 0; = 8i. Formally, regardless of how other agents act, we have
(B, a;, a)) - U d,, a.))
E A, = s;, Va, * 8,, Va_ E A_
Further, from the analysis of Theorem 4.3, agent i's regret against following signals s; 1 is always nonnegative. Therefore, by agent i's regret bound, there are most CVT/p rounds on which agent i fails to obey recommendation 8; in the steering stage. By union bound, there are therefore mnCvT/ rounds in the steering stage on which a' + s'. Thus, the principal's suboptimality is bounded by
(2n + 1)
(2n + 1)mnC
("( FT(T) F (i)
+ n(2e +p) +
T
PVT
(1)
(3)
(2)
(1)
L
S poly(M)
+
+ +
T
vI
PVT
where the four terms are:
The difference between the optimal objectives on games I and Г. It is most 2n because
F* (T) = F(u", < F(u², P + 2s) + 2nc < F("", PD) + 2ne F*(T" + 2nc.
(2) The suboptimality and payments in the utility learning stage,
(3) The bonus payments to ensure strict incentive compatibility in the steering stage, and
(4) The suboptimality and payments in rounds on which a' * st.
Setting 1-4 and L T2/3 then completes the proof.
18


Reviews:
[{"review_id": "UT2Y399v3h", "reviewer": "Reviewer_zfeR", "summary": "This game addresses a natural question of learning a player's utility functions over time and studies this from an online learning perspective. Although this is a standard problem, the paper differs from the literature in two important ways: first they assume that the players are not in equilibrium. Secondly, they assume that the players are playing a no regret algorithm. The main contribution is a polynomial time algorithm that learns the utilities upto an error of $\\epsilon$. They further show that they can guide the agent towards a particular correlated equilibrium with payments (also known as steering). \n\nThe model is as follows. In each round the principal payment functions $P^t_i: A_i \\to [0,B]$  gets added to the agent rewards. The principal can also send a private signal. The agent which maximizes the sum of the payment and their own utility will play a mixed strategy $x^t$ which is observed by the principal. The paper's central insight is to reduce this to a zero-sum game between the principal and agent. Effectively the unique optimal in this game is for the principal to offer a payment of $p = 1-u$ the utility, thus making the agent indifferent between the actions. Then the principal can read the utility function by simply taking $p=1-u$. This is because the utility is zero-mean and if the principal updates their weights according to a no-regret algorithm like projected gradient descent (note that the mixed strategy $x^t$ is the derivative of the principal's loss function $(u+p) \\cdot x^t$), it will eventually converge to a point where the optimal utility is $u+p$ is a constant. This is a simple but elegant idea that allows the principal to discover the agent's true utility. \n\nTo handle the general setting when there are $n$ agents, the principal uses signals to effectively freeze the other agent's actions.", "questions": "N/A", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I think the paper outlines a simple and beautiful idea to learn the utility of any agent in a normal formed game. The dependence and the  learning rate and the associated regret is tight.", "weaknesses": "The complexity to learn scales exponentially on the number of agents and their action profiles. Their lower bound suggests that this task is too hard for many practical games. I also wonder a conference such as EC  might be a better fit than ICLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "JvaiZhK3Kv", "reviewer": "Reviewer_bHow", "summary": "Dear authors,\nI am finalizing my evaluation and will upload my full review within the next two days. Thank you for your patience.\n\nBest regards,\n—Reviewer", "questions": "TBC", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "TBC", "weaknesses": "TBC", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "pBwBKwmXM8", "reviewer": "Reviewer_evWz", "summary": "This paper studies the problem of learning a game by observing the agents play the game using no-regret algorithms and paying them to influence their behavior. The actor in this game seeks to learn the utilities of the game, up to strategic equivalence, through picking payments and providing signals to the agents in each round of play, under the assumption that the agents play arbitrary, possibly correlated, no-regret algorithms. It is important to note that the agents are in fact assumed to have contextual no-regret, i.e. they have vanishing regret for each signal/ no-regret over strategies mapping signals to actions. The main result of the paper shows that it is possible to learn the game in number of rounds polynomial in the size of the payoff matrix and that there are matching lower bounds, up to polynomial factors. \n\nThe paper first shows a slick method to estimate the utilities of a single agent using payments, by defining a two-player zero-sum game with a unique equilibrium and then shows how to construct no-regret dynamics to generate a sequence of payments that approaches this equilibrium, which in turn reveals the utility function of the agent.  This method is then lifted to learn the utilities of all agents in sequence in a multi-agent game, by rotating through the actions of all other players and using signals to fix their behavior for each learning phase. Other results in the paper include using this result to steer agents to desirable correlated equilibria while starting with no initial information about the game.", "questions": "Connected to the main weakness highlighted above -- how necessary is the assumption about no-regret for each signal? For instance, is it at all possible to learn the utilities of a multiplayer game with just a vanilla external regret assumtion?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 2, "contribution": 4, "strengths": "The main strength of the paper is in posing a natural question about learning a game by observing no-regret behavior and making meaningful progress in answering it by extending existing technical machinery. In particular, the algorithm to find the utility of a single agent is an elegant construction to re-use no-regret dynamics to find the equilibria of a game despite not seeing full information feedback.", "weaknesses": "The main weakness of the paper is the strong assumption made about the agents having contextual no-regret over the signals employed by the actor learning the game. This gives the actor tremendous leverage over the players practically for \"free\" since it allows them to \"forget\" the history of play by switching signals. This is exploited in obtaining an almost direct reduction from multiple players to one player. While this might well be a necessary assumption, there is insufficient technical justification for it.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SvHvSGI0CA", "reviewer": "Reviewer_2pKK", "summary": "This paper studies an active, non-equilibrium inverse game problem interacts with any no-regret players by giving payments and signals. The obejctive is to learn the utility functions of players under a equivalent game. The main idea is to cast the principal–agent interaction as a zero‑sum game where the principal’s mixed strategy is a payment vector. Then, authors consdier the problem of steering no-regret learning algorithm to desired result without the access to utility functions of players.", "questions": "- I would like to hear whether it is possible to relax the requirement on the signal in Theorem 4.3. Could the authors clarify or discuss potential directions for such relaxation?\n\n- In Section 3, it is mentioned that the knowledge of the mixed strategy $x_t$ could be relaxed. Could the authors elaborate on how the proposed algorithm should be modified in that case?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The zero‑sum formulation simple yet interesting, which requires almost no modeling of the agent’s learning rule beyond no‑regret property.\n\n- The results of this paper hold for arbitrary no‑regret learner, and authors also provide a lower bound implying the tightness of $\\epsilon$ and necessarity of $M$.\n\n- The proposed approaches are extended to the problem of steering no-regret learner without the access of utility function. Authors show that the principal-optimal CEP characterizes the value that the principal can achieve.\n\n- The paper is well-written and easy to follow. I appreciate that authors offer clear intuitions for the most of places.", "weaknesses": "- The assumption in (1) needs to hold for all signals, which seems strong to me. In fact, many contextual algorithms ensure provable regret bounds on average over contexts, not uniformly over all contexts.\n\n- The sample complexity shown in Theorem 4.3 has polynomial dependence on M and C, but it does not match the given lower bound. \n\n- The rate of steering agents to achieve the optimal CEP is $T^{-1/4}$, which seems suboptimal.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)