Search

The standard definition of differential privacy (DP) ensures that a mechanism's output distribution on adjacent datasets is indistinguishable. However, real-world implementations of DP can, and often do, reveal information through their runtime distributions, making them susceptible to timing attacks. In this work, we establish a general framework for ensuring differential privacy in the presence of timing side channels. We define a new notion of timing privacy, which captures programs that remain differentially private to an adversary that observes the program's runtime in addition to the output. Our framework enables chaining together component programs that are timing-stable followed by a random delay to obtain DP programs that achieve timing privacy. Importantly, our definitions allow for measuring timing privacy and output privacy using different privacy measures. We illustrate how to instantiate our framework by giving programs for standard DP computations in the RAM and Word RAM models of computation. Furthermore, we show how our framework can be realized in code through a natural extension of the OpenDP Programming Framework.

As interactions between humans and AI become more prevalent, it is critical to have better predictors of human behavior in these interactions. We investigated how changes in the AI's adaptive algorithm impact behavior predictions in two-player continuous games. In our experiments, the AI adapted its actions using a gradient descent algorithm under different adaptation rates while human participants were provided cost feedback. The cost feedback was provided by one of two types of visual displays: (a) cost at the current joint action vector, or (b) cost in a local neighborhood of the current joint action vector. Our results demonstrate that AI adaptation rate can significantly affect human behavior, having the ability to shift the outcome between two game theoretic equilibrium. We observed that slow adaptation rates shift the outcome towards the Nash equilibrium, while fast rates shift the outcome towards the human-led Stackelberg equilibrium. The addition of localized cost information had the effect of shifting outcomes towards Nash, compared to the outcomes from cost information at only the current joint action vector. Future work will investigate other effects that influence the convergence of gradient descent games.

Particle dynamics in Earth's outer radiation belt can be modelled using a diffusion framework, where large-scale electron movements are captured by a diffusion equation across a single adiabatic invariant, $L^{*}$ $``(L)"$. While ensemble models are promoted to represent physical uncertainty, as yet there is no validated method to analyse radiation belt ensembles. Comparisons are complicated by the domain dependent diffusion, since diffusion coefficient $D_{LL}$ is dependent on $L$. We derive two tools to analyse ensemble members: time to monotonicity $t_m$ and mass/energy moment quantities $\mathcal{N}, \mathcal{E}$. We find that the Jacobian ($1/L^2$) is necessary for radiation belt error metrics. Components of $\partial\mathcal{E}/\partial t$ are explicitly calculated to compare the effects of outer and inner boundary conditions, and loss, on the ongoing diffusion. Using $t_m$, $\mathcal{N}$ and $\mathcal{E}$, we find that: (a) different physically motivated choices of outer boundary condition and location result in different final states and different rates of evolution; (b) the gradients of the particle distribution affect evolution more significantly than $D_{LL}$; (c) the enhancement location, and the amount of initial background particles, are both significant factors determining system evolution; (d) loss from pitch-angle scattering is generally dominant; it mitigates but does not remove the influence of both initial conditions and outer boundary settings, which are due to the $L$-dependence of $D_{LL}$. We anticipate this study will promote renewed focus on the distribution gradients, on the location and nature of the outer boundary in radiation belt modelling, and provide a foundation for systematic ensemble modelling.

A pivotal challenge in robotics is achieving fast, safe, and robust dexterous grasping across a diverse range of objects, an important goal within industrial applications. However, existing methods often have very limited speed, dexterity, and generality, along with limited or no hardware safety guarantees. In this work, we introduce DextrAH-G, a depth-based dexterous grasping policy trained entirely in simulation that combines reinforcement learning, geometric fabrics, and teacher-student distillation. We address key challenges in joint arm-hand policy learning, such as high-dimensional observation and action spaces, the sim2real gap, collision avoidance, and hardware constraints. DextrAH-G enables a 23 motor arm-hand robot to safely and continuously grasp and transport a large variety of objects at high speed using multi-modal inputs including depth images, allowing generalization across object geometry. Videos at https://sites.google.com/view/dextrah-g.

