Mengxiao Zhang

Multi-echelon stochastic inventory models with known demand distributions have long underpinned supply chain coordination, yielding first-best policies in centralized systems and contract mechanisms that induce decentralized agents to implement these policies. We revisit the classic two-echelon inventory model in an online learning setting with unknown demand, which necessitates rethinking both inventory control and coordination strategies. This setting poses three key challenges: (i) the overall loss function may be non-convex, limiting the applicability of standard online convex optimization methods; (ii) the multi-echelon structure creates information asymmetry, as the upstream agent observes only order quantities—potentially distorted by downstream learning—rather than true consumer demand; and (iii) realized inventory levels may exceed desired targets, further complicating learning dynamics. To address these challenges, we develop algorithms that combine online optimization with low-switching mechanisms and augmented loss functions, enabling effective learning despite these complexities. In the centralized setting, our algorithm converges to the first-best policy with low regret. In the decentralized setting, we design an adaptive coordination mechanism that yields favorable individual regret guarantees while learning the optimal contract, thereby incentivizing agents to implement the first-best policy and minimizing overall system regret. Numerical experiments demonstrate that our approach consistently outperforms standard benchmarks such as explore-then-exploit and vanilla online gradient descent, highlighting its robustness and practical relevance for supply chain coordination under demand uncertainty.

Decentralized online convex optimization (D-OCO), where multiple agents within a network collaboratively learn optimal decisions in real-time, arises naturally in applications such as federated learning, sensor networks, and multi-agent control. In this paper, we study D-OCO under unknown, time- and agent-varying feedback delays. While recent work has addressed this problem~nguyen2024handling, existing algorithms assume prior knowledge of the total delay over agents and still suffer from suboptimal dependence on both the delay and network parameters. To overcome these limitations, we propose a novel algorithm that achieves an improved regret bound of Õ(N √d_tot + N √( T / √(1 − σ₂) )), where d_tot denotes the average total delay across agents, N is the number of agents, and 1 − σ₂ is the spectral gap of the network. We also prove a lower bound showing that our upper bound is tight up to logarithmic factors. Our approach builds upon recent advances in D-OCO~wan2024nearly, but crucially incorporates an adaptive learning rate mechanism via a decentralized communication protocol. This enables each agent to estimate delays locally using a gossip-based strategy without the prior knowledge of the total delay. We further extend our framework to the strongly convex setting and derive a sharper regret bound. Experimental results validate the effectiveness of our approach, showing improvements over existing benchmark algorithms.

In this work, we study the online convex optimization problem with curved losses and delayed feedback. When losses are strongly convex, existing approaches obtain regret bounds of order dmaxlnT, where dmax is the maximum delay and T is the time horizon. However, in many cases, this guarantee can be much worse than dtot−−−√ as obtained by a delayed version of online gradient descent, where dtot is the total delay. We bridge this gap by proposing a variant of follow-the-regularized-leader that obtains regret of order min{σmaxlnT,dtot−−−√}, where σmax is the maximum number of missing observations. We then consider exp-concave losses and extend the Online Newton Step algorithm to handle delays with an adaptive learning rate tuning, achieving regret min{dmaxnlnT,dtot−−−√} where n is the dimension. To our knowledge, this is the first algorithm to achieve such a regret bound for exp-concave losses. We further consider the problem of unconstrained online linear regression and achieve a similar guarantee by designing a variant of the Vovk-Azoury-Warmuth forecaster with a clipping trick. Finally, we implement our algorithms and conduct experiments under various types of delay and losses, showing an improved performance over existing methods.

A recent work by Schlisselberg et al. (2025) studies a delay-as-payoff model for stochastic multiarmed bandits, where the payoff (either loss or reward) is delayed for a period that is proportional to the payoff itself. While this captures many real-world applications, the simple multiarmed bandit setting limits the practicality of their results. In this paper, we address this limitation by studying the delay-as-payoff model for contextual linear bandits. Specifically, we start from the case with a fixed action set and propose an efficient algorithm whose regret overhead compared to the standard no-delay case is at most D∆max log T, where T is the total horizon, D is the maximum delay, and ∆max is the maximum suboptimality gap. When payoff is loss, we also show further improvement of the bound, demonstrating a separation between reward and loss similar to Schlisselberg et al. (2025). Contrary to standard linear bandit algorithms that construct least squares estimator and confidence ellipsoid, the main novelty of our algorithm is to apply a phased arm elimination procedure by only picking actions in a volumetric spanner of the action set, which addresses challenges arising from both payoff-dependent delays and large action sets. We further extend our results to the case with varying action sets by adopting the reduction from Hanna et al. (2023). Finally, we implement our algorithm and showcase its effectiveness and superior performance in experiments

Motivated by alternating learning dynamics in two-player games, a recent work by Cevher et al. (2024) shows that o(T−−√) alternating regret is possible for any T-round adversarial Online Linear Optimization (OLO) problem, and left as an open question whether the same is true for general Online Convex Optimization (OCO). We answer this question in the affirmative by showing that the continuous Hedge algorithm achieves O~(d23T13) alternating regret for any adversarial d-dimensional OCO problems. We show that this implies an alternating learning dynamic that finds a Nash equilibrium for any convex-concave zero-sum games or a coarse correlated equilibrium for any convex two-player general-sum games at a rate of O~(d23/T23). To further improve the time complexity and/or the dimension dependence, we propose another simple algorithm, Follow-the-Regularized-Leader with a regularizer whose convex conjugate is 3rd-order smooth, for OCO with smooth and self-concordant loss functions (such as linear or quadratic losses). We instantiate our algorithm with different regularizers and show that, for example, when the decision set is the ℓ2 ball, our algorithm achieves O~(T25) alternating regret with no dimension dependence (and a better O~(T13) bound for quadratic losses). We complement our results by showing some algorithm-specific alternating regret lower bounds, including a somewhat surprising Ω(T−−√) lower bound for a Regret Matching variant that is widely used in alternating learning dynamics.

