12 papers
Follow the Perturbed Leader for Linear Bandits: Regret over General Action Sets
Chen-Yu Wei
We give the first adversarial linear bandit algorithm based on Follow-the-Perturbed-Leader (FTPL) that achieves regret over general action sets. Our algorithm attains $\…
Achieving Optimal Static and Dynamic Regret Simultaneously in Bandits with Deterministic Losses
Jian Qian, Chen-Yu Wei
In adversarial multi-armed bandits, two performance measures are commonly used: static regret, which compares the learner to the best fixed arm, and dynamic regret, which compares…
Is Online Linear Optimization Sufficient for Strategic Robustness?
Yang Cai, Haipeng Luo, Chen-Yu Wei +1
We consider bidding in repeated Bayesian first-price auctions. Bidding algorithms that achieve optimal regret have been extensively studied, but their strategic robustness to the s…
On the Complexity of Offline Reinforcement Learning with -Approximation and Partial Coverage
Haolin Liu, Braham Snyder, Chen-Yu Wei
We study offline reinforcement learning under -approximation and partial coverage, a setting that motivates practical algorithms such as Conservative -Learning (CQL; Ku…
Save the Good Prefix: Precise Error Penalization via Process-Supervised RL to Enhance LLM Reasoning
Haolin Liu, Dian Yu, Sidi Lu +6
Reinforcement learning (RL) has emerged as a powerful framework for improving the reasoning capabilities of large language models (LLMs). However, most existing RL approaches rely…
An Improved Model-Free Decision-Estimation Coefficient with Applications in Adversarial MDPs
Haolin Liu, Chen-Yu Wei, Julian Zimmert
We study decision making with structured observation (DMSO). Previous work (Foster et al., 2021b, 2023a) has characterized the complexity of DMSO via the decision-estimation coeffi…
An Improved Algorithm for Adversarial Linear Contextual Bandits via Reduction
Tim van Erven, Jack Mayo, Julia Olkhovskaya +1
We present an oracle-efficient, near-optimal algorithm for linear contextual bandits with adversarial losses and stochastic action sets, only requiring a linear optimization oracle…
Decision Making in Hybrid Environments: A Model Aggregation Approach
Haolin Liu, Chen-Yu Wei, Julian Zimmert
Recent work by Foster et al. (2021, 2022, 2023b) and Xu and Zeevi (2023) developed the framework of decision estimation coefficient (DEC) that characterizes the complexity of gener…
Beating Adversarial Low-Rank MDPs with Unknown Transition and Bandit Feedback
Haolin Liu, Zakaria Mhammedi, Chen-Yu Wei +1
We consider regret minimization in low-rank MDPs with fixed transition and adversarial losses. Previous work has investigated this problem under either full-information loss feedba…
Corruption-Robust Linear Bandits: Minimax Optimality and Gap-Dependent Misspecification
Haolin Liu, Artin Tajdini, Andrew Wagenmaker +1
In linear bandits, how can a learner effectively learn when facing corrupted rewards? While significant work has explored this question, a holistic understanding across different a…
Towards Optimal Regret in Adversarial Linear MDPs with Bandit Feedback
Haolin Liu, Chen-Yu Wei, Julian Zimmert
We study online reinforcement learning in linear Markov decision processes with adversarial losses and bandit feedback, without prior knowledge on transitions or access to simulato…
Bypassing the Simulator: Near-Optimal Adversarial Linear Contextual Bandits
Haolin Liu, Chen-Yu Wei, Julian Zimmert
We consider the adversarial linear contextual bandit problem, where the loss vectors are selected fully adversarially and the per-round action set (i.e. the context) is drawn from…