In this paper, we study the non-asymptotic sample complexity for the pure exploration problem in contextual bandits and tabular reinforcement learning (RL): identifying an epsilon-optimal policy from a set of policies with high probability. Existing work in bandits has shown that it is possible to identify the best policy by estimating only the difference between the behaviors of individual policies, which can be substantially cheaper than estimating the behavior of each policy directly. However, the best-known complexities in RL fail to take advantage of this and instead estimate the behavior of each policy directly. Does it suffice to estimate only the differences in the behaviors of policies in RL? We answer this question positively for contextual bandits but in the negative for tabular RL, showing a separation between contextual bandits and RL. However, inspired by this, we show that it almost suffices to estimate only the differences in RL: if we can estimate the behavior of a single reference policy, it suffices to only estimate how any other policy deviates from this reference policy. We develop an algorithm which instantiates this principle and obtains, to the best of our knowledge, the tightest known bound on the sample complexity of tabular RL., Comment: 59 pages, 2 Figures

Robotics policies are always subjected to complex, second order dynamics that entangle their actions with resulting states. In reinforcement learning (RL) contexts, policies have the burden of deciphering these complicated interactions over massive amounts of experience and complex reward functions to learn how to accomplish tasks. Moreover, policies typically issue actions directly to controllers like Operational Space Control (OSC) or joint PD control, which induces straightline motion towards these action targets in task or joint space. However, straightline motion in these spaces for the most part do not capture the rich, nonlinear behavior our robots need to exhibit, shifting the burden of discovering these behaviors more completely to the agent. Unlike these simpler controllers, geometric fabrics capture a much richer and desirable set of behaviors via artificial, second order dynamics grounded in nonlinear geometry. These artificial dynamics shift the uncontrolled dynamics of a robot via an appropriate control law to form behavioral dynamics. Behavioral dynamics unlock a new action space and safe, guiding behavior over which RL policies are trained. Behavioral dynamics enable bang-bang-like RL policy actions that are still safe for real robots, simplify reward engineering, and help sequence real-world, high-performance policies. We describe the framework more generally and create a specific instantiation for the problem of dexterous, in-hand reorientation of a cube by a highly actuated robot hand.

In many real-world dynamical systems, obtaining precise models of system uncertainty remains a challenge. It may be difficult to estimate noise distributions or robustness bounds, especially when the distributions/robustness bounds vary with different control inputs in unknown ways. Addressing this challenge, this paper presents a novel iterative method tailored for systems with decision-dependent noise without prior knowledge of the distributions. Our approach finds the open-loop control law that minimizes the worst-case loss, given that the noise induced by this control lies in its $(1 - p)$-confidence set for a predetermined $p$. At each iteration, we use a quantile method inspired by conformal prediction to empirically estimate the confidence set shaped by the preceding control law. These derived confidence sets offer distribution-free guarantees on the system's noise, guiding a robust control formulation that targets worst-case loss minimization. Under specific regularity conditions, our method is shown to converge to a near-optimal open-loop control. While our focus is on open-loop controls, the adaptive, data-driven nature of our approach suggests its potential applicability across diverse scenarios and extensions.

