Work in Progress
Working Papers1
Abstract
We study a general-sum Stackelberg Markov game under a leader–controller assumption, where a leader and a follower aim to learn a Stackelberg equilibrium (SE) with noisy bandit feedback and unknown transitions and without a central coordinator or best-response oracles. We propose the first decentralized online learning algorithm for SE in Markov games, featuring an intuitive combination of a UCB learning scheme for the follower with a policy optimization method for the leader, inspired by Luo et al. 2021 and augmented with online coverage-policy exploration. Notably, we establish theoretical guarantees showing that the proposed algorithm achieves \(\widetilde{\mathcal{O}}(\sqrt{T})\) Stackelberg regret in a learning-to-commit setting, where the leader learns fully online for episodes before committing to a policy that forms an approximate \(\widetilde{\mathcal{O}}(1/\sqrt{T})\)-SE with the follower’s learned best response. An application to dynamic platform price-setting is presented along with numerical experiments demonstrating the robustness of our results.
Abstract
We consider learning Markov Decision Processes (MDPs) with continuous state and action spaces, adversarial losses, bandit feedback, and unknown transitions. We present DIZOOM-PO, a policy optimization algorithm over a dynamically refined partition of the state-action space. It features three key ingredients: an adversarial zoom-in rule that refines the partition based on both cumulative and instantaneous confidences, dilated exploration bonuses adapted to the time-varying action sets, and a buffering mechanism that stabilizes importance-weighting estimators’ bonuses on newly created regions. Together, we achieve \(\widetilde{\mathcal{O}}(K^{(z+1)/(z+2)})\) regret, where \(K\) is the number of episodes and \(z\) is an instance-dependent adversarial zooming dimension satisfying \(z \le d\) (the covering dimension). This improves over uniform discretization whenever \(z < d\), matches the best known rate for stochastic continuous MDPs in the harder adversarial setting, and is tight in \(\text{poly}(K)\) dependencies. We require neither simulators nor exploratory assumptions.
Abstract
In learning problems within politics, finance, or operations, agents’ decisions and predictions can influence the underlying data-generating process—a phenomenon known as the performative effect. We study this effect in decentralized noncooperative games with coupled constraints, where data distributions depend endogenously on players’ actions. In many practical settings, agents may not know the functional form of their objectives and can only observe realized payoffs from played actions. Our main contribution is SPADE (Stochastic Payoff-based Algorithm for Decentralized Equilibria), a low-communication cost distributed algorithm in which each player perturbs its action with Gaussian noise and updates using payoff observations alone. We show that when data are sampled from players’ unperturbed actions, SPADE converges to the performatively-stable equilibrium (PSE). We also present SPADE-NE, in which both data and payoffs are induced by the deployed actions, and prove convergence to the harder Nash equilibrium (NE) under an additional smoothness assumption. Finally, we propose SPADE-MP, a multipoint-feedback approach that retains near full-information guarantees and improves empirical convergence to NE. We support our results through numerical experiments on networked Cournot competition and show significant improvements in reducing communication overhead.
Abstract
Policy optimization methods are a widely used and empirically effective class of reinforcement learning algorithms. In this paper, we use policy optimization to solve the challenging problem of efficient learning in corrupted Markov Decision Processes (MDPs) with both adversarial losses and transitions. In particular, we develop a corruption-robust policy optimization algorithm, CR-UOB-PO, that achieves \(\mathcal{O}(\sqrt{T} + C^{\mathsf P})\) regret in the finite tabular MDP setting under known \(C^{\mathsf P}\), which quantifies the total transition corruption across all episodes. We further demonstrate how CR-UOB-PO can be reduced using a principled black-box approach to maintain the same regret bound without knowledge of \(C^{\mathsf P}\). To our knowledge, this is the first algorithm for corrupted MDPs that relies almost entirely on policy optimization methods, allowing it to handle extreme environments with low computational complexity.
Publications & Accepted Papers
— CS Conference Publications —
Abstract
Agentic systems built on large language models (LLMs) are increasingly deployed in high-stakes settings, but the causal mechanisms by which adversarial agents induce harmful outcomes remain poorly understood. We address this with a single-call counterfactual necessity test for multi-agent LLM systems that asks: which specific agent communication was causally responsible for the harmful outcome? In contrast with actual-causality frameworks that reason over set-valued causes, we use one attribution rule throughout: single-call necessity for a selected proximate call. The key technical contribution is the Gumbel-Max tape, which lifts the per-token Gumbel-Max counterfactual generator from a single LLM to a multi-agent conversation. Per-token GPU random number generator (RNG) states are recorded during a factual run on a tape shared across all agents, then replayed during counterfactual (CF) runs everywhere except at the intervened call. Applied to the BAD-ACTS benchmark across 148 adversarial scenarios spanning four multi-agent environments and two prompting conditions (non-safe and safe), the test shows that single-call necessity tracks communication structure: decentralized and hierarchical environments (Travel Planning, Financial Article Writing) exhibit meaningful aggregate causal effect (ACE), while sequential debate (Multi-Agent Debate) shows near-zero ACE despite comparable attack success rate. A replay sanity check confirms that all CF effects under identity intervention are exactly zero, validating the tape mechanism. The results identify where targeted defenses are likely to be effective in deployed agentic systems.
Abstract
Many real-world reinforcement learning (RL) problems evolve in continuous time, where decisions occur at irregular, event-driven intervals rather than at fixed discrete steps. We study episodic continuous-time Markov Decision Processes (MDPs) in which decision epochs are governed by a homogeneous Poisson process and the reward and transition dynamics vary smoothly over time. We consider both a fixed number of jumps per episode and a fixed time budget with a random number of Poisson decision epochs. Under a Lipschitz continuity assumption in time, we exploit local smoothness through discretization and extend both UCRL and Q-learning to this setting, proving \(\widetilde{\mathcal{O}}(T^{2/3})\) regret bounds for both model-based and model-free algorithms. Finally, we establish matching \(\widetilde{\Omega}(T^{2/3})\) minimax lower bounds, showing that the rate is optimal up to logarithmic factors. These results provide the first tight regret guarantees for Lipschitz-smooth continuous-time episodic MDPs with Poisson decision epochs.
Resting
Abstract
In this brief, we examine how UI benefit generosity has evolved. Our central measure is the maximum weekly benefit amount (WBA) – the cap on weekly payments that each state sets under its UI system. We first describe the two methods states use to update their maximum WBAs: automatic indexing to wage growth, and discretionary legislative adjustment. We then compare changes in the maximum WBA across states to changes in inflation, housing costs, and earnings thresholds to assess how adequately benefit levels support unemployed workers. Finally, we discuss which approach to updating the maximum WBA most effectively maintains benefit adequacy over time.
Abstract
We formulate a decentralized, cooperative multi-agent bandit framework, applied to the stochastic partial-monitoring cascading bandit problem. The reward in each round depends on the joint-ranking” cascade” collectively taken by all learning agents. The objective is shared, but to make the coordination problem more challenging, we contend with three variants of information asymmetry: action asymmetry, where the overall joint-ranking is unobservable to all agents but the feedback received is common; reward asymmetry, where the overall ranking is observable, but feedback received by each agent is i.i.d.; and that with both action and reward asymmetry. For the first setting, we propose mCascadeUCB, and for the second setting, we propose mCascadeUCB-Intervals, with both algorithms achieving \(O\log{T}\) gap-dependent regret within their respective settings. For the last setting, we propose mCascadeDSEE, which achieves close to \(O\log{T}\) gap-independent regret. We demonstrate our algorithms with experimental results.
Footnotes
Working-paper rights.
Unless a manuscript states otherwise, working papers and works in progress are copyright their named authors and other applicable rights holders, with all rights reserved.
You may download and print one copy for personal scholarly use. Redistribution, modification, or commercial use requires prior written permission from all applicable rights holders. Citation, quotation, and other uses permitted by law remain unaffected.
Published versions are governed by their publisher or venue terms.
Full notice↩︎