We consider the problem of online multi-agent Nash social welfare (NSW) maximization. While previous works of Hossain et al. [2021], Jones et al. [2023] study similar problems in stochastic multi-agent multi-armed bandits and show that √T -regret is possible after T rounds, their fairness measure is the product of all agents' rewards, instead of their NSW (that is, their geometric mean). Given the fundamental role of NSW in the fairness literature, it is more than natural to ask whether no-regret fair learning with NSW as the objective is possible. In this work, we provide a complete answer to this question in various settings. Specifically, in stochastic N-agent K-armed bandits, we develop an algorithm with $\widetilde{\mathcal{O}}(K^{\frac{2}{N}}T^{\frac{N-1}{N}})$ regret and prove that the dependence on T is tight, making it a sharp contrast to the √T-regret bounds of Hossain et al. [2021], Jones et al. [2023]. We then consider a more challenging version of the problem with adversarial rewards. Somewhat surprisingly, despite NSW being a concave function, we prove that no algorithm can achieve sublinear regret. To circumvent such negative results, we further consider a setting with full-information feedback and design two algorithms with √T-regret: the first one has no dependence on N at all and is applicable to not just NSW but a broad class of welfare functions, while the second one has better dependence on K and is preferable when N is small. Finally, we also show that logarithmic regret is possible whenever there exists one agent who is indifferent about different arms.

Interaction-Grounded Learning (IGL) [Xie et al., 2021] is a powerful framework in which a learner aims at maximizing unobservable rewards through interacting with an environment and observing reward-dependent feedback on the taken actions. To deal with personalized rewards that are ubiquitous in applications such as recommendation systems, Maghakian et al. [2022] study a version of IGL with context-dependent feedback, but their algorithm does not come with theoretical guarantees. In this work, we consider the same problem and provide the first provably efficient algorithms with sublinear regret under realizability. Our analysis reveals that the step-function estimator of prior work can deviate uncontrollably due to finite-sample effects. Our solution is a novel Lipschitz reward estimator which underestimates the true reward and enjoys favorable generalization performances. Building on this estimator, we propose two algorithms, one based on explore-then-exploit and the other based on inverse-gap weighting. We apply IGL to learning from image feedback and learning from text feedback, which are reward-free settings that arise in practice. Experimental results showcase the importance of using our Lipschitz reward estimator and the overall effectiveness of our algorithms.

We study a game between autobidding algorithms that compete in an online advertising platform. Each autobidder is tasked with maximizing its advertiser's total value over multiple rounds of a repeated auction, subject to budget and return-on-investment (ROI) constraints. We propose a gradient-based learning algorithm that is guaranteed to satisfy all constraints and achieves vanishing individual regret. Our algorithm uses only bandit feedback and can be used with the first- or second-price auction, as well as with any "intermediate" auction format. Our main result is that when these autobidders play against each other, the resulting expected liquid welfare over all rounds is at least half of the expected optimal liquid welfare achieved by any allocation.(1) Our analysis holds whether or not the bidding dynamics converges to an equilibrium, side-stepping the dearth of provable convergence guarantees in the literature and hardness results that preclude such guarantees for budget-constrained second-price auctions (Chen et al., 2021).
Our vanishing-regret result extends to an adversarial environment without any assumptions on the other agents. We adopt a non-standard benchmark: the sequence of bids such that each bid b(t) maximizes value for the round-t environment under time-averaged constraints. Hence, we side-step the impossibility results for the standard benchmark of best fixed bid (Balseiro and Gur, 2019). Our benchmark specializes to the standard one for a stationary environment.
When there is only a budget constraint, our algorithm specializes to an autobidding algorithm of Balseiro and Gur (2019), and our guarantees specialize to the regret and liquid welfare guarantees from Gaitonde et al. (2023). While our approach to bounding liquid welfare shares a common high-level strategy with Gaitonde et al. (2023), handling the ROI constraint, and particularly both constraints jointly, introduces a variety of new technical challenges. These challenges necessitate a new algorithm, changes to the way liquid welfare bounds are established, and a different methodology for establishing regret properties.

We study high-probability regret bounds for adversarial K-armed bandits with time-varying feedback graphs over T rounds. For general strongly observable graphs, we develop an algorithm that achieves the optimal regret (O) over tilde((Sigma T-t=1 alpha(t))(1/2) + max(t is an element of[T]) alpha t) with high probability, where alpha(t) is the independence number of the feedback graph at round t. Compared to the best existing result (Neu, 2015) which only considers graphs with self-loops for all nodes, our result not only holds more generally, but importantly also removes any poly(K) dependence that can be prohibitively large for applications such as contextual bandits. Furthermore, we also develop the first algorithm that achieves the optimal high-probability regret bound for weakly observable graphs, which even improves the best expected regret bound of (Alon et al., 2015b) by removing the O(root KT) term with a refined analysis. Our algorithms are based on the online mirror descent framework, but importantly with an innovative combination of several techniques. Notably, while earlier works use optimistic biased loss estimators for achieving high-probability bounds, we find it important to use a pessimistic one for nodes without self-loop in a strongly observable graph.