CS Paper Radar

Adaptive Incentive Design in Dynamic Principal-Agent Problem via Kernelized Bandits

Arghya Mallick, Anuj S. Vora, Sergio Grammatico, Peyman Mohajerin Esfahani

cs.MA eess.SY ·submitted 2026-08-18 10:27 UTC · v1

Abstract

We consider the dynamic principal-agent problem under asymmetric information, wherein a principal sequentially designs contracts to incentivize an agent with unknown preferences and hidden actions. A fundamental bottleneck in the existing literature is the assumption of deterministic agent utility, which renders the principal's expected utility discontinuous and forces computationally intractable discretizations of the contract space. In this paper, we address this limitation by introducing a stochastic counterpart into the agent's utility model, capturing the inherent physical and behavioral variations in realistic subsystems. We formally prove that this stochastic formulation restores the continuity of the principal's expected utility. Leveraging this continuous geometric structure, we formulate the interaction as a structured multi-armed bandit problem subject to heteroscedastic noise. We propose a \texttt{Heteroscedastic GP-UCB} algorithm that utilizes a Neural Network (Arcsin) kernel, chosen to capture the non-stationary, sigmoidal geometry of the utility landscape. For an $m$-dimensional compact contract space, we establish a high-probability cumulative regret bound of $O\left(\sqrt{T}(\log T)^{m+1}\right)$. Finally, we demonstrate the practical efficacy of our theoretical framework by formulating the Vehicle-to-Grid (V2G) incentive design problem, proving its equivalence to a dynamic principal-agent problem, and showing superior economic performance for grid aggregators.

Closest papers

Nearest neighbours by meaning across the whole index.

Safety by Design: Realized-Cost Constraints for Contextual Bandits with Continuous Actions

cs.LG ·2026-08-27 ·Spyros Dragazis, Aldo Pacchiano
theory similarity 0.68
Abstract

Contextual bandits are a standard framework for sequential decision-making under uncertainty, with applications in clinical trials, dosage selection, recommendation systems, and autonomous systems. Safety is central in many of these applications, since a single unsafe decision in settings such as dosage selection or autonomous driving can have catastrophic consequences. A common way to model safety in bandit problems is to associate each action with both a reward signal and a cost signal, and to optimize reward subject to constraints on cost. Most existing safety-constrained bandit models enforce safety by requiring the expected cost of each action to remain below a prescribed threshold. However, this may be insufficient in heteroscedastic settings, where the chosen action affects not only the expected reward and cost, but also the variability of the observed outcomes. We study contextual bandits with one-dimensional continuous actions and stage-wise high-probability constraints on the realized cost. We propose High-Probability Constrained UCB, an optimistic-pessimistic algorithm that explores for reward while conservatively estimating the safe action set. For linear reward and cost models, we prove a tight $\tilde{\mathcal{O}}(d\sqrt{T})$ regret bound, and we extend the analysis to general function classes using the eluder dimension. Experiments show that enforcing realized-cost safety substantially reduces violations compared with expected-cost constrained baselines.

0.08

Contextual Non-Convex Bandit Optimization with Two-Point Feedback

cs.LG ·2026-11-13 ·Khaled Eldowa, Pierre Gaillard
similarity 0.68
Abstract

We study a non-stochastic contextual bandit problem with Lipschitz losses. At every round, the learner observes the context then picks two actions, observes the difference between their losses, and incurs their mean. The aim is to minimize the regret against a generic non-parametric comparator class of policies mapping contexts to actions; for example, Lipschitz policies and Hölder-smooth policies. We show how relying on a hierarchical discretization technique allows us to improve upon the regret rates achievable under one-point feedback, and even recover the full-information rate in some cases; notably, for sufficiently smooth policy classes or low-dimensional instances. Additionally, for Lipschitz policies, we present an algorithm whose per-round computational complexity is only logarithmic in the time horizon.

0.13

A Computationally Efficient and Rate-Optimal Algorithm for Adversarial Linear MDPs with (Aggregate) Bandit Feedback

cs.LG ·2026-10-22 ·Haolin Liu, Chen-Yu Wei, Hanbin Zhou
similarity 0.67
Abstract

We study episodic linear Markov decision processes with unknown transitions, adversarial losses, and bandit feedback. The state-of-the-art result for this setting (Liu et al., 2024) either achieves $\sqrt{K}$ regret with a computationally inefficient algorithm or achieves suboptimal $K^{3/4}$ regret, where $K$ is the number of episodes. Our work gives the first $\sqrt{K}$ regret with a polynomial-time algorithm. Our method reduces adversarial linear MDPs to adversarial linear bandits whose action set consists of policies' expected feature vectors. The central challenge is that this action set is unknown and can be estimated only through exploration. We address this challenge by constructing an approximate separation oracle for the action set that either generates executable policies from queried features, or refines an outer approximation of the action set. This approach draws inspiration from the reduction of van Erven et al. (2025) for linear contextual bandits and the oracle-efficient linear bandit algorithm of Ito et al. (2019), but additionally deals with the imprecision of the oracle. The resulting algorithm requires only aggregate loss feedback, and to our knowledge. This is the first polynomial-time algorithm for adversarial MDPs with aggregate feedback beyond the tabular case.

0.06

Coordinating the Unknown Lipschitz Constant in Multiplayer Bandits

cs.LG cs.AI ·2026-08-11 ·Ricardo Parada, Chenzhang Zhao, William Chang
theory similarity 0.67
Abstract

