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.

We study stochastic linear bandits with delayed feedback under several delay models and establish near-optimal regret guarantees. Our results identify when delayed linear bandits exhibit the same qualitative behavior as multi-armed bandits (MAB), and when the linear structure creates fundamentally new challenges. Specifically, (1) for loss-independent delays, where the delay does not depend on the realized loss (but potentially depends on the arm), we show that delays incur only an additive regret penalty. Under stochastic delays, this penalty scales with the expected delay, while under adversarial delays, it scales with the maximum number of outstanding observations. Notably, both delay penalties are dimension-free, improving upon the state-of-the-art results; (2) for loss-dependent delays, we show that linear bandits are substantially harder than MAB: unlike in MAB, we prove matching (up to log factors) upper and lower bounds in linear bandits, whose delay penalty depends on the square root of the dimension. (3) for the delay-as-payoff model, a special case of loss-dependent delay, we show that the optimal MAB guarantee, which depends only on the delay of the optimal arm, is also unattainable in linear bandits. Together, these results provide a sharp characterization of how delayed feedback interacts with linear generalization.

Last-iterate convergence of learning dynamics in games has attracted significant recent attention. In two-player zero-sum games with bandit feedback, where only the loss of the selected action pair is observed, Fiegel et al. (2025) show a separation between average-iterate and last-iterate convergence in duality gap: while the optimal t⁽-1/2) rate after t rounds is achievable for the former via standard no-regret algorithms, the latter cannot converge faster than t⁽-1/3) in expectation or t⁽-1/4) with high probability. However, in many practical settings, such as preference learning, the players observe not only their loss but also the opponent's action. This raises a natural question: can such additional information enable faster last-iterate convergence? We answer this question affirmatively, showing that t⁽-1/2) last-iterate convergence is achievable with high probability in this setting, via an efficient algorithm that updates its strategy infrequently by solving an estimated log-barrier-regularized game. We identify fundamental obstacles preventing standard analysis for multi-armed bandits, the single-player case, from generalizing to games, and develop a novel analysis to overcome them. Experiments confirm that our algorithm indeed converges faster than naive baselines and prior methods that do not exploit opponent-action feedback. Finally, we note that our results also improve those for dueling bandits, a special case with skew-symmetric game matrices.

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 sample complexity of obtaining a Nash equilibrium (NE) estimate in two-player zero-sum matrix games with noisy feedback. Specifically, we propose a novel algorithm that repeatedly solves linear programs (LPs) to obtain an NE estimate with bias at most$\varepsilon$with a sample complexity of$O\left(\frac{m_1 m_2}{\varepsilon\min\{δ^2,σ_0^2,σ^3\}} \log\frac{m_1 m_2}{\varepsilon}\right)$for general$m_1 \times m_2$game matrices, where$σ$ ,$σ_0$ ,$δ$are some problem-dependent constants. To our knowledge, this is the first instance-dependent sample complexity bound for finding an NE estimate with$\varepsilon$bias in general-dimension matrix games with noisy feedback and potentially non-unique equilibria. Our algorithm builds on recent advances in online resource allocation and operates in two stages: (1) identifying the support set of an NE, and (2) computing the unique NE restricted to this support. Both stages rely on a careful analysis of LP solutions derived from noisy samples.

We study the pricing query complexity of revenue maximization for a single buyer whose private valuation is drawn from an unknown distribution. In this setting, the seller must learn the optimal monopoly price by posting prices and observing only binary purchase decisions, rather than the realized valuations. Prior work has established tight query complexity bounds for learning a near-optimal price with additive errorεwhen the valuation distribution is supported on[0,1] . However, our understanding of how to learn a near-optimal price that achieves at least a(1-ε)fraction of the optimal revenue remains limited. In this paper, we study the pricing query complexity of the single-buyer revenue maximization problem under such multiplicative error guarantees in several settings. Observe that when pricing queries are the only source of information about the buyer's distribution, no algorithm can achieve a non-trivial approximation, since the scale of the distribution cannot be learned from pricing queries alone. Motivated by this fundamental impossibility, we consider two natural and well-motivated models that provide "scale hints": (i) a one-sample hint, in which the algorithm observes a single realized valuation before making pricing queries; and (ii) a value-range hint, in which the valuation support is known to lie within[1, H] . For each type of hint, we establish pricing query complexity guarantees that are tight up to polylogarithmic factors for several classes of distributions, including monotone hazard rate (MHR) distributions, regular distributions, and general distributions.

