At a glance
A strategy optimal when a follower knows its distribution can perform poorly while that distribution is being learned. The paper bounds this inferability gap using estimation error, response sensitivity, randomness, and distance from a decision boundary. Lower-randomness policies can improve transient returns while sacrificing their full-information optimum. The conclusion is conditional on the game and follower model: estimation errors can also benefit the leader, and deterministic behavior is not universally optimal.
I Introduction
The leader commits in advance to a fixed policy; the follower adapts to observed past actions. This differs from ordinary Stackelberg commitment, where the follower knows the distribution but still does not see the current sampled action. It also differs from an online learner that changes the leader policy after every observation.
Building on the conference version, the study analyzes several response models and identifies a tradeoff between full-information payoff and statistical inferability. It targets repeated statistical learning, whereas legible-motion planning commonly conveys intent within one trajectory. The bounds motivate a variance penalty; simulations and a twenty-four-participant study evaluate its finite-interaction implications.
II Notation and Preliminaries on Stackelberg Games
The notation distinguishes policy parameters, sampled actions, and random empirical estimates. Stochasticity ν is the square root of the trace of the categorical covariance, not the trace itself. A second quantity φ measures concentration and increases as a distribution approaches a point mass. L2 distance and Lipschitz continuity connect estimation errors to changes in actions and payoff. Follower optima are assumed unique unless a specified worst-case tie convention is used; finite-temperature entropy regularization gives uniqueness directly.
II-A Dynamic Stackelberg Games with Parametric Mixed Strategies
Each player uses a stationary parameterized action distribution at the current state, and the joint actions determine rewards and the next state. An episode ends on reaching an absorbing, reward-free set. Expected cumulative rewards include the initial step, and the hitting time can depend on both policies. The fully informed follower optimizes its expected episode return given the leader parameter. A static game is the one-step special case; the general setup permits continuous actions and parameter spaces.
Equations
| s.t. |
II-B Special Case: Static Bimatrix Stackelberg Games
The static discrete specialization has m leader actions, n follower actions, and separate payoff matrices A and B. Expected payoffs are bilinear in the two action distributions. The follower observes the leader’s distribution in the full-information comparison, but never its simultaneous realized action. Subsequent response assumptions change the follower solution and therefore the meaning of the full-information benchmark.
II-B 1 Fully Rational Followers
A fully rational follower selects a payoff-maximizing action distribution. The leader then chooses a commitment anticipating that response. Best responses can jump at indifference boundaries, and the leader’s optimum may be only a supremum. This discontinuity prevents direct application of the later Lipschitz-response bound.
Equations
| s.t. |
II-B 2 Boundedly Rational Followers with Maximum Entropy Response
The follower maximizes expected reward plus entropy divided by rationality parameter λ. Its unique response is softmax of the follower action values, as characterized in the cited softmax analysis. Small λ makes the response nearly uniform and insensitive to observations; large λ approaches a discontinuous fully rational response. This is a behavioral model, not a fitted universal account of human decision-making.
Equations
II-B 3 Boundedly Rational Followers with Maximum Likelihood Classificatrion
A classifying follower maps the observed distribution to one of finitely many predefined leader types by maximum likelihood, then best responds to that type. The leader anticipates both classification and response. Even full information about the actual distribution does not remove the imposed type approximation. The later analysis needs a unique selected type and positive separation from classification boundaries.
Equations
| s.t. |
III Problem Formulation: Repeated Stackelberg Games With Inference
The inferability gap compares one fixed policy’s full-information return with its expected return at interaction k when the follower uses past samples. The gap is signed: the definition does not rule out higher returns under inference. Optimizing the leader policy changes both actual payoffs and the distribution of the follower’s future estimates. Table I maps the distinct assumptions to the corresponding results.
| Achievability Results (Upper bounds on ) | ||||
| Problem section | Result section | Horizon | Strategy class | Follower type |
| III-A | IV-A | Static | Parametric | Rational |
| III-B1 | IV-C | Static | Discrete | Rational |
| III-B2 | IV-B | Static | Discrete | Max. Ent. |
| III-B3 | IV-D | Static | Discrete | Classifying |
| III-C | IV-E | Dynamic | Discrete | Myopic Max. Ent. |
| Converse Result (Lower bound on ) | ||||
| Problem section | Result section | Horizon | Strategy class | Follower type |
| III-B1 | IV-F | Static | Discrete | Rational |
| Achievability Result (Upper bound on ) | ||||
| Setting section | Result section | Horizon | Strategy class | Follower type |
| II-B1 | IV-G | Static | Discrete | Rational |
III-A Repeated Static Parametric Stackelberg Games with Inference Against Fully Rational Followers
Before play, the leader chooses one parameter for all K repetitions. Actions are independent samples from that fixed policy, and the follower estimates its parameter from the previous k−1 observations before responding. The leader maximizes expected cumulative reward over the resulting random estimates and responses. Its choice is made before those samples exist; this is not an adaptive signaling or policy-update algorithm.
Equation
III-B Repeated Static Bimatrix Stackelberg Games with Inference Against Fully or Boundedly Rational Followers
For discrete actions, the follower uses empirical action frequencies. The current response therefore changes with the observation history even though the true leader distribution stays fixed. Three variants use the empirical distribution directly, pass it through softmax, or first classify it into a prototype type.
Equation
III-B 1 Fully rational follower
The fully rational empirical follower best responds to observed action frequencies. The leader’s objective averages the cumulative payoff over all possible sample histories. Histories that cross a best-response boundary can cause abrupt changes in payoff.
Equation
III-B 2 Boundedly rational follower with maximum entropy response
The entropy-regularized empirical follower softmaxes the action values computed from observed frequencies. The leader optimizes expected cumulative payoff against these varying, smooth responses. Finite λ enables the direct error-to-payoff bound developed in Section IV-B.
Equation
III-B 3 Boundedly rational follower with maximum likelihood classification
The classifying follower chooses a maximum-likelihood type from empirical frequencies and best responds to that type. The leader anticipates classification errors across histories. A finite set of types makes the response piecewise constant when each type has a unique best response.
Equation
III-C Repeated Discrete Dynamic Parametric Stackelberg Games with Inference Against Boundedly Rational, Myopic Followers
In the discrete dynamic setting, the follower pools observed leader actions separately at each state across previous episodes. It then uses a myopic softmax response that optimizes immediate reward at each state. The leader still evaluates the full episode return. The dynamic theorem therefore does not establish a guarantee for a follower that strategically optimizes a multistep return.
Equation
III-D An Example Where Inferable Behavior is Necessary: Autonomous Car and Pedestrian Interaction
The car–pedestrian example uses stopping probability p. Under the stated payoff table, a fully informed pedestrian waits when p exceeds one half; the car then earns 2(1−p), approaching one near the boundary. Below one half, crossing gives the car −8(1−p). A nearly boundary-optimal policy can instead earn about −1.5 at the second interaction because a single observation often suggests the wrong side. Always stopping is inferred immediately but earns zero. The final type-classification paragraph reverses the two pedestrian actions relative to Table II; the notes use the table’s payoff logic.
| Pedestrian’s actions | |||
|---|---|---|---|
| Wait | Cross | ||
| Car’s actions | Stop | (0,2) | (0,1) |
| Proceed | (2,0) | (-8,1) | |
IV Performance Bounds Under Inference
The analysis excludes the first, observation-free interaction and compares the same fixed policy over interactions two through K. Static bimatrix payoff ranges are normalized for the bounds. Smooth-response or positive-margin conditions give per-interaction bounds scaling as 1/√(k−1), with cumulative bounds of order √K when other factors are fixed. Lower stochasticity shrinks a bound; it does not by itself establish that the policy’s actual payoff is maximal. The dynamic result additionally needs contraction and state coverage.
IV-A Achievability Bound for Repeated Parametric Static Stackelberg Games Against Fully Rational Followers
Theorem 1 assumes a bound on the estimator’s mean squared error, a leader payoff Lipschitz in the follower parameter, and a follower best-response map Lipschitz in the estimated leader parameter. Multiplying the two sensitivity constants bounds loss by parameter error; Jensen’s inequality converts expected error to the square root of MSE. Summing these terms gives the cumulative result. Rates in the interaction count require a separate estimator bound; continuity alone does not supply the finite-sample guarantee.
Equations 1a–2
| (1a) | ||||
| (1b) | ||||
| (1c) | ||||
| (1d) | ||||
| (2) |
IV-B Achievability Bound for Repeated Bimatrix Stackelberg Games Against Boundedly Rational Followers with Maximum Entropy Response
For independent categorical actions, the empirical estimator has MSE ν(x)²/(k−1). After payoff normalization, the leader payoff has sensitivity √n/2 and the softmax response has sensitivity λ√(mn)/2. Corollary 1 therefore sums λn√m ν(x)/(4√(k−1)). The result scales with action-space dimensions and rationality as well as randomness. Deterministic policies have zero static estimation error after one sample; uniform-response followers at λ=0 ignore estimation altogether. Exact evaluation is expensive because the number of possible empirical frequency vectors grows combinatorially.
Equations 3
| (3) |
IV-C Achievability Bound for Repeated Bimatrix Stackelberg Games against Fully Rational Followers
A fully rational follower is constant within each best-response region. If the true policy lies a positive distance d(x) from another response region, a changed response requires estimation error at least that large. Markov and Jensen inequalities yield the stated ν(x)/(d(x)√(k−1)) bound. A sharper empirical-distribution tail bound from Weissman and colleagues decays exponentially for a fixed positive margin; its cumulative sum is bounded independently of K.
The margin assumption is essential near indifference. Source notation mistakenly uses the leader matrix A where follower regions require B, and an introductory probability line has its inequality direction reversed. The subsequent argument uses the probability of leaving the region. Original displays remain intact; the summary states that argument rather than repeating the erroneous probability equality.
Equations
IV-D Achievability Bound for Repeated Bimatrix Stackelberg Games Against Classifying Boundedly Rational Followers
Maximum-likelihood type comparisons are linear in empirical frequencies after taking logarithms. Their decision regions therefore have hyperplane boundaries. With a unique type and positive distance to another region, the same boundary-crossing argument applies using the classification margin. This is a statement about the assumed finite type set and response rule, not a general guarantee for an arbitrary learned classifier.
Equations
IV-E Achievability Bound for a Repeated Discrete Dynamic Stackelberg Games Against Myopic Boundedly Rational Followers with Maximum Entropy Response
The dynamic argument combines concentration with a simulation bound for a fixed leader and a myopic follower. Every step must terminate with probability at least 1−γ. Uniform lower bounds on reaching and revisiting every nonterminal state must hold under every follower policy. Dependent samples and random stopping times are handled using the cited offline-evaluation analysis; a union bound then controls all states. The stated sample requirement is roughly inverse-square in target error, with logarithmic factors and explicit dependence on state coverage. Deterministic statewise policies still need relevant states to be observed.
Scope of the stated bound. Theorem 3 inherits a simulation term γ/(1−γ)² from Lemma 4. Its short appendix sketch does not separately account for changes in immediate expected reward when the follower policy changes, although the general reward depends on both actions. That immediate-reward dependence matters in interpreting the dynamic extension. The original assumptions, lemma, theorem, and formulas are retained; these notes do not turn them into an unconditional guarantee for arbitrary dynamic games.
Equations
IV-F Converse Bound for Repeated Static Bimatrix Stackelberg Games with Fully Rational Followers
A two-action example places near-optimal commitments close to a follower decision boundary. The proof compares two nearby Bernoulli policies, bounds the distinguishability of their sample histories by relative entropy, then applies data processing and Pinsker’s inequality. For sufficiently small ε, its displayed interaction threshold is of order ε⁻²: near-optimal full-information commitments can still lose at least ε before enough evidence accumulates.
This is a near-boundary family whose margin changes with ε. It does not contradict exponential convergence for a fixed policy with fixed positive margin. The source proof has visible notation slips in the region definition, region membership, action index, and its coordinate-versus-L2 distance description. The exact displayed threshold and derivation are preserved for inspection; the rate should be read with those conditions and notation issues in mind.
Equations 4–8
| (5) |
| (6) |
| (7a) | ||||
| (8) |
IV-G Static Bimatrix Games with Limited Inferability Gaps
Decompose the payoffs into a shared component (A+B)/2 and a competing component (A−B)/2. Let αᶜ and αᶻ be their ranges. Proposition 2 compares the best achievable inference return with the best full-information return, unlike the earlier same-policy gap. It gives a loss bound of 2αᶜ using a minimax policy against the follower’s payoff. With a unique maximal follower-payoff entry and an unbiased estimator, it also gives 2αᶻ using the corresponding deterministic leader action.
Nearly zero-sum games can tolerate inference errors through the minimax commitment, while nearly common-interest games admit an easily inferred deterministic near-optimum. Thus inferability is particularly consequential in intermediate general-sum settings. The result is existential and does not say every policy in those game classes has a small inferability gap.
Equations
V Numerical Examples
The numerical examples compare cumulative average returns, excluding the first interaction in the theoretical sums. They include the two-action car game, a continuous-action Gaussian game, and random correlated-payoff matrices. Monte Carlo averages approximate expectations; the figures retain all plotted full-information baselines and transient trajectories.
V-A Car-Pedestrian Interactions
Ten thousand simulations compare fixed stopping probabilities over one hundred interactions. The full-information optimum is approximately p=0.77 for λ=5 and p=0.53 for λ=100. With the more sensitive λ=100 response, the latter remains worse than more conservative policies within the plotted horizon. At λ=5 the gap is smaller. A prose sentence incorrectly calls p=0.9 the full-information optimum; the preceding specification and plot use 0.77. Improved transient return is a finite-horizon tradeoff, not a change to the asymptotic optimum.
V-B General-sum Tug of War
Each player samples a Gaussian action. Their preferred sum intervals lie on opposite sides of zero, while both dislike extreme or inconclusive outcomes. The follower’s best response cancels the leader mean and adds no variance, leaving the leader’s full-information reward dependent only on its standard deviation. A finite positive variance is optimal, demonstrating why complete determinism need not be desirable. Estimating the mean from k samples adds variance (sˡ)²/k to the next action sum; the combined variance is (sˡ)²(1+1/k). Smaller standard deviations can therefore improve early returns. The source’s Gaussian-distribution expressions have misplaced parentheses; the summary states the variance calculation implied by independent sampling.
V-C Randomly Generated Bimatrix Games
The experiment draws ten thousand 4×4 games with independent uniform entries for A and C, and B=(A+C)/2. Each policy is evaluated over one hundred interactions and one hundred Monte Carlo repetitions at λ=100. The optimizer maximizes full-information payoff minus cν² for c in {0,1,10,100}, initialized from a fully rational Stackelberg solution found through linear programs. It seeks a local optimum of a nonconvex objective.
Squaring ν gives a smoother penalty than the theorem’s linear ν term, so this is a motivated surrogate rather than direct optimization of the identical bound. In the reported average, c=100 produces deterministic commitments that perform best early; unregularized commitments overtake around forty-five interactions. These particular correlated games and local solutions do not establish a universal regularization weight.
Equations
VI Human Subject Study for the Autonomous Car Example
The human study tests whether the qualitative transient tradeoff appears when people drive in simulation. It uses the same payoff structure but replaces the pedestrian with a human-driven car. This is a behavioral experiment with virtual rewards, not a road deployment or a physical collision-safety evaluation.
VI-A Experiment Scenario
Participants drive toward a T-intersection with a wheel and pedals in the CARLA simulator. A second, automated car approaches on the through road. The automated car either yields or proceeds; if both proceed, it makes an emergency stop. Figure 4 preserves the participant’s view of the environment.
VI-B Objectives and Rewards
The task rewards a timely left turn and discourages failing to yield. The automated car receives zero for stopping, two for proceeding when the human stops, and minus eight for an emergency stop. Human rewards are two for a timely turn with a stop, one without the stop, and zero for missing the time limit. Table III is the authoritative payoff specification: the prose’s later claims of a near-optimal return of 0.5 and a successful-proceed return of one conflict with its values, which imply approximately one and two respectively.
| Human’s actions | |||
|---|---|---|---|
| Stop | Proceed | ||
| Autonomous car’s actions | Stop | (0,2) | (0,1) |
| Proceed | (2,0) | (-8,1) | |
VI-C Experiment Setting and Independent Variables
Twenty-four participants aged nineteen to thirty-one each encountered two randomly assigned automated-car types, with fifteen repetitions per type after controller practice. The six stopping probabilities were 0.1, 0.25, 0.4, 0.6, 0.75, and 0.9; the plotted type groups contain eight, seven, seven, nine, nine, and seven participants. These are forty-eight participant–type exposures, not forty-eight independent people. Each interaction lasted under forty-five seconds, with independent automated decisions and outcome/reward feedback. The authors provide an example interaction recording.
VI-D Dependent Variables
Before every interaction, including the first, participants estimated the probability of an automated courtesy stop from zero to one hundred percent and rated confidence on a five-level scale. Logged outcomes include courtesy and emergency stops, human stops, and timely turn completion. Confidence and probability judgments are distinct measures; the analysis also constructs a hypothetical sample-mean best-response comparator.
VI-E Results and Discussion
Probability estimates generally approach the assigned type, with substantial individual variability and initial anchoring near one half. More extreme probabilities are inferred more quickly. Two participants’ high estimates remain outliers in the p=0.1 group. Final mean confidence levels range from 3.71 to 4.28 out of five; confidence alone does not establish calibration.
The p=0.6 automated policy has a strong full-information payoff but negative empirical mean return and is outperformed by p=0.75 and p=0.9 during the study. For p below one half, human behavior instead improves the leader’s return relative to full-information best responses, illustrating that the inferability gap can be negative. The authors attribute some improvement to a human bias toward stopping. Figures 5 and 6 retain every individual trajectory, group mean, sample-mean comparator, and full-information baseline. The short, uneven groups and descriptive curves support a qualitative finite-horizon observation; no inferential significance test or general human response-model validation is reported.
VII Conclusions
A fixed randomized commitment can trade an asymptotically high payoff for difficult short-term inference. The practical implication is to consider how quickly other agents can identify the policy, together with their response sensitivity and the available interaction horizon. Assumptions about independent static samples, unique responses or margins, dynamic coverage, and the chosen behavioral model delimit the results. Simulations and a small simulated-driving study illustrate the tradeoff without establishing universal benefits from determinism or validating the full dynamic theory experimentally.
Appendix: Proofs of the Technical Results
The appendix derives the empirical-frequency MSE from binomial coordinate variances. For the softmax sensitivity bound, subtracting a common payoff midpoint leaves softmax unchanged, after which its Lipschitz constant and Cauchy–Schwarz give the dimension factor. An analogous midpoint argument bounds leader-payoff sensitivity. The remaining three lemmas have brief proof sketches citing contraction, dependent-sample concentration, and reach/revisit counts.
Original proof displays are preserved, including the omitted λ factor in the last line of Equation 9, the midpoint superscript inconsistency in the Lemma 2 prose, and the sketch’s description of two as an upper bound on φ despite its earlier lower-bound definition. The summary uses the stated lemmas’ constants and explicitly retains the limited detail of the dynamic proof.
Equations 9a–10c
| (9a) | ||||
| (9b) | ||||
| (9c) | ||||
| (9d) | ||||
| (10a) | ||||
| (10b) | ||||
| (10c) | ||||
Acknowledgement
The work acknowledges National Science Foundation support and discussions with Tichakorn Wongpiromsarn, plus Neel Bhatt’s help with the human-study simulator. Grant identifiers and original author material remain with the source.
References
The complete bibliography and the five original author portraits and biographies are retained. Citations in the edited discussion open the corresponding reference entries.
![]() |
Mustafa O. Karabag is a postdoctoral fellow in the Oden Institute for Computational Engineering & Sciences at the University of Texas at Austin. He received his Ph.D. degree from the University of Texas at Austin in 2023. His research focuses on developing theory and algorithms to control the information flow of autonomous systems to succeed in information-scarce or adversarial environments. |
![]() |
Sophia Smith received her B.S. in mathematics and her B.A. in Physics at the University of Chicago, Chicago IL, USA in 2021. She is currently working towards the Ph.D. degree in Computational Science Engineering in Math within the Oden Institute at the University of Texas at Austin, Austin, TX, USA. Her research interests include developing theory and algorithms for decomposing teams of autonomous agents. |
![]() |
Negar Mehr is an assistant professor in the Department of Mechanical Engineering at the University of California, Berkeley. Before that, she was an assistant professor of Aerospace Engineering at the University of Illinois Urbana-Champaign. She was a postdoctoral scholar at Stanford Aeronautics and Astronautics department from 2019 to 2020. She received her Ph.D. in Mechanical Engineering from UC Berkeley in 2019 and her B.Sc. in Mechanical Engineering from Sharif University of Technology, Tehran, Iran, in 2013. The focus of her research is to develop control algorithms that allow autonomous systems to safely and intelligently interact with each other and with humans. She draws from the fields of control theory, robotics, game theory, and machine learning. She is a recipient of the NSF CAREER Award. She was awarded the IEEE Intelligent Transportation Systems best Ph.D. dissertation award in 2020. |
![]() |
David Fridovich-Keil received the B.S.E. degree in electrical engineering from Princeton University, and the Ph.D. Degree from the University of California, Berkeley. He is an Assistant Professor in the Department of Aerospace Engineering and Engineering Mechanics at the University of Texas at Austin. Fridovich-Keil is the recipient of an NSF Graduate Research Fellowship and an NSF CAREER Award. |
![]() |
Ufuk Topcu received the Ph.D. degree from the University of California at Berkeley, Berkeley, CA, USA, in 2008. He joined the Department of Aerospace Engineering, University of Texas at Austin, Austin, TX, USA, in Fall 2015. He held research positions with the University of Pennsylvania, Philadelphia, PA, USA, and California Institute of Technology, Pasadena, CA, USA. His research focuses on the theoretical, algorithmic and computational aspects of design and verification of autonomous systems through novel connections between formal methods, learning theory, and controls. |
![[Uncaptioned image]](https://storage.literature.yihao.one/media/sha256/41/41b19c210d6237f05fec05a4506923e2e662288fcd575a79501b4469aafa81b6.jpg)
![[Uncaptioned image]](https://storage.literature.yihao.one/media/sha256/f2/f28d18ce0176f5c0720532b4a5ebdd70d2c66bdda93d45a19beba69647e6111e.jpg)
![[Uncaptioned image]](https://storage.literature.yihao.one/media/sha256/5d/5d6660a14a3fcfb1c5c4c647ef7073488b7820f45673bb549c006f234246fa1d.jpg)
![[Uncaptioned image]](https://storage.literature.yihao.one/media/sha256/bb/bbc70353bbb774538f494baaac6cc153200905a58bfc64fb9a426677d8e441dc.jpg)
![[Uncaptioned image]](https://storage.literature.yihao.one/media/sha256/7b/7b12d7878721f5a420480781e419dd68f82be48fefb5876b21bb90a976a0d61f.jpg)