This paper studies ML systems that interactively learn from users across multiple subpopulations with heterogeneous data distributions. The primary objective is to provide specialized services for different user groups while also predicting user preferences. Once the users select a service based on how well the service anticipated their preference, the services subsequently adapt and refine themselves based on the user data they accumulate, resulting in an iterative, alternating minimization process between users and services (learning dynamics). Employing such tailored approaches has two main challenges: (i) Unknown user preferences: Typically, data on user preferences are unavailable without interaction, and uniform data collection across a large and diverse user base can be prohibitively expensive. (ii) Suboptimal Local Solutions: The total loss (sum of loss functions across all users and all services) landscape is not convex even if the individual losses on a single service are convex, making it likely for the learning dynamics to get stuck in local minima. The final outcome of the aforementioned learning dynamics is thus strongly influenced by the initial set of services offered to users, and is not guaranteed to be close to the globally optimal outcome. In this work, we propose a randomized algorithm to adaptively select very few users to collect preference data from, while simultaneously initializing a set of services. We prove that under mild assumptions on the loss functions, the expected total loss achieved by the algorithm right after initialization is within a factor of the globally optimal total loss with complete user preference data, and this factor scales only logarithmically in the number of services. Our theory is complemented by experiments on real as well as semi-synthetic datasets.

In 2001, Rama Cont introduced a now-widely used set of 'stylized facts' to synthesize empirical studies of financial price changes (returns), resulting in 11 statistical properties common to a large set of assets and markets. These properties are viewed as constraints a model should be able to reproduce in order to accurately represent returns in a market. It has not been established whether the characteristics Cont noted in 2001 still hold for modern markets following significant regulatory shifts and technological advances. It is also not clear whether a given time series of financial returns for an asset will express all 11 stylized facts. We test both of these propositions by attempting to replicate each of Cont's 11 stylized facts for intraday returns of the individual stocks in the Dow 30, using the same authoritative data as that used by the U.S. regulator from October 2018 - March 2019. We find conclusive evidence for eight of Cont's original facts and no support for the remaining three. Our study represents the first test of Cont's 11 stylized facts against a consistent set of stocks, therefore providing insight into how these stylized facts should be viewed in the context of modern stock markets., Comment: 31 pages, 32 figures

This paper explores the problem of collision-free motion generation for manipulators by formulating it as a global motion optimization problem. We develop a parallel optimization technique to solve this problem and demonstrate its effectiveness on massively parallel GPUs. We show that combining simple optimization techniques with many parallel seeds leads to solving difficult motion generation problems within 50ms on average, 60x faster than state-of-the-art (SOTA) trajectory optimization methods. We achieve SOTA performance by combining L-BFGS step direction estimation with a novel parallel noisy line search scheme and a particle-based optimization solver. To further aid trajectory optimization, we develop a parallel geometric planner that plans within 20ms and also introduce a collision-free IK solver that can solve over 7000 queries/s. We package our contributions into a state of the art GPU accelerated motion generation library, cuRobo and release it to enrich the robotics community. Additional details are available at https://curobo.org, Comment: revised technical report, 62 pages, Website: https://curobo.org

We study the sample complexity of identifying the pure strategy Nash equilibrium (PSNE) in a two-player zero-sum matrix game with noise. Formally, we are given a stochastic model where any learner can sample an entry $(i,j)$ of the input matrix $A\in[-1,1]^{n\times m}$ and observe $A_{i,j}+\eta$ where $\eta$ is a zero-mean 1-sub-Gaussian noise. The aim of the learner is to identify the PSNE of $A$, whenever it exists, with high probability while taking as few samples as possible. Zhou et al. (2017) presents an instance-dependent sample complexity lower bound that depends only on the entries in the row and column in which the PSNE lies. We design a near-optimal algorithm whose sample complexity matches the lower bound, up to log factors. The problem of identifying the PSNE also generalizes the problem of pure exploration in stochastic multi-armed bandits and dueling bandits, and our result matches the optimal bounds, up to log factors, in both the settings., Comment: 22 pages, 5 figures