Motivated by decentralized applications, we study cooperative multi-agent bandits in continuous (Lipschitz) action spaces when the Lipschitz constant is unknown. We consider three information structures: (A)~unobserved actions with common rewards, (B)~observed actions with independent rewards, and (C)~unobserved actions with independent rewards. In each case we design and analyze an algorithm that estimates the Lipschitz constant, chooses a discretization of the joint action space, and applies a cooperative bandit method to the induced discrete problem. Players never communicate once learning starts, so the central difficulty is that they must reach the \emph{same} discretization from their own data. We prove regret guarantees showing that common rewards and observable actions each supply this agreement for free, and that in their absence agreement can still be bought, through a dithered quantization of the estimate, at no cost in the leading order of the regret.

0.04

Decentralized Bandit Learning of Markov Perfect Equilibria

cs.LG math.OC ·2026-10-09 ·Felix Höfer, H. Mete Soner
theoryhot direction similarity 0.67
Abstract · 23 pages, 1 figure

We study decentralized bandit learning in discounted infinite-horizon, general-sum Markov games with continuous actions. Agents observe the public state, but only their own realized rewards, and use simultaneous perturbation stochastic approximation to update their actions. Under strong monotonicity of the negative running-reward gradients and sufficiently small time steps, we prove that the fully decentralized procedure converges almost surely to the unique stationary Markov perfect equilibrium. We obtain an $O(n^{-1/2})$ convergence rate and present a natural extension to episodic finite-horizon learning.

0.25

Adaptive Incentive Design for Linear-Quadratic Dynamic Games: No-Regret Social Coordination

eess.SY ·2026-10-09 ·Lantian Zhang, Yibei Li, Georgios Vasileiou, Lihua Xie, Silun Zhang
theoryhot direction similarity 0.67
Abstract · 16 pages

Incentives can align private interests with collective goals, but their design becomes intertwined with learning when agents' preferences are unknown. This paper develops an adaptive incentive-design framework for multi-agent linear-quadratic dynamic games, where a system planner can simultaneously learn agents' private preferences and steer their strategic behavior towards the social optimum. To this end, we first characterize the complete family of affine incentives that implement the social optimum as the unique open-loop Nash equilibrium while ensuring exact budget balance. When agents' preferences are unknown, we develop an online algorithm to estimate their preference parameters and establish strong consistency of the estimates under a weak trajectory-dependent excitation condition, without requiring persistent excitation or i.i.d. trajectories. We then integrate this estimator into an active-learning incentive mechanism that combines certainty-equivalent coordination with decaying random probing. We prove that the probing generates sufficient information through the agents' equilibrium responses and the system dynamics, ensuring consistent preference learning from the resulting closed-loop trajectories. We show that the induced trajectories converge almost surely to their socially optimal counterparts, while cumulative social-cost regret relative to the full-information oracle and cumulative net-budget imbalance grow sublinearly. Simulations of a transboundary pollution game demonstrate the effectiveness of the proposed framework.

0.32

Block Optimism for Nonstationary Bandits with Latent Linear Dynamics

cs.LG stat.ML ·2026-10-01 ·Taehyun Hwang, Hyunjun Choi, Heesang Ann, Min-hwan Oh
top venuebenchmarktheory similarity 0.67
Abstract · Accepted at NeurIPS 2026

We study an endogenous nonstationary stochastic bandit problem with latent linear dynamics, where actions affect both immediate rewards and the future evolution of an unobserved latent state. Rewards are bilinear in the current action and latent state, inducing history-dependent rewards and a nontrivial long-horizon planning problem. The existing explore-then-commit approach achieves $\tilde{O}(T^{2/3})$ regret by uniformly exploring to estimate the latent dynamics and then committing to an optimized open-loop action sequence. We show that this rate can be improved via adaptive block-level optimism. Our key step is a cyclic approximation: under stable dynamics, the infinite-memory reward process can be truncated, and the open-loop benchmark can be approximated by optimizing a finite-memory block-level proxy. Building on this reduction, we propose a UCB-based block algorithm that maintains confidence sets for the truncated dynamics parameters and selects blocks optimistically. We prove a regret bound of order $\tilde{O}(\sqrt T)$, significantly improving over the previous $\tilde{O}(T^{2/3})$ guarantee for the same model. To the best of our knowledge, this is the first $\tilde{O}(\sqrt T)$ regret guarantee for latent linear-dynamics bandits with bilinear reward observations and an open-loop action-sequence benchmark.

0.33

Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary

cs.LG stat.ML ·2026-09-11 ·Mengxiao Zhang
similarity 0.66
Abstract

We study switching regret in adversarial multi-armed bandits, where the learner competes with an arm sequence that changes at most $S$ times. When $S$ is known, an optimal expected regret of $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ is obtainable [Auer et al., 2002]. However, when $S$ is unknown, Marinov and Zimmert [2021] show that this guarantee is impossible under an adaptive adversary. In this paper, we show that a single algorithm achieves $\widetilde{\mathcal{O}}(\sqrt{(S+1)KT})$ expected regret for every $S$ against an oblivious adversary, resolving an open problem of Auer et al. [2019b]. Our algorithm combines a fixed-share learner initialized with a small learning rate and dyadic-interval subroutines that search for local improvements using randomized learning rates and implicit exploration. Importantly, a non-uniform prior favors following the main learner, keeping the cost of maintaining many subroutines small. When the subroutines accumulate sufficient improvement over the main learner, its learning rate doubles, allowing adaptation to the unknown number of comparator switches $S$.

0.17