28 citations · 105 across the 29 of their papers we have counts for
29 papers
Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits
Mengxiao Zhang
We study second-order path-length regret in adversarial -armed bandits against oblivious loss sequences. Bubeck et al. [2019] designed an algorithm that achieves $\widetilde{\ma…
Near-Optimal Stochastic Linear Bandits with Delay
Ofir Schlisselberg, Mengxiao Zhang, Yishay Mansour
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 e…
Near-Optimal Last-Iterate Convergence for Zero-Sum Games with Bandit Feedback and Opponent Actions
Soumita Hait, Ping Li, Haipeng Luo +1
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 sel…
Interaction-Grounded Learning for Contextual Markov Decision Processes with Personalized Feedback
Mengxiao Zhang, Yuheng Zhang, Haipeng Luo +1
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 b…
Exploiting Curvature in Online Convex Optimization with Delayed Feedback
Hao Qiu, Emmanuel Esposito, Mengxiao Zhang
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…
Complexity and Manipulation of International Kidney Exchange Programmes with Country-Specific Parameters
Rachael Colley, David Manlove, Daniel Paulusma +1
Kidney Exchange Programmes (KEPs) facilitate the exchange of kidneys, and larger pools of recipient-donor pairs tend to yield proportionally more transplants, leading to the propos…
Comparator-Adaptive -Regret: Improved Bounds, Simpler Algorithms, and Applications to Games
Soumita Hait, Ping Li, Haipeng Luo +1
In the classic expert problem, -regret measures the gap between the learner's total loss and that achieved by applying the best action transformation . A recent work by…
Contextual Linear Bandits with Delay as Payoff
Mengxiao Zhang, Yingfei Wang, Haipeng Luo
A recent work by Schlisselberg et al. (2024) studies a delay-as-payoff model for stochastic multi-armed bandits, where the payoff (either loss or reward) is delayed for a period th…
Alternating Regret for Online Convex Optimization
Soumita Hait, Ping Li, Haipeng Luo +1
Motivated by alternating learning dynamics in two-player games, a recent work by Cevher et al.(2024) shows that alternating regret is possible for any -round adver…
No-Regret Learning for Fair Multi-Agent Social Welfare Optimization
Mengxiao Zhang, Ramiro Deo-Campo Vuong, Haipeng Luo
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 s…
Provably Efficient Interactive-Grounded Learning with Personalized Reward
Mengxiao Zhang, Yuheng Zhang, Haipeng Luo +1
Interactive-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 an…
Contextual Multinomial Logit Bandits with General Value Functions
Mengxiao Zhang, Haipeng Luo
Contextual multinomial logit (MNL) bandits capture many real-world assortment recommendation problems such as online retailing/advertising. However, prior work has only considered…
Efficient Contextual Bandits with Uninformed Feedback Graphs
Mengxiao Zhang, Yuheng Zhang, Haipeng Luo +1
Bandits with feedback graphs are powerful online learning models that interpolate between the full information and classic bandit problems, capturing many real-life applications. A…
Online Learning in Contextual Second-Price Pay-Per-Click Auctions
Mengxiao Zhang, Haipeng Luo
We study online learning in contextual pay-per-click auctions where at each of the rounds, the learner receives some context along with a set of ads and needs to make an estima…
Practical Contextual Bandits with Feedback Graphs
Mengxiao Zhang, Yuheng Zhang, Olga Vrousgou +2
While contextual bandit has a mature theory, effectively leveraging different feedback patterns to enhance the pace of learning remains unclear. Bandits with feedback graphs, which…
Autobidders with Budget and ROI Constraints: Efficiency, Regret, and Pacing Dynamics
Brendan Lucier, Sarath Pattathil, Aleksandrs Slivkins +1
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…
Improved High-Probability Regret for Adversarial Bandits with Time-Varying Feedback Graphs
Haipeng Luo, Hanghang Tong, Mengxiao Zhang +1
We study high-probability regret bounds for adversarial -armed bandits with time-varying feedback graphs over rounds. For general strongly observable graphs, we develop an a…
Corralling a Larger Band of Bandits: A Case Study on Switching Regret for Linear Bandits
Haipeng Luo, Mengxiao Zhang, Peng Zhao +1
We consider the problem of combining and learning over a set of adversarial bandit algorithms with the goal of adaptively tracking the best one on the fly. The CORRAL algorithm of…
Adaptive Bandit Convex Optimization with Heterogeneous Curvature
Haipeng Luo, Mengxiao Zhang, Peng Zhao
We consider the problem of adversarial bandit convex optimization, that is, online learning over a sequence of arbitrary convex loss functions with only one function evaluation for…
No-Regret Learning in Time-Varying Zero-Sum Games
Mengxiao Zhang, Peng Zhao, Haipeng Luo +1
Learning from repeated play in a fixed two-player zero-sum game is a classic problem in game theory and online learning. We consider a variant of this problem where the game payoff…
Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei +2
In this work, we develop linear bandit algorithms that automatically adapt to different environments. By plugging a novel loss estimator into the optimization problem that characte…
Last-iterate Convergence of Decentralized Optimistic Gradient Descent/Ascent in Infinite-horizon Competitive Markov Games
Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang +1
We study infinite-horizon discounted two-player zero-sum Markov games, and develop a decentralized algorithm that provably converges to the set of Nash equilibria under self-play.…
The Relevance of Classic Fuzz Testing: Have We Solved This One?
Barton P. Miller, Mengxiao Zhang, Elisa R. Heymann
As fuzz testing has passed its 30th anniversary, and in the face of the incredible progress in fuzz testing techniques and tools, the question arises if the classic, basic fuzz tec…
RANDOM MASK: Towards Robust Convolutional Neural Networks
Tiange Luo, Tianle Cai, Mengxiao Zhang +2
Robustness of neural networks has recently been highlighted by the adversarial examples, i.e., inputs added with well-designed perturbations which are imperceptible to humans but c…