We study the query complexity of finding the set of all Nash equilibria $\mathcal X_\star \times \mathcal Y_\star$ in two-player zero-sum matrix games. Fearnley and Savani (2016) showed that for any randomized algorithm, there exists an $n \times n$ input matrix where it needs to query $\Omega(n^2)$ entries in expectation to compute a single Nash equilibrium. On the other hand, Bienstock et al. (1991) showed that there is a special class of matrices for which one can query $O(n)$ entries and compute its set of all Nash equilibria. However, these results do not fully characterize the query complexity of finding the set of all Nash equilibria in two-player zero-sum matrix games. In this work, we characterize the query complexity of finding the set of all Nash equilibria $\mathcal X_\star \times \mathcal Y_\star$ in terms of the number of rows $n$ of the input matrix $A \in \mathbb{R}^{n \times n}$, row support size $k_1 := |\bigcup_{x \in \mathcal X_\star} \text{supp}(x)|$, and column support size $k_2 := |\bigcup_{y \in \mathcal Y_\star} \text{supp}(y)|$. We design a simple yet non-trivial randomized algorithm that, with probability $1 - \delta$, returns the set of all Nash equilibria $\mathcal X_\star \times \mathcal Y_\star$ by querying at most $O(nk^5 \cdot \text{polylog}(n / \delta))$ entries of the input matrix $A \in \mathbb{R}^{n \times n}$, where $k := \max\{k_1, k_2\}$. This upper bound is tight up to a factor of $\text{poly}(k)$, as we show that for any randomized algorithm, there exists an $n \times n$ input matrix with $\min\{k_1, k_2\} = 1$, for which it needs to query $\Omega(nk)$ entries in expectation in order to find the set of all Nash equilibria $\mathcal X_\star \times \mathcal Y_\star$., Comment: Our first version, uploaded on 24th October 2023, contained only the result for a unique Nash equilibrium. We have extended the result to the general case of multiple Nash equilibria

High-contrast imaging has been used to discover and characterize dozens of exoplanets to date. The primary limiting performance factor for these instruments is contrast, the ratio of exoplanet to host star brightness that an instrument can successfully resolve. Contrast is largely determined by wavefront error, consisting of uncorrected atmospheric turbulence and optical aberrations downstream of AO correction. Single-point diamond turning allows for high-precision optics to be manufactured for use in astronomical instrumentation, presenting a cheaper and more versatile alternative to conventional glass polishing. This work presents measurements of wavefront error for diamond-turned aluminum optics in the Slicer Combined with an Array of Lenslets for Exoplanet Spectroscopy (SCALES) instrument, a 2-5 micron coronagraphic integral field spectrograph under construction for Keck Observatory. Wavefront error measurements for these optics are used to simulate SCALES' point spread function using physical optics propagation software poppy, showing that SCALES' contrast performance is not limited by wavefront error from internal instrument optics., Comment: Techniques and Instrumentation for Detection of Exoplanets XI

Most dynamics functions are not well-aligned to task requirements. Controllers, therefore, often invert the dynamics and reshape it into something more useful. The learning community has found that these controllers, such as Operational Space Control (OSC), can offer important inductive biases for training. However, OSC only captures straight line end-effector motion. There's a lot more behavior we could and should be packing into these systems. Earlier work [15][16][19] developed a theory that generalized these ideas and constructed a broad and flexible class of second-order dynamical systems which was simultaneously expressive enough to capture substantial behavior (such as that listed above), and maintained the types of stability properties that make OSC and controllers like it a good foundation for policy design and learning. This paper, motivated by the empirical success of the types of fabrics used in [20], reformulates the theory of fabrics into a form that's more general and easier to apply to policy learning problems. We focus on the stability properties that make fabrics a good foundation for policy synthesis. Fabrics create a fundamentally stable medium within which a policy can operate; they influence the system's behavior without preventing it from achieving tasks within its constraints. When a fabrics is geometric (path consistent) we can interpret the fabric as forming a road network of paths that the system wants to follow at constant speed absent a forcing policy, giving geometric intuition to its role as a prior. The policy operating over the geometric fabric acts to modulate speed and steers the system from one road to the next as it accomplishes its task. We reformulate the theory of fabrics here rigorously and develop theoretical results characterizing system behavior and illuminating how to design these systems, while also emphasizing intuition throughout.