In this paper, we study Interaction-Grounded Learning (IGL) [Xie et al., 2021], a paradigm designed for realistic scenarios where the learner receives indirect feedback generated by an unknown mechanism, rather than explicit numerical rewards. While prior work on IGL provides efficient algorithms with provable guarantees, those results are confined to single-step settings, restricting their applicability to modern sequential decision-making systems such as multi-turn Large Language Model (LLM) deployments. To bridge this gap, we propose a computationally efficient algorithm that achieves a sublinear regret guarantee for contextual episodic Markov Decision Processes (MDPs) with personalized feedback. Technically, we extend the reward-estimator construction of Zhang et al. [2024a] from the single-step to the multi-step setting, addressing the unique challenges of decoding latent rewards under MDPs. Building on this estimator, we design an Inverse-Gap-Weighting (IGW) algorithm for policy optimization. Finally, we demonstrate the effectiveness of our method in learning personalized objectives from multi-turn interactions through experiments on both a synthetic episodic MDP and a real-world user booking dataset.

We study distributed adversarial bandits, whereNagents cooperate to minimize the global average loss while observing only their own local losses. We show that the minimax regret for this problem is\tildeΘ{(}{√(̅ρ̅^̅(̅-̅1̅/̅2̅)̅+̅K̅/̅N̅)̅T̅}{)} , whereTis the horizon,Kis the number of actions, andρis the spectral gap of the communication matrix. Our algorithm, based on a novel black-box reduction to bandits with delayed feedback, requires agents to communicate only through gossip. It achieves an upper bound that significantly improves over the previous best boundÕ(ρ^(-1/3)(KT)^(2/3))of Yi and Vojnovic (2023). We complement this result with a matching lower bound, showing that the problem's difficulty decomposes into a communication costρ^(-1/4)√T̅and a bandit cost√K̅T̅/̅N̅ . We further demonstrate the versatility of our approach by deriving first-order and best-of-both-worlds bounds in the distributed adversarial setting. Finally, we extend our framework to distributed linear bandits inRᵈ , obtaining a regret bound ofÕ(√(̅ρ̅^̅(̅-̅1̅/̅2̅)̅+̅1̅/̅N̅)̅d̅T̅) , achieved with onlyO(d)communication cost per agent and per round via a volumetric spanner.

In this paper, we study dynamic regret in unconstrained online convex optimization (OCO) with movement costs. Specifically, we generalize the standard setting by allowing the movement cost coefficientsλ_(t)to vary arbitrarily over time. Our main contribution is a novel algorithm that establishes the first comparator-adaptive dynamic regret bound for this setting, guaranteeing\widetilde{𝓞}{(}{√(̅1̅+̅P̅_̅(̅T̅)̅)̅(̅T̅+̅∑̅_̅(̅t̅)̅ ̅λ̅_̅(̅t̅)̅)̅})regret, whereP_(T)is the path length of the comparator sequence overTrounds. This recovers the optimal guarantees for both static and dynamic regret in standard OCO as a special case whereλ_(t)=0for all rounds. To demonstrate the versatility of our results, we consider two applications: OCO with delayed feedback and OCO with time-varying memory. We show that both problems can be translated into time-varying movement costs, establishing a novel reduction specifically for the delayed feedback setting that is of independent interest. A crucial observation is that the first-order dependence on movement costs in our regret bound plays a key role in enabling optimal comparator-adaptive dynamic regret guarantees in both settings.

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 (Nguyen et al., 2024), 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 O N$\sqrt$d tot + N$\sqrt$T (1- $σ$ 2) 1/4 , where T is the total horizon, d tot denotes the average total delay across agents, N is the number of agents, and 1 - $σ$2 is the spectral gap of the network. Our approach builds upon recent advances in D-OCO (Wan et al., 2024a), 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 of O N$δ$ max ln T$α$, where$α$is the strong convexity parameter and$δ$max is the maximum number of missing observations averaged over agents. We also show that our upper bounds for both settings are tight up to logarithmic factors. Experimental results validate the effectiveness of our approach, showing improvements over existing benchmark algorithms.