A locally-built, LLM-digested index of recent arXiv papers in quant finance, geometry/topology, and statistical ML — keyword search served straight from SQLite on this machine.
We consider regret minimization in repeated games with non-convex loss functions. Minimizing the standard notion of regret is computationally intractable. Thus, we define a natural notion of regret which permits efficient optimization and generalizes offline guarantees for convergence to an approximate local optimum. W…
We consider online algorithms under both the competitive ratio criteria and the regret minimization one. Our main goal is to build a unified methodology that would be able to guarantee both criteria simultaneously. For a general class of online algorithms, namely any Metrical Task System (MTS), we show that one can sim…
Adaptive designs achieve strong Neyman regret guarantees for ATE estimation.
problem Estimating unbiased average treatment effect in sequential experiments.
method Proposed adaptive designs with O(logT) Neyman regret under boundedness assumptions and O(T) multigroup Neyman regret in covariate-based settings.
result Adaptive designs outperform non-adaptive designs in terms of Neyman regret, especially in covariate-based settings.
Efficient algorithms for online learning with changing action sets, achieving no-approximate-regret guarantees.
problem Online learning with sleeping experts/bandits, where only a subset of actions are available each time.
method Developed computationally efficient algorithms providing no-approximate-regret guarantees for the general problem and better approximation ratios for special cases.
result Achieved no-approximate-regret guarantees for the general sleeping expert/bandit problems and better approximation ratios for specific cases.
Thompson Sampling remains differentially private with minimal modifications.
problem Ensuring privacy in Thompson Sampling for multi-arm bandits.
method Demonstrated differential privacy of original Thompson Sampling, provided per-round guarantees, and introduced modifications for tighter privacy.
result Privacy guarantees can be tuned by modifying the algorithm, and these modifications impact expected regret.
We show how to take any two parameter-free online learning algorithms with different regret guarantees and obtain a single algorithm whose regret is the minimum of the two base algorithms. Our method is embarrassingly simple: just add the iterates. This trick can generate efficient algorithms that adapt to many norms s…
Paper analyzes faster convergence rates for reinforcement learning from offline data.
problem Analyzing faster convergence rates for reinforcement learning from offline data.
method Fine analysis of reinforcement learning from offline data, providing fast rates for regret convergence.
result The paper provides fast rates for the regret convergence, showing that the level of exponentiation depends on the noise in the decision-making problem.
I analyse the frequentist regret of the famous Gittins index strategy for multi-armed bandits with Gaussian noise and a finite horizon. Remarkably it turns out that this approach leads to finite-time regret guarantees comparable to those available for the popular UCB algorithm. Along the way I derive finite-time bounds…
Recent literature on online learning has focused on developing adaptive algorithms that take advantage of a regularity of the sequence of observations, yet retain worst-case performance guarantees. A complementary direction is to develop prediction methods that perform well against complex benchmarks. In this paper, we…
We derive an online learning algorithm with improved regret guarantees for `easy' loss sequences. We consider two types of `easiness': (a) stochastic loss sequences and (b) adversarial loss sequences with small effective range of the losses. While a number of algorithms have been proposed for exploiting small effective…
We consider a variant of the contextual bandit problem. In standard contextual bandits, when a user arrives we get the user's complete feature vector and then assign a treatment (arm) to that user. In a number of applications (like healthcare), collecting features from users can be costly. To address this issue, we pro…
Learning reward functions can lead to poor policy performance despite low error.
problem Low error in learned reward functions does not guarantee low regret in policy performance.
method Mathematical analysis of reward learning and policy optimization.
result A low expected test error of the reward model guarantees low worst-case regret, but error-regret mismatch can occur with certain data distributions.
Regret minimization is treated as the golden rule in the traditional study of online learning. However, regret minimization algorithms tend to converge to the static optimum, thus being suboptimal for changing environments. To address this limitation, new performance measures, including dynamic regret and adaptive regr…
We consider undiscounted reinforcement learning in Markov decision processes (MDPs) where both the reward functions and the state-transition probabilities may vary (gradually or abruptly) over time. For this problem setting, we propose an algorithm and provide performance guarantees for the regret evaluated against the…
We study an interesting variant of the stochastic multi-armed bandit problem, called the Fair-SMAB problem, where each arm is required to be pulled for at least a given fraction of the total available rounds. We investigate the interplay between learning and fairness in terms of a pre-specified vector denoting the frac…
We study an interesting variant of the stochastic multi-armed bandit problem, called the Fair-SMAB problem, where each arm is required to be pulled for at least a given fraction of the total available rounds. We investigate the interplay between learning and fairness in terms of a pre-specified vector denoting the frac…