Stochastic Principal-Agent Problems: Computing and Learning Optimal History-Dependent Policies
Authors: Jiarui Gan
R Majumdar
Debmalya Mandal
Goran Radanovic
Venue: NeurIPS 2025 poster ()
Keywords: stochastic games
Markov games
Stackelberg games
information design
mechanism design
Primary area: theory

Abstract: We study a stochastic principal-agent model. A principal and an agent interact in a stochastic environment, each privy to observations about the state not available to the other. The principal has the power of commitment, both to elicit information from the agent and to signal her own information. The players communicate with each other and then select actions independently. 
Both players are {\em far-sighted}, aiming to maximize their total payoffs over the entire time horizon. 
We consider both the computation and learning of the principal's optimal policy. 
The key challenge lies in enabling {\em history-dependent} policies, which are essential for achieving optimality in this model but difficult to cope with because of the exponential growth of possible histories as the size of the model increases; explicit representation of history-dependent policies is infeasible as a result.
To address this challenge, we develop algorithmic techniques based on the concept of {\em inducible value set}. The techniques yield an efficient algorithm that computes an $\epsilon$-approximate optimal policy in time polynomial in $1/\epsilon$. 
We also present an efficient learning algorithm for an episodic reinforcement learning setting with unknown transition probabilities. The algorithm achieves sublinear regret $\widetilde{\mathcal{O}}(T^{2/3})$ for both players over $T$ episodes.

Stochastic Principal-Agent Problems: Computing and Learning Optimal
Policies
Jiarui Gan
Rupak Majumdar MPI-SWS
University of Oxford
j jiarui. gwn.ea..n....................... ox. ac uk
rupakempi-sws.. org
Debmalya Mandal
Goran Radanovic
University of Warwick
MPI-SWS gradanovicCmpi-sswi .rg
debmalya. mandal @warwick..... ac.
Abstract
We study stochastic principal-agent model. A principal and agent interact in stochastic environment, each privy to observations about the state not available to the other. The principal has the power of commitment, both to elicit information from the agent and to signal her own information. The players communicate with each other and then select actions independently. Both players are far-sighted, aiming to maximize their total payoffss over the entire time horizon. We consider both the computation and learning of the principal's ss optimal policy. The key chal- lenge lies in enabling history-dependent policies, which are essential for achieving optimality in this model but difficult to cope with because of the exponential growth of possible histories as the size of the model increases; explicit representation of -eeeeddde policies infeasible as a result. To address this challenge, we develop algorithmic techniques based on the concept of inducible value set. The techniques yield an efficient algorithm that computes an e-approximate optimal policy in time polynomial in 1 1/c. We also present an efficient learning algorithm for an episodic reinforcement learning setting with unknown transition probabilities.
The algorithm achieves sublinear regret (TT233) for both players over T episodes.
Introduction
Many problems in economic theory involve sequential reasoning between multiple parties with asym- metric access to information [37, 20, 4, 27]. For example, in contract theory, one party (the principal) delegates authority and decision-making power to another (the agent), and the goal is design mechanisms to ensure that the agent's actions align with the principal's utilities. This broad class of principal-agent problems lead to many research questions about information design and optimal strategic behaviors, with broad-ranging applications from governance and public administration to e-commerce and financial services. In particular, algorithmic techniques for optimal pecissonnmakingg and learning are crucial for obtaining effective solutions to real-world problems in this domain.
In this paper, consider general framework for stochastic principal-agent problems. We study the algorithmic problems related to the computation and learning of optimal solutions under this framework. In this framework, the interaction between the principal and the agent takes place in stochastic environment over multiple time steps. In each step, both players are privy to information not available the other and make partial observations about the environment. The players can communicate their private information to influence each other and, based on this communication, play actions that jointly influence the state of the environment. Each player has their own payoff, and we study the general-son -um case with far-sighted players: each player aims to maximize the (expected)
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

