Stochastic Principal-Agent Problems: Computing and Learning Optimal History-Dependent Policies

Thank you for your very insightful and valuable comments and your positive assessment of our work!

Re: Necessity of hindsight observability

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

Re: Prior work [14]

Yes, [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.

Re: History-dependence

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

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

Re: Optimality of history-dependent strategies and complex bahavior they capture

Besides 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:

• Cooperate if the other player cooperated in the previous round; and defect, otherwise.

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

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

Please let us know if you have any further questions. We would be more than glad to provide additional clarifications.

Thank you so much for your very thoughtful follow-up comments! We greatly appreciate them. We just have a couple of additional points which we hope you could kindly consider.

We describe the work of Bernasconi et al. as concurrent because our preprint version predates both their preprint and their published version. This timeline is supported by publicly archived records. We'd be happy to clarify this point further in the final version of our paper and include relevant context that is currently omitted due to anonymity requirements.

We also realized that we overlooked another point you raised in the Strengths and Weaknesses section, so we add our response below. (We didn't mean to ignore it—we were just a bit overwhelmed as we had five reviews to address for this submission.)

Re: centralized learning: Centralized learning can be viewed as a mechanism the principal commits to. Indeed, our mechanism ensures incentive compatibility in the sense that the agent's regret is sublinear. So, in this regard, the agent's behavior is incentivized rather than forced. This centralized learning paradigm aligns with other principal-agent-style mechinam design problems, which also involve some level of centralisms as the principal functions similarly to a central planner.

Completely decoupling the two learners is an interesting direction. However, this is very challenging as our goal is effectively to find a Stackelberg equilibrium, which involves an optimization problem for the principal. This differs from the known convergence result of some decoupled learning dynamics to (coarse) correlated equilibria, as our goal is akin to reaching not only just an arbitrary equilibrium but also an optimal one. To the best of our knowledge, even in the much simpler setting of repeated normal-form Stackelberg games, there is currently no elegant approach in the literature to steer a completely independent learning agent into a Stackelberg equilibrium. For this reason, we were unable to pursue this line of work further in the present paper.

Please let us know if you have any further questions!

Thank you for your very insightful and valuable comments and your positive assessment of our work!

Before we address your individual comments/questions below, we’d like to first highlight the following main points:

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

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

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

Regarding your specific questions:

1. Hindsight observability is inevitable due to intrinsic computational complexity barriers

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

2. Scaling to multiple followers is NP-hard even in one-shot settings (as implied by [Papadimitriou & Roughgarden, 2008])

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

3. Settings where only part of the interaction log is revealed

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

4. Re: Experiments

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

Reference:

• Christos H Papadimitriou and Tim Roughgarden. Computing equilibria in multi-player games. SODA ‘05.

Please let us know if you have any further questions. We would be more than glad to provide additional clarifications.

Thanks a lot for your very insightful comments and questions; they are greatly appreciated! Below are our answers to the your questions.

Re: Why POMDP instead of MDP?

We consider POMDP because it captures information asymetry between different players, while a standard MDP is insuffient for this purpose.

Re: Why history-dependence?

We 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):

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

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

Re: How did we address the challenges of handling history-dependent strategies

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

Re: Definition of $\epsilon$-optimal IC policy

An $\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).

Reference:

• Jiarui Gan, Rupak Majumdar, Goran Radanovic, and Adish Singla. Bayesian persuasion in sequential decision-making. AAAI ‘22.

We 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!

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.

Re: Difference with Gan et al., and Bernasconi et al. (as well as Zhang et al.)

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

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

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:

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

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

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

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

Re: Technical obstables

Following our responses above, the main technical obstables we overcome in this paper are the following:

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

2. A novel slice-based discretization approach to ensure exact IC (which is missing in the work of Bernasconi et al.).

3. Application of reward-free exploration to the learning version of the problem to achieve efficient learning.

Re: Intuition of Point 3, Figure 1

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

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

P.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]).

Reference:

• Christos H Papadimitriou and Tim Roughgarden. Computing equilibria in multi-player games. SODA ‘05.

Please let us know if you have any further questions. We would be more than glad to provide additional clarifications.

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.

Our answers to your other questions are as follows. If anything remains unclear, we would be more than glad to provide further clarifications.

First, regarding your questions in the Strengths and Weaknesses section:

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

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

Next, regarding your questions in the Questions section:

Re: Q1

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

Re: Q2

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

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

Re: Q3

In 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:

• First, assign the value of $\bar{\pi} ( \cdot | \tilde{\omega}^P, \omega^A)$ to $\pi( \cdot | \sigma; \tilde{\omega}^P, \omega^A)$;

• Then, return $\pi( \cdot | \sigma; \tilde{\omega}^P, \omega^A)$.

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

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

Re: Q4

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

Re: Q5

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

Re: Q6

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

Re: Q7

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

Re: Q8

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

Please let us know if anything remains unclear. We’d be very glad to provide more clarifications.