One of the most surprising discoveries made at Jefferson Lab has been the discrepancy in the determinations of the proton's form factor ratio $\mu_p G_E^p/G_M^p$ between unpolarized cross section measurements and the polarization transfer technique. Over two decades later, the discrepancy not only persists but has been confirmed at higher momentum transfers now accessible in the 12-GeV era. The leading hypothesis for the cause of this discrepancy, a non-negligible contribution from hard two-photon exchange, has neither been conclusively proven or disproven. This state of uncertainty not only clouds our knowledge of one-dimensional nucleon structure but also poses a major concern for our field's efforts to map out the three-dimensional nuclear structure. A better understanding of multi-photon exchange over a wide phase space is needed. We propose making comprehensive measurements of two-photon exchange over a wide range in momentum transfer and scattering angle using the CLAS12 detector. Specifically, we will measure the ratio of positron-proton to electron-proton elastic scattering cross sections, using the proposed positron beam upgrade for CEBAF. The experiment will use 2.2, 4.4, and 6.6 GeV lepton beams incident on the standard CLAS12 unpolarized hydrogen target. Data will be collected by the CLAS12 detector in its standard configuration, except for a modified trigger to allow the recording of events with beam leptons scattered into the CLAS12 central detector. The sign of the beam charge, as well as the polarity of the CLAS12 solenoid and toroid, will be reversed several times in order to suppress systematics associated with local detector efficiency and time-dependent detector performance. The proposed high-precision determination of two-photon effects will be..., Comment: Experimental Proposal E12+23-008 submitted to Jefferson Lab PAC 51, 34 pages, 18 figures

We report on the results of the first search for the production of axion-like particles (ALP) via Primakoff production on nuclear targets using the GlueX detector. This search uses an integrated luminosity of 100 pb$^{-1}\cdot$nucleon on a $^{12}$C target, and explores the mass region of 200 < $m_a$ < 450 MeV via the decay $X\rightarrow\gamma\gamma$. This mass range is between the $\pi^0$ and $\eta$ masses, which enables the use of the measured $\eta$ production rate to obtain absolute bounds on the ALP production with reduced sensitivity to experimental luminosity and detection efficiency. We find no evidence for an ALP, consistent with previous searches in the quoted mass range, and present limits on the coupling on the scale of $O$(1 TeV). We further find that the ALP production limit we obtain is hindered by the peaking structure of the non-target-related dominant background in GlueX, which we treat by using data on $^4$He to estimate and subtract these backgrounds. We comment on how this search can be improved in a future higher-statistics dedicated measurement.

We propose a novel framework for analyzing the dynamics of distribution shift in real-world systems that captures the feedback loop between learning algorithms and the distributions on which they are deployed. Prior work largely models feedback-induced distribution shift as adversarial or via an overly simplistic distribution-shift structure. In contrast, we propose a coupled partial differential equation model that captures fine-grained changes in the distribution over time by accounting for complex dynamics that arise due to strategic responses to algorithmic decision-making, non-local endogenous population interactions, and other exogenous sources of distribution shift. We consider two common settings in machine learning: cooperative settings with information asymmetries, and competitive settings where a learner faces strategic users. For both of these settings, when the algorithm retrains via gradient descent, we prove asymptotic convergence of the retraining procedure to a steady-state, both in finite and in infinite dimensions, obtaining explicit rates in terms of the model parameters. To do so we derive new results on the convergence of coupled PDEs that extends what is known on multi-species systems. Empirically, we show that our approach captures well-documented forms of distribution shifts like polarization and disparate impacts that simpler models cannot capture.