sum of their rewards over the entire horizon of the game. Technically, the setting is a stochastic game with partial information on both sides [1, 31].
In line with the principal-agent framework, we assume that the principal has the power of commitment, both to elicit information from the agent and to signal the agent about her own private information. A commitment is binding agreement for the principal to act according to the committed policy. The agent acts optimally in response the commitment, deciding what information share and what actions to perform at their own discretion. At a high level, we have a Stackelberg game and we aim to find Stackelberg equilibrium [40]. The possibility of information exchange further results in a model that incorporates both sequential Bayesian persuasion (or information design [22]) [16, 41] and sequential mechanism design [45]. We adopt stochastic games (or Markov games) [39] as our modeling basis, whose transition models are graph-structured Hence, our model is more expressive than tree-structured prineipal-agent problems such as those based on extensive-form games (EFGs), in the sense that exponentially many possible history trajectories can be unrolled from our graph-based model as the length of the time horizon increases, whereas in tree-structured ones, the number is bounded by the size of the tree.
Indeed, history-dependence is a key consideration in our policy design. Unlike in single-player Markov decision processes (MDPs) or zero-sum stochastic games, stationary (or history-indeeeedeen)) policies are no longer without loss of generality in our setting. For example, strategies like tit-for- tat uut-hhich are essential for achieving optimal outcomes in certain scenarios (such as the repeated prisoner's dilemma)- -eeeed on remembering past actions and thus cannot be implemented by stationary policies. Enabling history-dependent policies in our graph-based model, however, begets a major challenge caused by the exponential growth of possible histories. Explicitly representing history-dependee policy requires specifying strategy for every possible history, which quickly becomes infeasible as the number of histories increases exponentially with the length of the time horizon. To further optimize such a policy is even more challenging as the output of this computational task would be function over an exponentially large domain. In contrast, the size of a stationary policy is linear in the number of states.
1.1 Our Contributions
Surprisingly though, as we discover in this work, history-dependens policies can be represented as value vectors and can be efficiently unrolled provided polytopes consisting of all inducible value vectors. Building on this insight, we develop algorithmic techniques that work by constructing the inducible value sets. These techniques make it possible to implement and optimize eestory-dependen strategies dynamic principal-agent settings. More surprisingly, they are computationally efficient, so not only do they significantly expand the policy space- from stationary policies to the far more expressive class of history-dependee ones-but they also address a key computational barrier posed by stationary policies, to optimize which, even approximately, is known to be NP-hard [15].
In summary, we make the following contributions in this paper.
We introduce generalized framework for principal-agent problems in stochastic environments, which incorporates the stochastic extensions of various subcases of principal-agent problems such as information design [22] and automated mechanism design [38].
We develop algorithmic techniques that enable the implementation and optimization of history- dependent strategies in the stochastic principal-agency framework. The techniques are based on a compact representation of fully history-dependen polices and novel approach that works by constructing the inducible value sets. Together, they yield an efficient near-optimal algorithm that computes an e-approximate optimal policy in time polynomial in 1/e, while the policy it produces ensures exact incentive compatibility (IC).
We also consider an episodic RL setting where the transition dynamics are unknown and must be learned through interaction. We present a learning algorithm that guarantees sublinear regret (poly( M, H)- T2/3) for both players, where M the model size, H is the episode length, and T is the number of episodes. The algorithm builds on recent advances in reward-free exploration from the RL. literature and it leverages efficient computation of approximately IC policies, using a variant of our algorithm for the full-information setting.

---

1.2 Related Work
The principal-agent problem is a well-known concept in economics studies [see, e.g., 37, 33, 32, 29]. Models featuring sequential interactions have also been proposed and studied [34, 12]. Our work follows the same modeling approach as these early works and extends the one-shot versions of the respective models-suee as information design [22], automated mechanism design [38], as well as mixtures of the two [33, 7. 14]-into the sequential setting. There has been a growing interest in the algorithmic aspects of these sequential models, focusing their computation and learning (e.g.. information design [8, 15, 16, 41, 2), automated mechanism design [45, 6]. other types of sequential Stackelberg games [25, 26, 5, 18, 10], and even more recently, contract design [42, 19]).
More specifically, Gan et al. [15] first introduced an on an MDP. They showed that optimal stationary strategies are inapproximable, unless the receiver is myopic. This work left open the tractability of optimal history- finite-horizon models, which consider in this paper. Wu et al. [41] later studied the reinforcement learning problem against a myopic agent in the same sequential information design model. Bernasconi et al. [2] also studied the same problem in model based an EFG; efficient computation and learning algorithms were presented. Similar EFG- models have also been explored in the recent literature [43, 44]. EFGs are tree- structured and hence easier than MDP-based models in the sense that all history sequences are modeled explicitly in the model. The number of possible histories is bounded by the size of the problem as result, where this can be exponential in an MDP. Hence, efficient algorithms for EFG-based models do not directly translate to efficient algorithms for our MDP-based model. In the domain of automated mechanism design. Zhang and Conitzer [45] studied a Lmite-horizon model that is POMDP for the principal and MDP for the agent. They presented a linear program for computing optimal mechanisms, whose size exponential in the problem size.
information design model based
strategies, especially in
As mentioned earlier, our algorithm leverages compact representation of history-dependent polices and construction of inducible value sets. Similar techniques have been proposed in earlier works by Dermed and Isbell [11] and MacDermed et al. [28] to compute optimal correlated equilibria of stochastic games. Our algorithm extends these techniques into the principal-agent setting, with adaptions that ensure exact incentive compatibility (IC) in the full-information setting. Concurrently with our work [17], Bernasconi al. [3] also used similar approximation approach to solve an information design problem (as a special case of our model). Compared to their results, our algorithm guarantees exact IC, with more straightforward approach. Moreover, we also study the learning problem where the transition model needs to be learned, in addition to the computation problem where this is given. While all the above works (including ours) only guarantee near-optimality, exact solutions are possible in some special cases. In a recent work of Zhang et al. [46], they presented a sophisticated exact algorithm for computing optimal correlated equilibria in two-player turn- basdd stochastic games. In infinite- horizon games, however, such exact solutions appear computationally infeasible because of irrational numbers involved in optimal polices; we refer the reader to a more recent work by Gan and Majumdar [13].
2 Preliminaries
principal (P) and an agent (A) interact in a finite-horizon POMDP M = (S, A, p. r). where:
S a finite state space; = AP x A is a finite joint action space; Q S2P S2A is a finite joint observation space; p (pr) ) = and
(r,, h== are two tuples, each consisting of an element for every time step h. Specifically, Po E A(S x 52) is a distribution of the initial state-observation pairs, and each Ph. h 2 1, is a transition function ps: : S x A + A(S x Q). Each ry = (rf, r is a pair of reward functions rh. : S x A- + R and r : S x A - R, for the principal and the agent, respectively. W.l.o.g,, we assume that all rewards are [0, 1]. and all rewards in the last time step H are 0.
The interaction proceeds as follows. At the beginning, an initial state-observation pair (81, wi) ~ po is drawn. Then, each time step h = 1...., H involves the following stages.
1. Observation: The principal and the agent observe, privately, wf, and wA respectively (but not sn.).
2. Communication: The principal elicits the agent's observation. The agent reports WA E SAA (possibly different from w Then, based on wf, and ãA the principal recommends an action of for the agent to play. The recommendation is sent to the agent coordination signal.
3

---

3. Action: Based on the information exchange above, the principal and the agent, simultaneously. each perform an action, say a and d respectively. (The action af the agent actually performs may be different from the recommended one af.))
4. Rewards and next state: Rewards r (sh, ai. af) and (sn, af a.)) are generated for the princi- pal and agent, respectively. The next state drawn: Sh+11 Pr. (- Sp. a. af))
Following the general paradigm of principal-agent problems, we consider the principal's s commitment coordination policy. The agent best-responds to the principal's commitment. Both players are far-sighted and aim to maximize the sum of their rewards over the H time steps." 1 We take the principal's 's perspective and the goal, we will shortly formalize, is compute the principal's 's optimal commitment. At a high level. this is a Stackelberg game between the principal and the agent and we aim to compute a Stackelberg equilibrium.
2.1 Hindsight Observability
We assume hindsight observability, whereby both players observe the full interaction history (includ- ing 8h, and a) at the end of each time step. This condition is essential for circumventing intrinsic computational complexity barriers: without it, our model would directly subsume partially observable MDPs (POMDPs), which is famously known be PSPACE-hane [36], in which case any efficient algorithms would be hopeless unless P = PSAPCE. (See a further discussion in Appendix C.) Similar assumptions have been adopted in the POMDP literature [24). Importantly, our model remains highly expressive under hindsight observability, capturing a broad range of relevant subcases, including: scenarios where the state is immediately observable, e.g., repeated games, stochastic games with full state observability [10], as well as scenarios where observations can be interpreted as external parameters generated based on an internal Markovian state observable both players (e.g.. [15, 41J).
Indeed, in many real-world scemarios, it natural for players to observe each other's actions after they are taken (consider, e.g., repeated rock-paper- scpsr-scsssors) Beyond actions, players may also receive regular updates about each other's s private observations. This occurs in particular when each player observes a different part of the state and the full state is revealed at the end of the time step- at which point all private observations effectively become public. For example, traders may each observe local regional market information that is later aggregated and released publicly; in energy markets, regional grid operators obtain first-hand information about supply and demand within their own regions and later receive system-wid reports covering the entire market; and in an R&D consortium, each firm privately evaluates prototypes or test results and acts on that information during the reporting cycle, after which all results are disclosed to members under agreed rules.
2.2 History-dependent Policy
We consider history-dependent policies, which are more general than stationary policies and hence typically yield higher payoffs. For example, to punish the agent for performing certain action requires a History-dependent policies are also natural choice for finite-horizon models, where the memory required to track the history is bounded by the horizon length.
policy that remember the agent's 's action in the previous time step.
A history up to time step h is a sequence = (se, We, We, DA ae, SA) h f-1- containing elements in the four stages of each step described above (and we write wi ( ) and a; (af a²) We let Σn denote the set of all sequences till time step h, and let = U En. where Eg = {Ø} contain only the empty sequence. Moreover, we denote by Σ = x Ω x Ω2a x x A the set of all possible interactions within one time step. We can now write the transition function as pal ( (o) = (. 8h, as) for any given sequence a E E., (specially, po(. Ø) = po).).
Principal's Policy A history-dependent policy takes the form E x Ω + A(A), whereby upon seeing a in the previous steps. observing uP, and receiving the agent's 's report AA in the current step. the principal draws a joint action a (aP, d^) ~ T(r: AaA), sends ad to the agent as an action recommendation, and performs aP herself. We denote by (aaa a; _ the probability of each in xt (oo:",
While we assume no discounting, all our results easily extend to discounted rewards.

---

Agent's Response The principal's commitment results in meta-POMDP for the agent. The agent reacts by playing optimally in this meta-POMMP.. When the principal's policy IC, this simply means responding truthfully. Formally, the agent's is strategy can be described by deviation plan p: (a, w²) (wA, A - A²), such that given any history a and observation W in the current step, the agent reports α and then plays ā = f(aA) if subsequently the principal recommends playing aA, For simplicity, we write ~a (") and â p(o:wA aAA. We denote by 1 the special deviation plan where deviation is made, i..., 1 (o:w²) = w and I (or, aa*) a².
The agent's value (i.e., total reward) induced by a policy and deviation strategy p can be defined recursively via the value function as follows. For every h = I,...,, H. - and o E 2
A (o) E r (s,a as,a, ,a*)
)+ + V (a; s, w. a. ,, a²a
(1)
where the expectation is taken over (8, w) pn-1(-1a) and a ~ x( Ia ; moreover, WA p(a", w* and ã^ = p(o", wn, a²), and by assumption (a(a) = 0 for the last time step. The principal's 's value is defined the same way by changing the labels.
Our goal to find policy ı that maximizes the principal's value under the agent's best response:
max T.P
subject to P arg / VATT (2)
(2-1)
In other words, we look for IT and p that form Stackelberg equilibrium. We say that i is c-optimal if (e)) V e for some satisfying (2-1), where V denotes the optimal value of (2).
As we will demonstrate, under hindsight observability, it is without loss of optimality to consider policies that are IC (incentive compatible), which incentivize 1 as an optimal response of the agent. Definition 1 (IC policy). policy x is IC V. (Ø)= 2 V=ATT:(())) for every possible deviation plan p of the agent.
3 Computing an Optimal Policy
We compute a near-optimal policy by constructing the inducible value sets. The approach is similar to value-based approaches to solving MDPs, which operate by reasoning about the values of the states. However, involves the following crucial differences:
1. Since we are in a two-player setting, both player's values need to be incorporated. We use a two-dimensional value vector instead of scalar value.
2. Since we consider history-dependent policies, the game may proceed differently from the same state based on different histories. In this case, a single value (vector) is no longer sufficient for characterizing a state, unlike the case with stationary policies. We use the set consisting of all values can be induced by some valid policy to characterize a state. We refer to these sets are inducible value sets.
Moreover, since the actual state of the underlying MDP is not observable at the beginning of each time step. we will instead characterize the inducible value sets of state-action pairs E O == S x A. Under hindsight observability, these pairs function the states in Markovian process, which the players observe before they each decide an action to play.
Definition (Inducible value set). The inducible value set Vn((o) S IR2 of a state-action pair o O = x A at time step h consists of all vectors v = (oP, (A) such that up = Vp (/ and A (a) for some policy म, deviation plan p arg max, V.A.s.o'' (o), and sequence E _n ending with o.
It is straightforward that once we obtain (Ø), then the principal's 's optimal value in (2) can be com- puted by solving max (utje, uP. We present dynamic programming approach to constructing the inducible sets next. We will later also show that, once we obtain all the inducible sets, every inducible value vector can be efficiently unrolled into history-depender policy that induces it, and the policy can be executed efficiently on the fly. Hence, each value vector serves as a compact representation of fully specified iistory-dependee policy.
5

---

3.1 Computing Inducible Value Sets
Instead computing the exact value sets, we use convex polytopes to approximate them, so as to avoid possible exponential growth of the representational complexity. Let (o()) denote the approximation of (o) we aim obtain. Recall that in the last time step all rewards are 0, so trivially we use (o) Vn((s) = ((,,0) for all o & O as the base case.
Dynamic Programming Now suppose that we have obtained the polytopes (o') for all o' O. We move to time step and construct each Vr. (o) based on the 1 ss Central to the approach is the following characterization, which describes an IC condition at time step h: for every v E R it holds that v E (o) if and only if there exist a one-step policy : + (AA) and set of onward value vectors (v TR22.
{ that satisfy the following constraints.
1. A value function constraint based (I), which expresses via the immediate rewards and onward value vectors v' to be induced next, assuming truthful response of the agent:
Σ Ph- 1 o) a(a () (ra(s, + v w, a (, a 8,w,a
(3)
The onward value vectors represent the subsequent part of the principal's ' commitment, which is contingent the interaction (s, w, WF a, ā²) in step h. Under the truthful response of the agent, we have WA = w and â^ = a in (3).
2. IC constraints, which ensure that the agent's truthful behavior assumed in (3) is indeed incen- tivized, where we denote by 1 w lo,w*) x (s-1(s,w| the conditional probability defined by Ph-1- For all WA, mA E 2A
Σ Ph- pn- w (l, (w (s, + +
S,wP.
max Σ aA
Σ suuP .P
Ph-1(8, (0, a(alwp. (rA(s, aa) + (s,,,,
aMEAM
Namely, the constraint says, upon observing wA, the agent's expected payoff under their truthful response is at least as much as what they could have obtained, had they: 1) reported a different observation @A 2) performed best action ã^ in response to every possible recommendation a of the principal, and 3) responded optimally in the subsequent time steps (whereby the onward values given by v').
3. Onward value constraints, which ensures that the onward values given by v' are also inducible:
v'(s, w, aa,aa" a² E Vn+i(s, A
for all (s, w. WA aA) E Σ.
(5)
The following lemma indicates the correctness of the above characterization.
Lemma 3. v E (o( if and only if (3) to (5) hold for some मे : + ((A) and v - R
Therefore, decide whether v (o) amounts to deciding whether the above constraints are satisfied by some न and v' (highlighted in blue in the constraints). Note that since the inductive hypothesis assumes approximation (o')(o') instead of the exact set Vn+i we will in fact impose the following approximate onward value constraint, instead of the exact version in (5):
v'(s, w. AA a, a+) E DetI(s, aP, (
for all (s, w. AA a. a. E.
Linearizing (3) and (4) The constraint satisfiability problem defined above is non-linear due the quadratic terms and the maximization operator in (3) and (4). Nevertheless, it can be linearized as long every polytope 10'), o' O, is given by the half-space representation, i.e., by linear constraints in the form H S for some matrix H and vector b. Due to the space limit, we leave the details in Appendix B.

---

V6
5
(o)
4
4
(o(
Figure 1: Constructing (o) as a
a 5-approximation of (o). The black points constitute W.
For h H 1, 1, do the following for all o E O:
1. Plug in (6) the half-space representation of (n+z(o'), o' E O. Then linearize (3) and (4),
2. Discretize the space [0, HJ2 into a finite point set (see Lemma 4 for more detail). Check the inducibility of each point v in this set by solving the linear constraint satisfiability problem defined by (the linearized version of) (3), (4) and (6).
3. Compute ()(() the convex hull of the inducible points obtained above, in half-space representation.
Figure 2: Computing approximate value polytopes via dynamic programming.
Constructing (o) As a result, we obtain a polytope defined by set of linear constraints equivalent to (3), (4) and (6). The projection of P onto the dimensions of v is (approximately) (o). To ensure that the projection can be plugged back into (6) in the next induction step, we need the half-space representation of the projection, too. In particular, we want to eliminate the additional variables in the representation so that only v remains. (Otherwise, the number variables may grow exponentially the induction step increases.) This can be done approximately in polynomial time given that v is wwo-dimensional. Roughly speaking, we discretize the box [0, HH² into a finite set of points (recall that rewards in each time step are bounded in [0, 1]. so [0, H contains Va (o)), check the inducibility of each point, and compute the convex hull of the inducible points half-space representation. The specific way discretize the space (see Fig. 1) ensures that IC is satisfied exactly (which can otherwise not be achieved by using standard grid-based discretization.. The details can be found in the proof of Lemma 4.
Repeating the induction procedure till h = 1, we obtain (Ø) well as a near-optimal value of the principal by solving the IP max (e) vP. Fig. 2 summarizes this dynamic programming approach.
Lemma 4. For any constant e > O, it can be computed in time poly( H, 1/e) the half- space representations of a set of polytopes Vn(o) C Vi(o), E U (Ø) and h = 1,..., H. such that (3), (4) and (6) are satisfiable for every Vo(o) and max max o maxvevi op
Proof sketch. We construct the approximate sets (o) by backward induction. Assume for all o that Dn+1 (o) is detined by polynomially many constraints and an e-approximation of Vn+i(o). Let (o) be the feasible set defined by (3), (4) and (6) using (o'). We discretize the principal's value into slices of width 5 (see Fig. 1). We include the following points into collection W use the convex hull of W as (o): 1) for every line w separating the slices, the two points V., and v.. at the intersection of and the boundary of Di+ (o); and 2) the extreme points v. and v. of (o) minimizing and maximizing the agent's 's value, respectively. Each of these points can be obtained
7

---

Input: a sequence (o:wP, ,aA,,, where o = (st, wi, w az, az aA)411 1. Initialize: f- arg max (0r) of and o t Ø.
12=11
2. For l h...., 1:
Fix v and o, and solve (3), (4) and (6), where we use the polytopes 1. (o) described in Lemma Let the solution be and v'.
Update: (se, We, 2 ag, at) and -- (st,
3. Output x-1 w,; ( #(- w )²
Figure 3: Computing a near-optimal policy based on approximations of the value polytopes.
efficiently by solving a polynomial-size LP. The inclusion of the extreme points ensures in particular that we do not miss the agent's extreme values, which critical for achieving exact IC.
It can be verified that (o) Vo(()) and that any E (o) can be approximated by some x E (o( with αA a and xP 2 o - So (o) is 5-approximation of (o) and aAA oA ensures exact IC for the agent. Since (o) itself is an e-approximation of V%. (o), we obtain an (s + -)apppooxnnttion overall. Choosing ā = e/H and noting the trivial base case (o)(o) (0, 0)}, the construction yields (Ø) as an e-approximation of Vi (Z). computable in time ()) | 1/e).
3.2 Unrolling the Optimal Policy
The above procedure yields the maximum inducible value of the principal but yet an optimal policy that achieves this value. We next demonstrate how to compute an optimal policy based on (2). Rather than obtaining an explicit description of history-dependent policy ग which would be exponentially large as the policy specifies a distribution for each possible sequence-we present an efficient procedure that computes the distribution π (. a; _,AA) for any given sequence (a;w&,, (AA). This means that, when playing the game, the principal can compute an optimal policy on the fly based on the realized history.
We use a forward computation procedure presented in Fig. 3. Starting from time step 1, the procedure repeatedly computes a one-step policy ग and set of onward vectors, to induce the target value vector v. The onward vectors define the target values to be induced in the next time step, contingent on the interaction in the current, which is given by a. Hence, the target vector is updated to one of the onward vectors according a at the end of each iteration. In other words, in each time step, we expand the target vector into set of onward vectors, and then select one of them the next target vector according to the realized interaction given by a. This leads to the following main result.
Theorem 5. There exists an e-optimal IC policy x such that, for any given sequence (a;wP,0* E x Qt the distribution क (-10; (.A) can be computed in time (, 1/e).
4 Learning to Commit
We now turn to an episodic online learning setting where the transition model p: S - A(S 12) not known to the players beforehand. Let there be T episodes. At the beginning of each episode, the principal commits to a new policy based on the outcomes of the previous episodes. Each episode proceeds in Hi time steps the same way as the model defined in Section 2.
We present learning algorithm that guarantees sublinear regrets for both players under hindsight observability. The algorithm is centralized and relies on the agent behaving truthfully. It does not guarantee exact IC during the course of learning but IC the limit when the number of episodes approaches infinity. Indeed, since the model is unknown to both players, IC in the limit is a more relevant concept as the agent cannot decide how to optimally deviate from their truthful response, either. In this case, the sublinear regret the algorithm guarantees for the agent should in many
8

---

scenarios be sufficient for incentivizing for the agent to participate and follow the centralized learning protocol.
The players' regrets are defined as follows:
T _ = Σ Vy
T V.T.
Reg"
and
Reg"
max V1 (0) -V
V. (0)
t=1
where V is the optimal value of (2) and ny denotes the policy the principal commits to the I-th episode. In words, the principal's regret Reg is defined with respect the optimal policy under the true model. The agent's regret Reg" defined with respect to his optimal response to each Tr, which is a dynamic regret as the benchmark changes across the episodes.
4.1 Learning Algorithm
Reward-free Exploration Our learning algorithm based on reward-free exploration, which an RL paradigm where learning happens before a reward function is provided [21]. It has been shown in series of works that efficient learning possible under this paradigm [21, 23, 30]. In particular, we will use the sample complexity bound in Lemma 6. At high level, our algorithm proceeds by first conducting reward-free exploration learn sufficiently accurate estimate of the true model. Based on the estimate we then solve relaxed version of the policy optimization problem (2) to obtain policy. Using this policy in the remaining episodes guarantees sublinear regret for both players.
Lemma 6 ([21, Lemma 3.6 restated]). Consider an (single-player) MDP (8, A, (without any reward function specified) with horizon length H. There exists an algorithm which learns model p after Ö # 1S--AA
episodes of exploration, such that with probability at least q. for any reward
function r and policy n, it holds that ( S 6/2 all states s, where Vi" and V.r denote the value functions under reward function and models p and respectively.
With the above result, we can learn a model P for our purpose. what follows, we let D.P.. and f.A.T.PP denote the players' value functions in model p (i.e., by replacing in (1) with p). Lemma 7 then translates Lemma 6 our setting. Note that under hindsight observability the process facing the principal and the agent jointly during the learning process is effectively an MDP, where the effective state space is O Q. An effective state, say 0 (8, a, w), consists of the state-action pair (s, a) in the previous step and the observations w in the current. When joint action a' is performed, 0 transitions to 6' (s', a', w²) with probability 1
A
(iss,cu w [s,a).
Lemma 7. model p can be learned after Ö [ ||| |A| |2///87 /5²) episodes of exploration, such that Vi VAA. - \)))T.P()) I 6/2 and V. V.P.t.(()) (2) - P.. P.. (2)
s 8/2 with probability at least
1 q for any policy ı and deviation plan p.
Therefore, the value functions change smoothly as the learned model f approaches However, this smoothness is insufficient for deriving a sublinear bound on the principal's 's regret because of the agent's s incentive constraints in our problem. Roughly speaking, the set of IC policies does not change smoothly with p. even though the value functions do. Hence, even an infinitesimal difference between P and may lead to a jump between the IC policy sets under these two models and, in turn, a gap between the values of the optimal policies.
Approximate IC Relaxation To deal with this issue, we relax the incentive constraints, allowing small violations to the constraints. Such violations are inevitable we aim to achieve a near-optimal value under the true model but only know an estimate p of the true model. On the positive side, given the sublinear regret guarantee for the agent, the violation diminishes with the number of episodes. We define 5-IC policies below.
"The notation δ omits logarithmic factors. the original statement of Jin [21], я non-stationary ((mme-deenddent but independent of the history. However, the proof of the lemma also applies to history- dependent policies. The dependence on H in the sample complexity can be further improved with better reward-free exploration algorithms [23, 30). but this is not focus of ours.

---

Definition 8 (6-IC policy), A policy т is ô-IC (wrr.t model p) if 1 every possible deviation plan p of the agent. A 6-IC policy is said be c-optimal if 1y 1i..5- (0) V* where V* is the optimal value of (2) (underp) p).
( 2 ()Am.(2) d for
6-IC policy, the agent can improve his overall expected payoft by no more than 8 if he deviates from the truthful response. We assume that the agent will not deviate for such small benefit, and we evaluate the value of 6-IC policy based on the agent's truthful response. This is how the e-optimality is defined above, where we compare against the optimal value V in (2), which obtained under a more stringent setting without any relaxation of the agent's incentive. In other words, we relax the feasible space and compare the solution obtained in this relaxed space with the optimum over the smaller original feasible space. Such relaxations are common in the optimization literature, and they are crucial for resolving the non-smooth issue.
That is, in response
Let Ii, and II denote the set of 5-IC policies under p and p. respectively. The relaxation immediately results in IIg 2 1l for the model ğ stated in Lemma 7. As a result, optimizing over 1I, ensures that the optimal value yielded is as much (up to a small error) as the optimal value V over llg. Meanwhile, the value loss introduced by this relaxation for the agent is also small (bounded by 6).
With the above results, our learning algorithm proceeds as follows.
1. Run reward-free exploration to obtain model p stated in Lemma 7.
2. Compute 6-optimal 8-IC policy in P and use it in the remaining episodes.
The near-optimal policy Step can be computed efficiently according to Lemma via an approach similar to the one in Section 3.1. This gives an efficient algorithm with sublinear regrets for both players. We present Theorem 10.
Lemma 9, There exists an e-optimal 8-IC policy π such that, for any given sequence (o; (o;w², (a) Σ Q the distribution a(-la;w ( can be computed in time poly((S))|A)110)) H, 1/c, log log(1/6)).
Theorem 10. There exists algorithm that guarantees regret ((C1/3T2/3) for both players with probability 1 g. where Ç H | | | The computation involved in implementing the algorithu takes time poly([S)|[4))00).) H.)).
5 Conclusion
We studied a stochastic principal-agent framework and presented efficient computation and learning algorithms. Our model can be further extended to the setting with agents. The algorithms we presented remain efficient for any constant if approximate IC solutions are considered. Computing optimal exact IC policies for n agents remain an interesting open question, as our discretization method, which operates by slicing the space, does not generalize to n agents. When is not a constant, representing games in normal-form requires space exponential in n, more succinct representations are typically considered. However, is known that in succinetly represented games even to compute an optimal correlated equilibrium in one-shot games may be NP-hard [35].) Our results indicate how a policy designer might interact with agents optimally. particular implementations, the designer's s incentives may not be aligned with societal benefits. In these cases, a careful analysis of the incentives and their moral legitimacy must be considered. Besides this, since the paper is theory focused, we do not feel any other potential impacts must be specifically highlighted here.
Acknowledgement
The work of Goran Radanovic was funded by the Deutsche Forschungsgemeinschaatt (DFG, German Research Foundation) project number 467367360.
10

---

References
[1] Robert J. Aumann and Michael B. Maschler. Repeated Games with Incomplete Information. MIT Press, 1995.
[2] Martino Bernacconi, Matteo Castiglioni, Alberto Marchesi, Nicola Gatti, and Francesco Trovò. Sequential information design: learning to persuade in the dark. In Proceedings of the 36th International Conference on Neural Information Processing Systems (NeurIPS 2022.
[3] Martino Bernasconi, Matteo Castiglioni, Alberto Marchesi, and Mirco Mutti. Persuading farsighted receivers in MDPs: the power of honesty. Advances Neural Information Processing Systems (NeurIPS'23) 36, 2024.
[4] Patrick Bolton and Mathias Dewatripont. Contract Theory. Mit Press, 2004.
[5] Branislav Bošanský, Simina Brânzei, Kristoffer Arnsfelt Hansen, Troels Bjerre Lund, and Peter Bro Miltersen. Computation of stackelberg equilibria of finite sequential games. ACM Transactions on Economics and Computation (TEAC), 5(4):1-24, 2017.
[6] Federico Cacciamani, Matteo Castiglioni, and Nicola Gatti. Online mechanism design for information acquisition. In Proceedings of the 40th International Conference on Machine Learning (ICML 22), 2023.
[7] Matteo Castiglioni, Alberto Marchesi, and Nicola Gatti. Bayesian persuasion meets mechanism design: Going beyond intractability with type reporting. In Proceedings the 21 International Conference on Autonomous Agents and Multiagent Systems (AAMAS 22), page 226-234, 2022.
[8] Andrea Celli, Stefano Coniglio, and Nicola Gatti. Private bayesian persuasion with sequential games. In Proceedings of the AAAI Conference on Artificial Intelligence (AAAI 20), volume 34, pages 1886-1893, 2020.
[9] Timothy M Chan. Optimal output-sensitive convex hull algorithms in two and three dimensions. Discrete & Computational Geometry, 16(4):361-368 1996.
[10] Natalie Collina, Eshwar Ram Arunachaleswaran, and Michael Kearns. Efficient stackelberg strategies for finitely repeated games. In Proceedings the the 2023 International Conference on Autonomous Agents and Multiagent Systems (AAMAS'23), page 643-651, 2023.
[11] Liam Dermed and Charles Isbell. Solving stochastic games. Advances in Neural Information Processing Systems (NIPS'09) 09), 22, 2009.
[12] Francoise Forges. An approach to communication equilibria. Econometrica: Journal of the Econometric Society, pages 1375-1385, 1986.
[13] Jiarui Gan and Rupak Majumdar. Value-set iteration: Computing optimal correlated equilibria in infinite-horizon multi-player stochastic games, 2025. URL https: //tpx//axvvv////////////e//aaiaa www.:org/aaaaoo.. //tp//bbb//00..... 07186.
[14] Jiarui Gan, Minbiao Han, Jibang Wu, and Haifeng Xu. Optimal coordination in generalized principal-agent problems: A revisit and extensions. arXiv preprint arXiv:2209.011 /46, 2022.
[15] Jiarui Gan, Rupak Majumdar, Goran Radanovic, and Adish Singla. Bayesian persuasion in sequential decision-makinn makiin.. In Proceedings of the 36th AAAI Conference Artificial Intelligence (AAAI'22), pages 5025-5033, 2022.
[16] Jiarui Gan, Rupak Majumdar, Goran Radanovic, and Adish Singla. Sequential decision mak- ing with information asymmetry. In 33rd International Conference on Concurrency Theory (CONCUR'22 22), volume 243 of Leibniz International Proceedings in Informatics (LIPles), pages 4:1-4:18, 2022.
[17] Jiarui Gan, Rupak Majumdar, Debmalya Mandal, and Goran Radanovic. Sequential principal- agent problems with communication: Efficient computation and learning, 2023. URL https: / //axiiv.. org/abs 2206. 03832v1.

---

[18] Keegan Harris, Hoda Heidari, and Steven Z Wu. Stateful strategic regression. Advances in Neural Information Processing Systems, 14:28728-287444 2021.
[19] Dima Ivanov, Paul Dütting, Inbal Talgam- Tonghan Wang, and David C. Parkes, Principal- agent reinforcement learning, 2024. URL https://arxiv.... httpaaawwii.....aaa/aa/aaeo.oett http//bs//// /207. 18074.
[20] Michael C. Jensen and William H. Meckling. Theory of the firm: Managerial behavior, agency costs and ownership structure. Journal of Financial Economics, 3(4):305-360, 1976.
[21] Chi Jin, Akshay Krishnamurthy, Max Simchowitz, and Tiancheng Yu. Reward-free exploration for reinforcement learning. In International Conference on Machine Learning, pages 4870-4879 PMLR, 2020.
[22] Emir Kamenica and Matthew Gentzkow. Bayesian persuasion. American Economic Review, 101(6):550-2615, 2011.
[23] Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko. Adaptive reward-free exploration. In Algorithmic Learning Theory, pages 865-891, PMLR, 2021.
[24] Jonathan Lee, Alckh Agarwal, Christoph Dann, and Tong Zhang. Learning in POMDPs is sample-efficient with hindsight observability. In International Conference on Machine Learning, pages 18733-18773. PMLR, 2023.
[25] Joshua Letchford and Vincent Conitzer. Computing optimal strategies commit to in extensive- form games. In Proceedings of the 11th ACM conference on Electronic commerce (EC' pages 83-92, 2010.
[26] Joshua Letchford, Liam MacDermed, Vincent Conitzer, Ronald Parr, and Charles L. Isbell. Computing optimal strategies to commit to in stochastic games. In Proceedings of the 26th AAAI Conference on Artificial Intelligence (AAAI'12), page 1380-1386, 2012.
[27] Lars Ljungqvist and Thomas J. Sargent. Recursive Macroeconomic Theory, fourth edition. Mit Press, 2018
[28] Liam MacDermed, Karthik Sankaran Narayan, Charles Lee Isbell Jr., and Lora Weiss. Quick polytope approximation of all correlated equilibria in stochastic games. In Wolfram Burgard and Dan Roth, editors, Proceedings of the 25th AAAI Conference on Artificial Intelligence (AAA['II) 2011.
[29] Miltiadis Makris. The theory of incentives: The principal-agent model. The Economic Journal, 113(488):F394 F395, 2003.
[30] Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko. Fast active learning for pure exploration in reinforcement learning. In International Conference on Machine Learning, pages 7599-7608. PMLR, 2021.
[31] Jean-Francois Mertens, Sylvain Sorin, and Shmuel Zamir. Repeated Games (Econometric Society Monographs Book 55). Cambridge University Press, 2015.
[32] Robert Milgrom and John Roberts. Relying on the information of interested parties. Rand Journal of Economics, 17:18-32, 1986.
[33] Roger B Myerson. Optimal coordination mechanisms in generalized principal agent problems. Journal of mathematical economics, 10(1):67-81, 1982.
[34] Roger B Myerson. Multistage games with communication. Econometrica: Journal of the Econometric Society, pages 323-358, 1986.
[35] Christos H Papadimitriou and Tim Roughgarden. Computing equilibria in multi-player games. In SODA, volume 5, pages 82-91. Citeseer, 2005.
[36] Christos H Papadimitriou and John N Tsitsiklis. The complexity of Markov decision processes. Mathematics of operations research, 12444444,4450 1987.
12

---

[37] Stephen A. Ross. The economic theory of agency: The principal's problem. The American economic review, 63(2):134-1333 1973.
[38] Tuomas Sandholm. Automated mechanism design: new application area search algorithms. In Principles and Practice of Constraint Programming CP 2003: 9th International Conference, CP 2003, Kinsale, Ireland, September 29- October 3, 2003. Proceedings 9, pages 19-36. Springer, 2003.
[39] Lloyd S Shapley. Stochastic games. Proceedings of the national academy of sciences, 39(10): 1095-1100, 1953.
[40] Heinrich Von Stackelberg, Market structure and equilibrium. Springer Science & Business Media, 2010.
[41] Jibang Wu, Zixuan Zhang, Zhe Feng, Zhaoran Wang, Zhuoran Yang. Michael Jordan, and Haifeng Xu. Sequential information design: Markov persuasion process and its efficient reinforcement learning.
Proceedings of the 23rd ACM Conference on Economics and Computation (EC'22), page 471-472, 2022.
[42] Jibang Wu, Siyu Chen, Mengdi Wang, Huazheng Wang, and Haifeng Xu. Contractual rein- forcement learning: Pulling arms with invisible hands, 2024, URL https://arxiil org/abs/ 2407 .01458.
[43] Brian Zhang and Tuomas Sandholm. Polynomial-time optimal equilibria with mediator in extensive-form games. Advances in Neural Information Processing Systems, 35:24851-24863, 2022.
[44] Brian Zhang, Gabriele Farina, Ioannis Anagmostides, Federico Cacciamani, Stephen McAleer, Andreas Haupt, Andrea Celli, Nicola Gatti, Vincent Conitzer, and Tuomas Sandholm. Com- puting optimal equílibria and mechanisms via learning in zero-sum extensive-form games. Advances in Neural Information Processing Systems, 36, 2023.
[45] Hanrui Zhang and Vincent Conitzer. Automated dynamic mechanism design, 2021.
[46] Hanrui Zhang, Yu Cheng, and Vincent Conitzer. Efficiently solving turnttaking stochastic games with extensive-fome correlation. In Proceedings of the 24th ACM Conference on Economics and Computation (EC'23), pages 1161-1 1161-1186, 2023.
13

---

NeurIPS Paper Checklist
1. Claims
Question:
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We outline the key claims and contributions of this work in the abstract and in the introduction section. All claims are supported by rigorous proofs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: We mentioned in the main paper limitations of our results and assumptions required. Additionally, we also discussed potential future directions to address these limita- tions in the conclusion section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "I "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: Every theoretical result is supported by rigorous proofs, with all details provided in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, descríbing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e-g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing verifying the results.
5. Open access to data and code
15

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [NA]
Justification:
This paper does not include experiments.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
hhblliicguudees/deeeSttiissss caiibbiisiooooocccr for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: ctsps.cc/public//eeeee guwdee/eee/ee// /CodeSubmia sgionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
16

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: This paper does not include experiments.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental rums as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with NeurlPS Code of Ethics https htt///nuriip../ cttppppp...ppppppppp.pppp http./////c/cccccccciieeeeeeeeee
Answer: [Yes]
Justification:
This research conforms the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification;
We discussed potential positive and negative societal impacts in the conclusion section. In particular implementations, the designer's 's incentives may not be aligned with societal benefits. In these cases, a careful analysis of the incentives and their moral legitimacy must be considered.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
17

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcode. thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
18

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/model as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Bthies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, not include any information that would break anonymity (if applicable), such the institution conducting the review.
19

---

16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, or formatting purposes and does not impact the core methodology. scientific rigorousness, originality of the research, declaration is not required.
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to L.M policy (https: http://neurisscpee hatrrripssccccoofffeeeeee/////// for what should or should not be described.
20

---

A Omitted Proofs
A.1 Omitted Proofs in Section
For simplicity, we write (o))= = -VV Vn v() in the following proofs.
Lemma 3. v Vx(() if and only if (3) to (5) hold for some म Ω ((A) and v' - R
Proof. First, consider the "only if direction of the statement. Suppose that v E V4 (o). By definition, have (o) for some n, P arg max Vn VA (o), and E Σn-1 ending with According to a standard revelation principle argument, we can assume w.l.o.g. that is IC in step h. Hence, by (I), we have
v Σ Ph- Ph- 1s, o) (T(al;; (In(s, a) + V (o; w, " a) s,w,a
(7)
Letting 7 (a w) = (a w: for every w E Ω and v'))) = V (o; ō) for every ā E E, we establish (3). (Recall that E S x x QA A A denotes the set of all possible interactions within one time step.)
Since P is IC in step h, (4) also follows immediately: the agent cannot benefit from any possible deviation. By definition, we have v') V (o; Vo+1 for every Σ that contains o', so (5) holds.
Now consider the "if" direction. Suppose that (3) (5) hold for some ग and v'. Pick arbitrary E -n-1 that ends with o. Consider a policy π such that: 7(a 0; w:w) = (aa w) for all w E Ω, and ra o) = ra w) for all Σ and w Ω2 where n' is arbitrary policy that induces v'()) for every ō (which exists given (5)). Namely, и is the same as π in step h and switches to in the subsequent steps. Given (4), the agent cannot benefit from any deviation at step h, so (3) gives the players' values for π and an optimal deviation plan of the agent. Hence, v E (o()).
Lemma 4. For any constant c > O, can be computed time poly((S)+(A1110)),) H, 1/)) the half- space representations of a set of polytopes Vo,(o) C Vn(o), E O (Ø) and h = 1, H, such maxvev oP that (3), (4) and (6) are satisfiable for every E Va(o) and max (2) x v
Proof. Throughout the proof, we say that the polytope Va(o) is e-approximation of Vv (0) if and only if:
(o) S (o) and
for every Va(o), there exists v' E Pn(o) such that v 2 up - and u/ A
We will show that an e-approximation (Ø) of (Ø) can be computed efficiently, that (2) o 2 maxvevi oP -c follows readily.² Meanwhile, we also show that the polytopes we compute ensures that (3), (4) and (6) are satisfiable for every E (o).
We now prove by induction. The key the following induction step. Suppose that the following conditions hold for all E O:
1. Vh+ (o) is defined by O(H/8) many linear constraints.
2. (o) is an E-approximation of Vo))(o).
In the definition of e-approximation, the dimension of A are the same (i.c., / = ~²), so that the approximation compromises only on the principal's value. This is crucial for ensuring exact IC and smooth changes of the approximation throughout the induction process present below.
require additionally that the projections of V (0) and Va(o) onto
21

---

We show that, given the above conditions, for every o E O we can compute in time polynomial in 1/ó polytope Va (o) (in half-space representation) that satisfies the above conditions (for h), with an approximation factor s' = E + ô in the second condition. Once this holds, picking 6 = H then gives, by induction, that (2)) is an e-approximation of V1 (Ø) (where e is the target constant in the statement of the lemma). Note that as a based case, {(0. 0)} is readily a O-approximation of VH (o) and can be defined by three linear constraints.
We proceed as follows. For every o E O, let Va denote the set of vectors v satisfying (3), (4) and (6).4 We follow the algorithm presented in Fig. 2 and discretize [0, H to construct (o). Specifically, we slice the space along the dimension of the principal's s value. We compute the inter- section points of the slice lines and (the boundary of) Vo(o). and construct (0) as the convex hull of the intersection points to approximate (o). Specifically, let W {0, 6, 25, .... H 5, H} contain the principal's values on the slice lines we use, and let W be the set consisting of the following points.
First, for each w E W, the two intersection points of the slice line at w and (o):
V E arg ve (o),,o))==== a and V E arg max (oV) v.
Moreover, two vertices of (o) with the minimum and maximum values for the agent:
V. E arg min veV. v and v. E arg maxveV V.A If there are multiple maximum (or minimum) vertices, we pick arbitrary one. An illustration is given in Fig. 1.
It shall be clear that the choice of these points ensures that we can approximate any inducible value vector with most ō compromise on the principal's 's value and no compromise on the agent's. (In particular, the inclusion of v. and v. ensures that we do not miss the agent's 8 extreme values that may not be attained at any of the slice lines.) All the points can be computed efficiently by solving LPs that minimizes (or maximizes) vA (where we also treat v as variables in addition to the other variables), subject the linearized version of (3), (4) and (6), and additionally of = w when we compute V. or V... The hypothesis that V (o) defined by O ((H/5) linear constraints ensures that all the LPs are polynomial sized and hence can be solved efficiently.
We then compute (o) by taking the convex hull of W. Given that the space is two-dimensional, this can be done efficiently via standard algorithms computational geometry (e.g.. Chan's 's algorithm (9]). This way, the first condition in the inductive hypothesis holds for (o) because (1) has at most O(H/d) vertices while it is in R Meanwhile, (0) is an 5-approximation of V (o) according to the following arguments.
Claim 1. (o) is an ô-approximation of Vn(o).
Proof of Claim 1. First, since W S (o) by construction, Di(()) C (A(o) S (a) holds readily.
It remains to show that for any E (o) there exists x E Pa())) such that A = UAA and xP 2 uP 8.
Let B = (v' E R2 i6 < /P < (i + 1)8} be the band between two slice lines that contains v. Consider the relation between AAA and the agent's minimum and maximum values attained at W n B. There can be the following possibilities.
Case 1. A lies in between the minimum and maximum values, i.e.,
min v'EWnE
A
< A
max
y/A
v'EWnB
This means that there must be point
ConvexHull(W n B3) such that '¹ = vA, We have x E ConvexHull(M) n B) C B. So both v and x are inside B. According to the definition of B, this means xPP > P 8, as desired.
*Note that (o) is different from V. (o): the latter, according to Lemma 3, is defined by (3) (5), where (5) uses the exact value sets Vo+i(o'), unlike the approximate ones Dn+ in (6).
22

---

Case 2. v < minw v'A In this case, it must be that v. & B (otherwise, minv'ewnn yn in S v*). Now that v B, the line segment between v and v. must intersect with the boundary of B (i.e., one of the slice lines) at some point y. We have y < v (because i I vA by definition) and y E (o( (because v, v. E Va(o)). Pick Vw where w = y.. By definition i I S.A. It follows that
min
V'EWNB'
This a contradiction because we have V. E WWB B as y is on the boundary of B.
Case 3, A > maxyrewn v/A, An argument similar to that for Case implies that this case is not possible, either.
Hence, only Case possible, where a desired point x exists. The claim then follows.
The fact that Vi S (o) also implies that (3), (4) and (6) are satisfiable for every E ()()), they are for every (o). We next confirm that (),()) is eventually (s + apprroxxmaaioonn of Vi, (o). Indeed, now Claim indicates that ()) is an 8-approximation of (o). so (o) an (E + apprroxxxianoo of (o) long (o) an e-approximation of (o).
To see that (o) is E-approximation, consider an arbitrary Vo(o). By Lemma 3, v can be induced by some and v' satisfying (3) to (5). By assumption, every ( is an e-approximation of (o'). so for every onward vector v' E Vn-1(d'), there exists a vector v' E Vx+1(o') and (o) = (6). Using v' instead of v', the same policy then induces vector v E (o) approximate same under v' and v', so the same response of the agent can be incentivized. This why we require the approximation the overall difference between eP and of is at most because it holds for the coefficients that EawaPh-1l6 w (o) (Taa(aaa w) 1. As result, iP up and (o) an s-approximation of (o).
such that 5d (ō) 2 w (ō)
Indeed, the agent's values are exactly the
not compromise on the agent's value, Moreover, according to (3),
Hence, the inductive hypothesis holds for h. By induction, Di (1)) is an 8H aproooiooinnttioon of V (g). Since 8H e. we get that m oP maxvev,(2) u
Theorem 5. There exists an e-optimal IC policy æ such that, for any given sequence (o; w. wiA) S2 the distribution x1- a(-1a;w?, ,.A) can be computed time (, 1/c).
Proof. Consider the algorithm presented in Fig. The outputs of the algorithm over all possible
input sequences (a:w", (,,A) E Σ x Ω specify a policy æ. The polynomial running time of the algorithm for computing each x(- a[:1o, (AA) follows by noting that it runs by solving at most H linear constraint satisfiability problems.
remains to argue that æ is and e-optimal. Indeed, by Lemma 4 and an inductive argument, æ IC at each time step h and induces the corresponding values encoded in v' as the expected onward values. The e-optimality of follows given the condition maxveD (0) u 2 maxvev( uP stated in Lemma (and the choice of the initial v in Fig. 3).
A.2 Omitted Proofs in Section
Lemma 9. There exists c-optimal 5-IC policy a such that, for any given sequence (o; wo: (,AA Σ x Ω, the distribution T( o; (AA can be computed in time pol)(())-AA)111)), H, 1/e,
(18)).
Proof. The proof is similar to the approach in Section 3.1, which computes near-optimal and 0-IC policy. We describe the differences below.
Instead of maintaining two-dimensional sets of inducible values, we split the dimension of the agent's s value into two dimensions A and ef, which represent the agent's values under his truthful response (i.c., L) and his best deviation plan, respectively. Hence, each V(() is now tuple (vf v v
23

---

(In Section 3.1, V and in are eventually forced to be the same, so there is no need to keep an additional dimension.)
The inducibility of a vector v (vP, vA, vf is characterized by the following constraints. First, we impose the same constraint as (3) on the first two dimensions of v, so that they capture the players' payoff's under the agent's truthful response. In order for the third dimension oy to capture the agent's maximum attainable value, we use constraint similar (4):
Σ Ph- Ph-11wA
E
max Σ
Ph- P8-1 (0, maaaaaa
max
aA
B,N .aF
(rA(s,aP,, + (8,,,,
(8)
The remaining constraint is the same as (6).
All the non-linear constraints can linearized the same way as the approach described in Section 3.1. Hence, we can efficiently approximate (o) by examining the inducibility of points on a sufficiently fine-grained grid in [0, H]S. which contains poly (H, 1/E) many points, and constructing the convex hull of these points. (Note that there is no need to ensure zero compromise as required the proof of Lemma
the agent's s value This because 5-IC is defined with respect to the agent's expected value at the beginning of the game instead of that at every time step. Hence, using points on grid suffices the purpose of the approximation in this proof.) The half-space representation of the convex hull can be computed efficiently given that it is in IR3 [9]. Eventually, an optimal ı E II, corresponds solution maxveVi (2) o subject A 2 v 6, and we can use the same forward construction procedure in Section 3.2 to compute Tr. ( a w ..AA)
Note that (8) only enforces of as an upper bound of the maximum attainable value, instead of the exact value. This suffices for our purpose because any (v,, v v in the feasible set (1(2) n {v: A 2 E c3 also implies the inclusion of (2P, v 6A) ) in the same feasible set, where a is the actual maximum attainable value induced by the policy that induces (v", e v.A according to our formulation.
Theorem 10. There exists algorithm that guarantees regret 0(53/3/2/3) for both players with probability q. where Ç H |S| A 11/2" The computation involved in implementing the algorithm takes time poly([ H,T).
Proof. We run reward-free exploration obtain model f with error bound 8/2. This can be achieved w.h.p. in (((/8²) episodes according to Lemma 7. Next, we compute an d-optimal strategy E πl and use in the remaining rounds. According to Lemma 9, this can be done in polynomial time.
By assumption, rewards are bounded in [0, 1] so the regrets are at most 1 for both players in each of the exploration episodes. In each of the remaining episodes, the agent's regret is as follows, where pick arbitrary p* arg max, V/A (AA))(()))
VA (0) V, (0) < DA (0) 1.A.T. (0) +
26 Fef
DARP (0) - VAA. (0) + ( - VA < 28.
(0)-VAA,
Ló Lemmna?
The principal's regret is:
V VP. (2) = max V.P V.P.''L -PP
s' r'lllo
max V.P
v.P.''. + - (B) < max PP,'' - r'llls
(Ø) +8 < 28.
x'Ells
as Cñ,
<8 as 6-optimal
24

---

The reason that II - IIg is the following: Since P ensures enror bound 5/2. we have "()) - y ( & 6/2 for all p. By definition, n' E Io means that V Vi 1 (2) 2
(AT-P(0)) So, V.A. (Ø) 2 V (()) å for all p. hence, T' Iis.
The above bounds then lead to a total regret of at most Ō(C/6)) + O(6)) for each player. Taking
5 = (C/T) gives the upper bound (((1/372/3)
B Linearizing (3) and (4)
Specifically, remove the maximization operator in (4), we introduce set of auxiliary variables vla", wn wA ) to capture the maximum values on the right hand side of (4). We replace the right hand side of (4) with Eetear y(a*, wA, aA), and by adding the following constraint we force each
v(a", wn (AA) to be an upper bound of the corresponding maximum value: for all ã^ E AA,
v(a" wn x))) Z
Σ
(n-1(8, w (o,w") #(a ([alw,, ,0AA),))A..)))))))). (rā(s, ,aA) o o (s,w, a a²))
(9)
To remove the quadratic terms in (3) and (9), each term F(a w) v'(s, @AA a²) and impose the following constraint 2:
auxiliary variable z(s, w, w, a, a²) replace
H (s,, w, WA a. a²) S 7 w) b,
(10)
where H and b are taken from the half-space representation of the polytope Va+i. i.e.. Da+1 (s, al, aaf [x H < b). is straightforward that, when Di+1 (s, aP, a.a))) is nonempty and bounded, (10) holds if and only if z(s, w, aAAA a, a²) = #(a ([| x for some x E Vn+i a,, a²). Hence, (10) is the only constraint needed (for each tuple (s, w. L. a, a²)) after we replace the terms with z.
The Complete Formulation In summary, the above approach yields the following linearized version of the constraint satisfiability problem in Section 3.1, where म, z = (= x2 ),), and y are the variables (highlighted in blue).
1. The value function constraint:
Σ (h- (r)(s, ( + as 8,w,
2. An IC constraint for each wA s2a:
Σ Ph-1(s, (. (1²(s, a(aa w) 2 (s.w..t, Σ 30
aAEA
Moreover, for each tuple (AA, wA, E AA 22 sAa
y (a
(n-1 w (o,wA) ( (1 (s, aP, aa) a(a (a,))) ) + AA (s, (,,,
8,00 .aP
3. An onward value constraint for each tuple (s, w. WA a, a²) E Σ:
H (s.a² a a²) z(s, w. WA a, x²) i w) b (ss (s. aa)
where for every o O, the matrix H()) and vector b(o) are given by the half-space representation of (n+i(o), i... ()+2(0)= (v' H()) v' < b(o)).
4. Additionally, we impose
ww| () E ((A)
for each Ω to ensure that .(- w) is valid distribution over A.
'Note that if a(a (w) 0, then (10) imply that z(s, w, ar a, a²) 0: otherwise, the fact that x' 2(ss, w, A ف+)) satisfies H x' I b for any 0 and Dati a?, a²) would prevent Dati(s, a., d²) from being bounded.
25

---

C Additional Discussion about Intractability without Hindsight Observability
The PSPACE-hardnest can be seen by thinking of a POMDP as an instance of our problem where only the principal can make observations and perform actions to influence the environment (essentially, the agent can neither influence the principal nor the environment this instance).
The PSPACE-hardness remains in the case of information design, where the principal observes the state directly but does not act, while the agent makes no observation but acts; well the case of mechanism design, where the agent observes the state directly but does not act, while the principal does not observe but acts. This can be seen by considering zero-sum instances, where the principal's and the agent's 's rewards sum to zero.
More specifically, consider for example the case of information design. If the goal is to compute the principal's 's maximum attainable payoff, the PSPACE-hardnee of the problem is immediate: Since the game is zero-sum, it is optimal for the principal to not send signal (if signaling were improve the principal's 's payoff, the agent would be better-off just ignoring the signals). Hence, computing the maximum attainable payoff of the principal in this case is equivalent to computing (the negative of) the agent's maximum attainable payoff, which amounts to solving a POMDP.
One may argue that while the above example demonstrates the hardness of determining the principal's maximum attainable payoff, computing the principal's 's optimal policy is actually trivial in the example (i.e.. sending no signal is optimal). So it does not rule out the possibility of an efficient algorithm which, given any sequence, computes the signal distribution of an optimal policy, without computing the principal's 's payoff the policy yields. It turns out that this is not possible, either.
Consider game where the agent can choose between two actions and b the first time step. Action leads to process where the principal's 's rewards are zero for all statenaction pairs. Action b leads to another process with payoff's x for the principal and x for the agent, where x E [0, 1] depends on the principal's ss signaling strategy in this sub-process. For example, we can design this sub-process as a matching pennies game, where: nature flips fair coin, the principal observes the outcome, and the agent must choose the same side of the coin to get a reward 1 and otherwise he gets -1. If the agent plays this matching pennies game on his own, his expected payoff is 0. The principal can reveal her observation to help the agent to improve the payoff. And the principal can do so probabilistically, so that she can fine tune the agent's s expected payoff x to any desired value in [0, I]. To maximize the principal's 's payoff in the entire process requires finding an that is sufficiently high, so that the agent is incentivized to choose b (otherwise, the principal only gets 0); at the same time, we would like x to be low possible to maximize the principal's 'ss payoff 1 x. This essentially requires knowing the agent's ss maximum attainable payoff in the sub-process following o, which is PSPACE-hard as we discussed above.
26


Reviews:
[{"review_id": "CD4e0tweCZ", "reviewer": "Reviewer_RCDp", "summary": "The paper analyzes a sequential principal-agent game in which, at every round, the principal observes her private signal, elicits (truthfully or not) the agent’s private signal, and then sends non-binding action recommendation for the agent.  Crucially, it imposes hindsight observability: once the round ends, the entire log—hidden state, both private signals, recommendation, chosen actions, and pay-offs—becomes common knowledge.  \n\nWith the transition dynamics known, the authors show that an approximate incentive-compatible commitment policy can be computed in polynomial time.  The key device is the inducible value set: a two-dimensional convex polytope that lists every pair of (principal payoff, agent payoff) that remains achievable from a given state-action pair while keeping the agent willing to comply.  A backward dynamic program updates these polytopes, yielding both the optimal value and a constructive policy.\n\nWhen transition dynamics are unknown, the method is extended with reward-free exploration. After collecting enough trajectories, a modified version of the algorithm yields an approximate incentive complatible policy with regret growing as T^2/3.", "questions": "- In settings where only part of the interaction log can be revealed, do you see a principled way to adapt inducible value sets so that tractability is preserved, perhaps with approximation guarantees?\n- Do you intend to implement the algorithm on synthetic or real-world benchmarks to test runtime and sample complexity? If such experiments are not planned, what do you see as the primary bottlenecks for implementation?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n- The paper is well written: definitions, lemmas and algorithms are laid out cleanly, and intuition is provided alongside formal results.\n- The paper introduces hindsight observability, a theoretically valuable assumption that renders the model tractable yet still incentive-rich.\n- The introduction of inducible value sets, enabling a polynomial-time dynamic-programming solution while embedding incentive constraints, is a solid technical contribution.\n\nWeaknesses\n- Despite clean, hindsight observability means that every private signal and action becoming public at the end of each round, which significantly limits practical reach.\n- As the author also acknowledges, the method does not scale well to multiple followers, further restricting its scope.\n- The paper provides no empirical validation, so the practical runtime and sample-complexity costs remain untested.", "was_revised": true, "final_justification": "I’m satisfied with the authors’ rebuttal and maintain my positive rating for the paper.", "rebuttal": "Thank you for your very insightful and valuable comments and your positive assessment of our work! \n\n---\n\nBefore we address your individual comments/questions below, we’d like to first highlight the following main points: \n\n- The limitations and scalability issue of our approach **are due to computational complexity barriers intrinsic to the problem itself, rather than the deficiency of our algorithm.** We will explain this in detail below.\n\n- More importantly, even though our approach is still subject to these computational barriers, **traditional approaches based on stationary strategies would only be worse:** they are intractable even when there are only a constant number of players and when hindsight observability is assumed. \n\n- The main insight of our results is that **history-dependent strategies—though seemingly unamenable at first glance—become feasible with our approach and, thanks to that, we are able to overcome critical limitations of stationary strategies.** This makes our approach computationally more advantagious than approaches based on stationary strategies, which dominate the current literature. \n\n---\n\nRegarding your specific questions:\n\n**1. Hindsight observability is inevitable due to intrinsic computational complexity barriers**\n\nThe assumption of hindsight observability, even though restricted, is inevitable as the problem would subsume POMDPs without such assumptions. POMDPs are known to be intractable (PSPACE-hard). Hence, unless PSPACE = P (which is widely believed unlikely as this would be even stronger than P = NP), it would not be possible to find any efficient algorithm without making additonal assumptions on the structure of the problem. (Please also see Appendix C in our supplementary material for a detailed discussion about the intractablility without hindsight observability.)\n\n**2. Scaling to multiple followers is NP-hard even in one-shot settings (as implied by [Papadimitriou & Roughgarden, 2008])**\n\nOur solution concept generalizes the correlated equilibrium. Since our goal is to find an **optimal** equilibrium, with $n$ players, the problem is unfortunately known to be NP-hard even for one-shot games [Papadimitriou & Roughgarden, 2008]. \n\n**3. Settings where only part of the interaction log is revealed**\n\nIn settings where only part of the interaction log is revealed (say, only the state is revealed), our algorithm based on inducible value sets is still applicable and will generate a policy in polynomial time. We do not know if this policy has any approximation guarantee though, **but we can at least be certain that it outperforms the best stationary policy.** Since different players may observe different part of the interaction log under partial observability, to compute optimal policies in such settings requires working with belief states, but the belief state space grows exponentially with the size of the problem instance. **This is exactly also where the intractablity of POMDP stems from, so in general there is no efficient approach to deal with such settings.** It is possible that under some structural assumptions weaker than hindsight observability, the problem remains tractable. To identify such assumptions (and whether they exist at all) require further investigation, which we think is beyond the scope of this present work.\n\n**4. Re: Experiments**\n\nSince our aim is to establish the theoretical foundation of the model, especially the tractability of history-dependent strategies, we didn’t conduct any experiments in the current work. We are indeed interested in evaluating our approach empirically, and we do not see any sever bottleneck for implementing the algorithm. Scalability may be one issue if one wants to implement the algorithm for many agents/followers. In this case, heuristic algorithms would be a more practical option, as is the case with many other NP-hard problems. We believe that our results remain constructive in this domain and inform the design of heuristic algorithms about the importance and advantage of history-dependent strategies. \n\n---\n\n**Reference:**\n\n- Christos H Papadimitriou and Tim Roughgarden. Computing equilibria in multi-player games. SODA ‘05.\n\n---\n\nPlease let us know if you have any further questions. We would be more than glad to provide additional clarifications."}, {"review_id": "5Mae0jjKyP", "reviewer": "Reviewer_o1dQ", "summary": "The paper studies a dynamic principal-agent problem modeled by POMDP, as the policy could depend on the history. It aims to find a policy for the principal so as to maximize its reward, assuming that the agent responds optimally. Under hindsight observability, the paper proposes an algorithm based on computing inducible value sets and optimal policies. Then the paper considers an online setting with episode RL.", "questions": "Motivation: Why is it necessary to consider POMDP instead of a normal MDP?\n\nSince the policy is history-dependent, there could be a scenario tree getting involved in the algorithm, but how the authors address the curse of dimension remains unclear. \n\nContribution in Line 62, it should be stated what the key motivation is for addressing history dependence. \n\nThe notation system is very hard to understand. For example, there are multiple notations at the beginning of Sec 2 and a lot of new notations in Sec 2.1. In addition, the same notation is widely abused with several meanings and several different input set. \n\nThm 3.7, what is the definition of  an $\\epsilon$-optimal IC policy?", "limitations": "NA", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The idea to overcome NP hardness via hindsight observability and computing the optimal policy in polynomial time is quite surprising. \n\nThe major weakness is that the writing makes it very hard to comprehend the main idea and verify the claims made in the paper. \n\nA few questions related to motivation: why it is important to consider history-dependent policy instead of a Markov policy? \n\nDespite the fact that the paper seems to achieve a poly time algorithm for the very hard POMDP problem, the lack of experiments in the main context makes it hard to judge how significant the improvement it achieves.", "was_revised": true, "final_justification": "The paper studies a challenging problem and addresses it well. The writing is an issue yet I believe that authors could handle it properly.", "rebuttal": "Thanks a lot for your very insightful comments and questions; they are greatly appreciated! Below are our answers to the your questions.\n\n---\n\n**Re: Why POMDP instead of MDP?**\n\nWe consider POMDP because it captures information asymetry between different players, while a standard MDP is insuffient for this purpose.\n\n---\n\n**Re: Why history-dependence?**\n\nWe introduce history-dependence to the model and view it as the main contribution of the work because of the following reason (as we also explained between Lines 49 to 69 on Page 2):\n\n1. **History-dependent strategies offer higher utility than stationary (Markovian) ones.** History-dependent strategies are by definition a generalization of stationary ones. In the multi-player setting we consdier, they offer strictly higher utilities than stationary strategies in many problem instances. (For example, tit-for-tat is a history-dependent strategy, which is necessary for achieving optimality in some sequential games.) This is very different from (single-player) MDPs, where stationary strategies are always sufficient for achieiving optimality. \n\n2. **History-dependent strategies are computationally more advantagous than stationary (Markovian) ones.** Besides being suboptimal, stationary strategies are also computationally intractable, as reveald by previous work [Gan et al., 2022]—it is NP-hard even just to approximate the best stationary strategy. In contrast, our main finding in this paper is that optimal history-dependent policies can be computed in polynomial time (in the same setting where stationary strategies are intractable).\n\n---\n\n**Re: How did we address the challenges of handling history-dependent strategies**\n\nYes, you are right. History-dependent strategies are hard to deal with because of the exponential growth of possible histories as the time horizon gets longer (if we understand correctly, this is what you meant by \"scenario tree\" in your comments). For each history, one action distributon needs to be defined, so explicit representations of history-dependent strategies would be too costly to be efficiently managable. Our approach can be viewed as a **compact representation** to overcome this representational issue. Effectively, the algorithm in Figure 2, along with the inducible value sets computed by the algorithm in Figure 1, encodes a history-dependent policy $\\pi$, so that for any given history trajectory $(\\sigma;\\omega^P, \\tilde{\\omega}^A)$ (i.e., any path in the scenario tree), the algorithm computes the action distribution $\\pi(\\cdot | \\sigma;\\omega^P, \\tilde{\\omega}^A)$ defined by this policy. This is a key technical novelty our work introduced to overcome the challenges of handling history-dependent strategies. Please also refer to our discussion in Section 3.2 for more details.\n\n---\n\n**Re: Definition of $\\epsilon$-optimal IC policy**\n\nAn $\\epsilon$-optimal IC policy is a policy that is $\\epsilon$-optimal and also IC. IC is defined in Defintion 1 (Page 5). And $\\epsilon$-optimality means that the payoff it offers is as high as that offered by an optimal policy, up to a difference of at most $\\epsilon$ (as explained in Lines 186--187, Page 5).\n\n---\n\n**Reference:**\n\n- Jiarui Gan, Rupak Majumdar, Goran Radanovic, and Adish Singla. Bayesian persuasion in sequential decision-making. AAAI ‘22.\n\n---\n\nWe sincerely hope that our answers above have clarified your questions and would be very grateful if you could consider raising your scores accordingly. If anything remains unclear, please let us know and we would be more than glad to provide further details!"}, {"review_id": "YCGYLv4YJu", "reviewer": "Reviewer_HYK4", "summary": "The paper shows that optimal and exactly IC solutions can be computed efficiently in two-player stochastic games with asymmetric information by extending a recent idea of using value polytopes.", "questions": "Could you please comment on my questions above? Specifically:\n\n1. Technical obstacles\n2. Assessment of the difference with Gan et al. and Bernasconi et al.\n3. Intuition for point 3 of figure 1.", "limitations": "Yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Computation of Stackelberg equilibria in stochastic games is not my area of expertise, so I will focus on clarity of the contribution.\n\nOverall, I find the paper well written. The technique used in the paper, based on value polytopes, seems to have been used already in a few papers (as mentioned by the authors at the end of the related work section). However, if I understood correctly, the authors claim that they are able to use the idea of inducible values to guarantee exact incentive compatibility, unlike prior work. So, there seems to be a tangible improvement, though it is hard for me to quantify how technically challenging (or, conversely, incremental) this is. I would have appreciated more clarity regarding the technical obstacles that the authors had to overcome to establish this refined result. \n\nAnother point of comparison is the paper by Gan et al.. That paper is for turn-taking games, whereas the current paper seems to be more general, although somewhat related in terms of techniques (Gan et al. also keeps a sort of \"Pareto frontier\" via constraints if I understood correctly). Is this assessment accurate?\n\nOverall, I found the discussion in Section 3 quite terse. An example could have gone a long way. Furthermore, I am still slightly puzzled about how and why it is possible to compute the H-representation of the value polytope efficiently, given that usually converting from V- to H-polytopes (say, using double description techniques) cannot be tractable in general. Is there any intuition regarding this?\n\n\nMinor points:\n- Citations [2], [6], [17], and [40] are to an arXiv preprint. Were the corresponding papers published anywhere? If so, please update to use the published version, unless there is a specific reason not to.\n- Citations [3] and [22]: \"pomdp\" and \"mdp\" should be \"POMDP\" and \"MDP\", respectively.\n- Citation [34]: \"markov\" -> \"Markov\"\n- Citation [27]: the citation is missing a venue, journal, publisher, or similar.", "was_revised": true, "final_justification": "The authors did a great job at answering my questions. I now have a better appreciation of the contribution, and have raised my score accordingly.\n\nAs discussed below, the authors resovled my questions regarding the connection with existing work, and have also resolved a concern on a technical claim.", "rebuttal": "Thank you for your very insightful comments and positive assessment of our work! We will cerntainly fix the citations and other minor issues you pointed out. Thanks a lot for pointing them out.\n\n---\n\n**Re: Difference with Gan et al., and Bernasconi et al. (as well as Zhang et al.)**\n\n_(It seems that in your comments the paper you wanted to refer to is Zhang et al. 2023—titled “Efficiently solving turn-taking stochastic games with extensive-form correlation”—but you pointed out Gan et al. instead. Please see our remark about the paper of Zhang et al. at the end of this answer.)_\n\nGan et al. (2022) first introduced a similar sequential information design model, **but their focus is on stationary strategies, which is less general than history-dependent strategies we considered in our paper**. Gan et al. showed the intractablity of stationary strategies (NP-hard to optimize even approximately), which is one of the main motivations behind our consideration of history-dependent strategies. To the best of our knowledge, Gan et al.’s approach did not involve constructing inducible value sets or anything alike. Their main positive result is an efficient algoritm that works but only with myopic (or advice-myopic) agents. In our paper (and that of Bernasconi et al.), the agent is far-sighted (which is strictly more general than myopic agents).\n\n**Our work is in fact concurrent with Bernasconi et al.** (their preprint version appeared after ours but their work got published ealier). We would therefore hope that our contributions could be evaluated based on their own merits, rather than being considered as subsequent to Bernasconi et al. **Besides preceeding the work of Bernasconi et al., our results are also stronger**, as we explain below:\n\n-  Our algorithm provides better guarantees: using a novel slice-based discretization, it ensures **exact IC (incentive compatibility)**. In comparision, the approach of Bernasconi et al. only ensures **approximate IC**, whereby the IC constraint is alway violated by a $\\delta > 0$ amount. \n\n- Our model allows partial observability of both the principal and the agent, and two-way communication between them. In comparision, **Bernasconi et al. considered an information design model, which is only a special case of ours.** In their model, only the agent has partial observability and communication is uni-directional: signals only go from the principal to the agent, not the other way round.\n\n- In addition to the computation problem, we also explored the learning version of the problem in Section 4, whereas this was not considered by Bernasconi et al.\n\nP.S. It seems that in your comments the paper you wanted to refer to is Zhang et al. 2023, instead of Gan et al. 2022. In the paper of Zhang et al., they considered turn-taking games and used the notion of Pareto frontier. The high level idea of their approach and ours are similar, but since they are consider a more special case of the model (that is turn-taking and without any information asymmetry), they were able to design a very sophasiticated algorithm to compute an exact optimal solution, without involving any approximation errors. It remains open whether this approach can be extended to our more general setting (which appears very challenging, perhaps not even possible, as the approach is already highly sophasiticated even with turn-taking games.)\n\n---\n\n**Re: Technical obstables** \n\nFollowing our responses above, the main technical obstables we overcome in this paper are the following:\n\n1. Enabling the use and efficient computation of history-dependent strategies (which were also addressed concurrently by Bernasconi et al.). This is non-trivial especially because of the exponential growth of history trajectories. \n\n2. A novel slice-based discretization approach to ensure exact IC (which is missing in the work of Bernasconi et al.).\n\n3. Application of reward-free exploration to the learning version of the problem to achieve efficient learning.\n\n---\n\n**Re: Intuition of Point 3, Figure 1**\n\nThe Half-space representation can be computated efficiently because the polytope is in $\\mathbb{R}^2$. In fact, an easy algorithm that builds the H-representation of the convex hull of a set $P$ of points works as follows: enumerate ever pair of points in $P$, compute the line passing through each pair, and check if all points in $P$ are on the same side of this line (the same half-space). If yes, then keep this line as a linear constraint in the H-representation; otherwise, discard it. \n\nThis can further be generalized to **any fixed dimension $d$**, where we enumerate every combination of  $d$ points in $P$ and compute the hyperplane passing through these points. There are only polynomially many such combinations when $d$ is fixed.\n\nP.S. If I understand correctly, the conversion between V- and H-representations of a polytope is hard only when the number of dimensions is **not** fixed. This corresponds to the setting where the number of agents is not fixed in our model. As we also mentioned in the response to reviewer RCDp, if the number of agents is not fixed, then our problem (which subsumes computing an optimal correlated equilibrium) would be NP-hard even when the game is one-shot (as implied by [Papadimitriou & Roughgarden, 2008]).\n\n---\n\n**Reference:**\n\n- Christos H Papadimitriou and Tim Roughgarden. Computing equilibria in multi-player games. SODA ‘05.\n\n---\n\nPlease let us know if you have any further questions. We would be more than glad to provide additional clarifications."}, {"review_id": "l2shqctz2D", "reviewer": "Reviewer_o9Qq", "summary": "This paper considers a stochastic principal agent problem with history dependent policies. Once this generalized principal agent problem is introduced, the paper makes the following main contributions: \n\n1. It is shown that there exists an approximately optimal incentive compatible (IC) policy and the paper proposes a polynomial time procedure to compute the induced distribution for any given history of interaction and observation tuple in polynomial time (Theorem 5). From the technical viewpoint the procedure requires to compute polytope approximations of the so-called inducible value sets introduced by the paper using dynamic programming before one can unroll the optimal policy for a given history and observation tuple.\n\n2. In the episodic online learning setting where the transition model is unknown for the players, the paper proposes a centralized learning algorithm which guarantees a regret of order $T^{2/3}$ to both players with high probability, and which can be executed in polynomial time in the problem parameters (Theorem 10). The algorithm follows a explore-and-commit strategy which involves a first reward-free exploration step to learn an estimate of the transition kernel followed by a second step for computing an approximately optimal approximate IC policy using the estimated kernel. In particular, the learning algorithm requires relaxing the IC constraints compared to the result of the previous section.", "questions": "1. Clarification question about hindsight observability: Both players (and the agent in particular) observe the full history *at the end* of each time step. I find it a little confusing that the deviation plan (l. 176) for the agent takes the history as input (including the last principal’s observation and action?). Can you clarify this? \n\n2. Before committing to approximation, is there anything known or that can be said and exploited about the geometry of exact value sets beyond nonlinearity? Also can you make the point in l. 248 clearer? Ou argue about nonlinearity: What are the quadratic terms in the expressions? Also there is no max term in (3) which seems linear in v’. Nonlinearity is somehow clear from the max but less so from the rest.  \n\n3. What is exactly the output in step 3 of Fig. 2? You say $\\bar{\\pi}$ (which is a one-step policy as mentioned in l. 225), is it the last one computed in the loop? Is the output the ‘concatenation’ of the $h-1$ ones computed so that it’s a history dependent policy? It’s a little confusing. \n\n\n4. Is there a way to compute an optimal policy recursively without needing to compute first all the inducible value sets and then perform the unrolling? Say simultaneously using the inducible value sets and approximate the optimal policy for a given history and observation tuple if that makes sense. \n\n5. l. 341-348: I am a little confused by the comparator in this learning part. You resort to relaxation for IC constraints which seems reasonable, but then the final comparator in the regret is not adjusted for this, i.e. you still compare to V^* which is the optimal value of (2) where the lower level (agent’s problem) is not relaxed with $\\delta$-IC. \nCan you clarify why you can still achieve vanishing (average) regret w.r.t $V^*$ and the (true) best response for the agent? Do you reduce $\\delta$ in some way? Otherwise there should still be a bias in the final regret bound and a dependence on $\\delta$ I guess. \n\n6. Is there a way to provide a sharper characterization of the dependence on $\\epsilon$ for the problem, more than just polynomial? Is it related to the discretization? Can such a discretization be avoided? \n\n**Additional, more minor questions:**\n\n7. Optimal policy unrolling: This kind of procedure reminds me of what is sometimes called *local planning* in RL which can be done efficiently in polynomial time given a state for instance to compute the optimal policy at that state (see e.g. Szepesvari’s lecture notes online). Is this accurate?\n\n8. Is the order of regret a consequence of the reward free exploration procedure? Because the quality of the approximation (order in epsilon) is not really specified in Theorem 5 whereas the order is precisely given in Theorem 10. Is it optimal up to improving the reward free exploration step? Is there still room for improvement?", "limitations": "See weaknesses section.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "**Strengths** \n\n- Solving repeated principal agent problems is an active topic of research nowadays, including in the ML community. The paper adds to this literature by considering a sequential stateful setting with far-sighted agents and history dependent policies beyond simpler stationary policies. In my opinion, this is an interesting addition although I am not an expert in principal-agent problems and I leave experts of the room provide a more accurate judgment in view of existing literature. Considering history dependent policies definitely brings some complexity to the problem which is balanced by the hindsight (full) observability assumption. The appendix and technical developments (which I did not go over in details) seem rather compact. \n\n- The paper is overall well-written, notations are precise and the paper is generally easy to follow. Although the mathematical objects involve some complexity, the paper did a good job introducing nice and rigorous notations which make the paper readable, especially for (recursive) induced value sets, dynamic programming procedures, summaries of the algorithms in frames and a precise introduction of the problem in section 2 including the communication protocol and the setting of interest with the required assumptions.   \n\n- The results are sound but I have not checked the proofs in the appendix.\n\n**Weaknesses**\n\n- One of the highlighted contributions is a **generalized** framework for principal-agent problems. With this regard, I would expect a clearer positioning of the paper w.r.t the literature. The paper discusses related work. Nevertheless, it is not immediately clear to me from the paper which principal-agent problems are particular cases of the setting of this paper in the literature, among the papers dealing with sequential **stateful** settings (MDPs) which are the most relevant to this paper (if there are any). I think that would clarify further the generality of the model and the positioning of the paper: \n\n-- More precisely, can you elaborate more precisely on the differences than in l. 95-108? The model seems different in several aspects via communication and the use of history dependent policies for instance as well as the setting itself (not contract design like in Wu et al. 24, Ivanov et al. 24 and others) … \n\n-- Can you also clarify the positioning w.r.t. Stackelberg (Markov) games? E.g. Bai et al. Neurips 2021 Sample-Eﬃcient Learning of Stackelberg Equilibria in General-Sum Games. There are also several more recent works about learning Stackelberg equilibria. \n\n- l. 317-323: About hindsight observability and reward-free learning: Are the sampling requirements aligned here? You reframe your problem as an MDP but do the MDP works you use rely on a generative model (which is a standard assumption in RL), i.e. the ability to query a next state from any given state action (not necessarily only the ones observed online during the interaction)? Is this a reasonable assumption in your principal-agent setting with hindsight observability? Is it reasonable to assume that one can query the next state from any state $\\theta$ (which combines actions of both players for instance) while hindsight observability seems to only give access to a history of interactions between the principal and the agent? \n\n- One limitation might be that the algorithm is centralized. I would imagine that players in a Principal-Agent setting would rather act independently. Who is computing the optimal policy exactly? The principal? Is it reasonable to assume the principal (or some central entity) has access to all information (in hindsight) for both players (actions for instance)? \n\n **Typos and suggestions**\n\n- l. 234: is it rather $\\tilde{\\omega}^A$ here for the IC constraint? \n- It might be useful to remind in Fig. 2 step 1 that $v= (v^P, v^A)$ and that $v^P \\in \\mathbb{R}$. \n- l. 340: I guess $\\delta$ should be $\\epsilon$ here?", "was_revised": true, "final_justification": "The rebuttal response addresses my concerns regarding generality of the PA model and the positioning of the work with respect to prior work, computation of the optimal policy and the hindsight observability feedback assumption. The illustrative examples for this assumption are appreciated. I believe that the ability to enable history dependence in optimal policy design is a nice feature of this work within the growing literature of principal agent problems. I maintain my positive attitude towards this paper as per my initial review and recommend acceptance.", "rebuttal": "Thanks a lot for the very thoughtful comments! We find them very valuable for improving our paper. We will cerntainly fix the citations and other minor issues; thanks for pointing them out. \n\nOur answers to your other questions are as follows. If anything remains unclear, we would be more than glad to provide further clarifications.\n\n---\n\nFirst, regarding your questions in the **Strengths and Weaknesses** section:\n\n\n1. **Generative model.** To the best of our knowledge, the reward-free exploration algorithm of Jin et al. (2020) does not rely on a generative model. The algorithm relies only on state-action pairs encountered online. They have in particular introduced associated concepts such as $\\delta$-significant states to handle states that are hard to reach. Therefore, we believe that not having access to a generative model would not be an issue for our algorithm. (But please let us know if we didn’t understand your question correctly.)\n\n\n2. Our algorithm is **not** fully centralized in the sense that the principal does **not** have any control over the agent, who are free to deviate to whatever actions they prefer. Hindsight observability is indeed the case in many models such as games with full observability (which is fairly common in the literature) and information design (where one of the players have full observability). (Please also see our discussion at Lines 145--149.) From a computational complexity point of view, some degree of hindsight observability is needed for the setting to be tractable; otherwise, the problem would be as hard as POMDPs, which are PSPACE-hard. \n\n---\n\nNext, regarding your questions in the **Questions** section:\n\n**Re: Q1**\n\nIn the deviation plan, the agents takes into account the history in the previous time steps, which are seen by the agent because of hindsight observability. **In the current  time step, the agent only has access to their own observation**, so as we described at Line 176, the deviation plan does **not** rely on the principal’s observation in the current time step.\n\n**Re: Q2**\n\nIn Equations (3) and (4), **the quadratic terms are the products of the $\\bar{\\pi}$’s and $v$’s (i.e., terms highlighted in blue in the paper)**. When we say “the quadratic terms and the maximization operator in (3) and (4)”, we mean the quadratic terms in both (3) and (4) and the maximization operator only in (3); we do **not** imply that each equation contains both types of elements.\n\n\nWe did not find any other properties of the value sets that can be used to design efficient approaches to computing the exat value sets. All we know is that each set is a convex polytope defined by possibly exponentially many hyperplanes. \n\n**Re: Q3**\n\nIn Line 3 of Figure 2, the value of the output is equal to $\\bar{\\pi} ( \\cdot | \\tilde{\\omega}^P, \\omega^A)$, while it is interpreted as the distribution $\\pi( \\cdot | \\sigma; \\tilde{\\omega}^P, \\omega^A)$ (which is what the algorithm is expected to compute). Perhaps this line would be easier to understand if we break it into the following two lines:\n\n\n-  First, assign the value of $\\bar{\\pi} ( \\cdot | \\tilde{\\omega}^P, \\omega^A)$ to $\\pi( \\cdot | \\sigma; \\tilde{\\omega}^P, \\omega^A)$;\n\n\n- Then, return $\\pi( \\cdot | \\sigma; \\tilde{\\omega}^P, \\omega^A)$. \n\n\nAnd, yes, you are right: the value of $\\bar{\\pi}$ in Line 3 is computed in the last iteration of the for-loop in Line 2.\n\n\nNote that (as explained in the first paragraph of Section 3.2) our goal is to compute the action distribution defined by $\\pi$ for any given history, rather than the explicit representation of $\\pi$. And $\\pi$ is history-dependent because for different input sequences, the algorithm in Figure 2 will output different distributions. So $\\pi$ prescribes different joint action distribution for different histories.\n\n**Re: Q4**\n\nThis is a very interesting question. We don’t find any way to compute the policy and the inducible value sets simultenously. One possibility is to use policy-based approaches that compute optimal policies without maintaining the value sets. For example, if we could compute the gradient of the value function w.r.t. the policy, we might be able to use gradient descent to optimize the policy directly. This is a very interesting direction, but we have little understanding so far. Computing the gradient appears very challenging especially because we must also avoid using explicit representations of history-dependent policies at the same time. To work with the gradient of something that does not even have an explicit representation---if possible at all---appears to require highly innovative techniques.\n\n**Re: Q5**\n\nYes, you are right, when it comes to the regret, we still compare the value achieved against the optimal value achivable under the exact IC constraint. This is actually an easier benchmark than the one with the $\\delta$ relaxation. To see this please note that any solution to the problem with the exact IC constraint is also a feasible solution to the one with the $\\delta$ relaxation.\n\n**Re: Q6**\n\nWe are not aware of any approach that can further reduce the polynomial dependence on $1/\\epsilon$ in the time complexity. An associated open question is whether we can compute the exact solution efficiently. The latter has been shown to be possible in the special case of turn-taking games, where only one player acts in each time step and there is no information asymmetry. It remains unknown though whether this is also possible in our much more general model where the players move simultaneously under information asymmetry.\n\n**Re: Q7**\n\nYes, there are some similarities between our approach and local planning in RL you mentioned. Both of them are recursive implementation and are based on the Bellman equation (or its variant). But the unrolling process in each iteration is a lot more complicated in our case. It requires solving the problem we described in Section 3.1, instead of just a maximization problem as in RL local planning.  \n\n**Re: Q8**\n\nYes, you are right, the regret bound is a consequence of reward-free exploration. There is no $\\epsilon$ or $\\delta$ terms in the time complexity in Theorem 10 becasue we use specific $\\epsilon$ and $\\delta$ that are polynomials of the other terms to derive the regret bound. The details can be found in the proof of Theorem 10 in the appendix. It could be that the bound is tight but we don’t have any evidence so far; a lower regret bound can help to resolve this question. \n\n---\n\nPlease let us know if anything remains unclear. We’d be very glad to provide more clarifications."}, {"review_id": "8BEyfg9Zdf", "reviewer": "Reviewer_bM1C", "summary": "This work studies the problem of computing optimal history-dependent policies under a model of principal-agent style stochastic games. The problem is general-sum and the goal is to find a Stackelberg equilibrium among history-dependent strategies. This work makes a \"hindsight observability\" assumptions, where both players observe the full interaction history, including states, observations and actions at the end of each time step. Under this model, this work shows that it is possible to compute an $\\epsilon$-optimal policy with time complexity scaling polynomially with the problem parameters. The key idea underlying this result is the construct of \"inducible value sets\", enabling the use of a value-based approach through sets that can be estimated with dynamic programming to compute convex polytope approximations of the value sets. This work also presents results on learning in such principal-agent problems, making use of recent advancements in reward-free exploration in RL.", "questions": "* In line 141-142, you say that the *hindsight observability* assumption is necessary, as without it the model subsumes POMDPs. Can you clarify what you mean here? The claim that it is necessary seems to imply that this is the *only* structural condition that can be made on top of what was described to make planning tractable. Is this the case? If not, perhaps this sentence should be clarified in the paper.\n* You mention in the related work section that prior work [14] has shown optimal stationary strategies are inapproximable, leaving opening the tractability of optimal history-dependent policies. Is this work making the \"hindsight observability\" assumption? Wouldn't optimization over history-dependent policies be *harder*? Besides computational issues, a different motivation you discuss is the importance of history-dependence for optimality and capturing complex/interesting behaviors. Can you comment on the relationship between these two aspects?", "limitations": "The authors adequately addressed the limitations and potential negative societal impact of their work", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n* This work identifies conditions under which it is possible to computationally-efficiently compute solutions to principal-agent-style stochastic games with partial information, which are known to be computationally-intractable in general.\n* The importance of history-dependence in such principal-agent problems is well-motivated. The construct of inducible value sets effectively addresses the core challenge of the exponential growth of history-dependent policies.\n* This work addresses both computation and learning, attaining polynomial complexity in both cases\n\n**Weaknesses**\n* The \"hindsight observability\" assumption appears quite restrictive---assuming that the states, observations, and actions are observable to both agents---given the motivations of the model as capturing aspects of imperfect and imbalanced information. However, the authors provide some discussion of this assumption in the main text and the appendix.\n* The centralized learning assumption allows for the use of recent advancements in reward-free exploration in RL, but is perhaps not the best fit for the principal-agent style games in practice, where one would expect the two players to be learning in a decentralized manner with different observable information.\n* ~The paper's discussion of related work contained some confusing phrasing that warrants revision. For example, [3] is described as 'concurrent work' (lines 114-115), despite being published two years ago. Also, I would suggest avoiding the phrase \"while we discovered these techniques independently\" in lines 110-111, which refers to work dating back to at least 2009.~\n**Edit:** The authors have clarified this. Their preprint predates the mentioned works.", "was_revised": true, "final_justification": "I thank the authors for their responses and clarifications, which are helpful. In particular, they have addressed a concern I have about crediting related prior work (edited in review). However, since the main technical concerns have not been fully addressed, I will maintain my current score of a borderline accept, noting that I still lean towards acceptance.", "rebuttal": "Thank you for your very insightful and valuable comments and your positive assessment of our work! \n\n---\n\n**Re: Necessity of hindsight observability**\n\nThanks for this very insightful observation! You are right. The form of hindsight observability we assumed in the paper is not the only structural condition that could make the problem tractable. What we intended to mean here is that _some_ form of hindsight observability (not necessarily the one we used) is necessary due to the general intractability of POMDPs. We will clarify this to avoid confusions.\n\n---\n\n**Re: Prior work [14]**\n\nYes, [14] implicitly assumes hindsight observability. It considered a simpler model, where the principal observes everything about the environment, while the agent is missing part of the state that is modeled as an external parameter sampled based on an internal Markovian state. The external state is effectively hindsight observable in expectation. Our algorithm directly applies to the model of [14] and computes an optimal history-dependent policy. \n\n---\n\n**Re: History-dependence**\n\nWe understand that it may appear counterintuitive that it is hard to optimize over the space of history-dependent strategies—which is a larger space that also contains all stationary strategies. **However, when it comes to computational complexity, what matters is not the size of the feasible space, but rather how complicated its boundary is.** For example, an objective function might be easy to optimize over a convex space, but much harder over a subset of this convex space that is nonconvex. \n\nIn our problem, while stationary stategies may appear to have a simpler form, **they actually impose additional constraints that force us to use the same strategy at the same state**. These additional constraints make the space of stationary strategies less well-shaped and hard to optimize over. \n\n---\n\n**Re: Optimality of history-dependent strategies and complex bahavior they capture**\n\nBesides computational advantage, optimal history-dependent strategies in general also yield higher utilities than optimal stationary strategies. Roughtly speaking, consider for example a repeated version of the prisoner’s dilemma. The following tit-for-tat strategy can sustain mutual cooperation between the two players:\n\n- _Cooperate if the other player cooperated in the previous round; and defect, otherwise._\n\nThe strategy is history-dependent because it depends on what the other player did in previous round. In contrast, no stationary strategy achieves this, as it effectively reduces the problem to a one-shot game, where defection is the dominant strategy for both players.\n\nP.S. We were a bit sketchy in the paper when it comes to these relations because we though they were elementary for the game theory community. However, we fully agree that elaborating on them in more detail would be very beneficial for the clarity of the paper, especially considering a broader audience.\n\n---\n\nPlease let us know if you have any further questions. We would be more than glad to provide additional clarifications."}]

Author rebuttal:

Meta-review: The paper shows that optimal and exactly IC solutions can be computed efficiently in two-player stochastic games with asymmetric information by extending a recent idea of using value polytopes.  The reviewers unanimously appreciate the novelty, importance, and technical depth of the results.  There were a number of questions and concerns, most of which were addressed during extensive author-reviewer discussion.  Altogether we believe the paper would be a valuable addition to the program.  We encourage the authors to further improve the paper based on the constructive comments.
Decision: Accept (poster)