This paper considers a variant of zero-sum matrix games where at each timestep the row player chooses row $i$, the column player chooses column $j$, and the row player receives a noisy reward with mean $A_{i,j}$. The objective of the row player is to accumulate as much reward as possible, even against an adversarial column player. If the row player uses the EXP3 strategy, an algorithm known for obtaining $\sqrt{T}$ regret against an arbitrary sequence of rewards, it is immediate that the row player also achieves $\sqrt{T}$ regret relative to the Nash equilibrium in this game setting. However, partly motivated by the fact that the EXP3 strategy is myopic to the structure of the game, O'Donoghue et al. (2021) proposed a UCB-style algorithm that leverages the game structure and demonstrated that this algorithm greatly outperforms EXP3 empirically. While they showed that this UCB-style algorithm achieved $\sqrt{T}$ regret, in this paper we ask if there exists an algorithm that provably achieves $\text{polylog}(T)$ regret against any adversary, analogous to results from stochastic bandits. We propose a novel algorithm that answers this question in the affirmative for the simple $2 \times 2$ setting, providing the first instance-dependent guarantees for games in the regret setting. Our algorithm overcomes two major hurdles: 1) obtaining logarithmic regret even though the Nash equilibrium is estimable only at a $1/\sqrt{T}$ rate, and 2) designing row-player strategies that guarantee that either the adversary provides information about the Nash equilibrium, or the row player incurs negative regret. Moreover, in the full information case we address the general $n \times m$ case where the first hurdle is still relevant. Finally, we show that EXP3 and the UCB-based algorithm necessarily cannot perform better than $\sqrt{T}$., Comment: 68 pages, 2 figures

Measurements of deep inelastic scattering from nuclei have revealed that the partonic structure of bound nucleons differs from that of free nucleons. One hypothesis is that this structure modification primarily occurs in highly virtual nucleons participating in short-range correlations, although distinguishing this from other hypotheses is difficult with inclusive measurements alone. Spectator-tagged deep inelastic scattering, on the other hand, may offer a way to specifically probe the partonic structure of highly-virtual nucleons by detecting the correlated emission of a spectator nucleon. Here, we present a method for calculating a "spectator-tagged" structure function for a nucleus by combining Generalized Contact Formalism's description of short-range correlations with light-cone convolution formalism to determine the impact of nucleon motion on the structure function. We apply this method to calculate predictions for helium-4, and find that differences in the virtuality-dependence of nucleon structure modification can lead to large measurable changes in the tagged structure function. The recent CLAS12 Short-Range Correlations Experiment, which collected electron scattering data on helium-4 and other nuclear targets, may be able to constrain this virtuality-dependence and help test whether correlations are the origin of the modification of bound nucleon structure., Comment: 19 pages, 5 figures

We review the modulation stability of parallel propagating/field aligned Whistler Mode Chorus waves propagating in a warm plasma from a formal perspective with a focus on wave-particle interactions. The modulation instability criteria is characterised by a curvature of the dispersion relation for Whistler mode waves and a condition on the ratio between the group velocity $c_g$ and the electron sound speed $c_{s,e}$. We also demonstrate the in order to investigate the spatiotemporal evolution of the envelope and the formation of packets, one necessarily needs to account for the motion of ions within the system, leading to an ionic influence on the modulation instability threshold determined by the ion fraction of the plasma. Finally, we demonstrate that chirping may be captured when higher order effects are included within the spatiotemporal evolution of the amplitude. This yields not only an explicit expression for the sweep rate but identifies a possible origin for the power band gap that occurs at half the electron gyrofrequency. Numerical validation demonstrates that the interaction between wave packets is a source for the emergence of tones observed within mission data, and such interactions may be a major source of the electron energisation which Whistler-Mode chorus are responsible for.

Leveraging tools from the study of linear fractional transformations and algebraic Riccati equations, a local characterization of consistent conjectural variations equilibrium is given for two player games on continuous action spaces with costs approximated by quadratic functions. A discrete time dynamical system in the space of conjectures is derived, a solution method for computing fixed points of these dynamics (equilibria) is given, local stability properties of the dynamics around the equilibria are characterized, and conditions are given that guarantee a unique stable equilibrium.

Autocurricular training is an important sub-area of multi-agent reinforcement learning~(MARL) that allows multiple agents to learn emergent skills in an unsupervised co-evolving scheme. The robotics community has experimented autocurricular training with physically grounded problems, such as robust control and interactive manipulation tasks. However, the asymmetric nature of these tasks makes the generation of sophisticated policies challenging. Indeed, the asymmetry in the environment may implicitly or explicitly provide an advantage to a subset of agents which could, in turn, lead to a low-quality equilibrium. This paper proposes a novel game-theoretic algorithm, Stackelberg Multi-Agent Deep Deterministic Policy Gradient (ST-MADDPG), which formulates a two-player MARL problem as a Stackelberg game with one player as the `leader' and the other as the `follower' in a hierarchical interaction structure wherein the leader has an advantage. We first demonstrate that the leader's advantage from ST-MADDPG can be used to alleviate the inherent asymmetry in the environment. By exploiting the leader's advantage, ST-MADDPG improves the quality of a co-evolution process and results in more sophisticated and complex strategies that work well even against an unseen strong opponent.

Adaptive machines have the potential to assist or interfere with human behavior in a range of contexts, from cognitive decision-making to physical device assistance. Therefore it is critical to understand how machine learning algorithms can influence human actions, particularly in situations where machine goals are misaligned with those of people. Since humans continually adapt to their environment using a combination of explicit and implicit strategies, when the environment contains an adaptive machine, the human and machine play a game. Game theory is an established framework for modeling interactions between two or more decision-makers that has been applied extensively in economic markets and machine algorithms. However, existing approaches make assumptions about, rather than empirically test, how adaptation by individual humans is affected by interaction with an adaptive machine. Here we tested learning algorithms for machines playing general-sum games with human subjects. Our algorithms enable the machine to select the outcome of the co-adaptive interaction from a constellation of game-theoretic equilibria in action and policy spaces. Importantly, the machine learning algorithms work directly from observations of human actions without solving an inverse problem to estimate the human's utility function as in prior work. Surprisingly, one algorithm can steer the human-machine interaction to the machine's optimum, effectively controlling the human's actions even while the human responds optimally to their perceived cost landscape. Our results show that game theory can be used to predict and design outcomes of co-adaptive interactions between intelligent humans and machines.

We study the sample complexity of identifying an approximate equilibrium for two-player zero-sum $n\times 2$ matrix games. That is, in a sequence of repeated game plays, how many rounds must the two players play before reaching an approximate equilibrium (e.g., Nash)? We derive instance-dependent bounds that define an ordering over game matrices that captures the intuition that the dynamics of some games converge faster than others. Specifically, we consider a stochastic observation model such that when the two players choose actions $i$ and $j$, respectively, they both observe each other's played actions and a stochastic observation $X_{ij}$ such that $\mathbb E[ X_{ij}] = A_{ij}$. To our knowledge, our work is the first case of instance-dependent lower bounds on the number of rounds the players must play before reaching an approximate equilibrium in the sense that the number of rounds depends on the specific properties of the game matrix $A$ as well as the desired accuracy. We also prove a converse statement: there exist player strategies that achieve this lower bound., Comment: 53 pages, Accepted at AISTATS 2023

In this paper, we present an efficient algorithm to solve online Stackelberg games, featuring multiple followers, in a follower-agnostic manner. Unlike previous works, our approach works even when leader has no knowledge about the followers' utility functions or strategy space. Our algorithm introduces a unique gradient estimator, leveraging specially designed strategies to probe followers. In a departure from traditional assumptions of optimal play, we model followers' responses using a convergent adaptation rule, allowing for realistic and dynamic interactions. The leader constructs the gradient estimator solely based on observations of followers' actions. We provide both non-asymptotic convergence rates to stationary points of the leader's objective and demonstrate asymptotic convergence to a \emph{local Stackelberg equilibrium}. To validate the effectiveness of our algorithm, we use this algorithm to solve the problem of incentive design on a large-scale transportation network, showcasing its robustness even when the leader lacks access to followers' demand., Comment: 31 pages