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 prove non-asymptotic lower bounds on the expectation of the maximum of d independent Gaussian variables and the expectation of the maximum of d independent symmetric random walks. Both lower bounds recover the optimal leading constant in the limit. A simple application of the lower bound for random walks is an (…
In this short note we consider a dynamic assortment planning problem under the capacitated multinomial logit (MNL) bandit model. We prove a tight lower bound on the accumulated regret that matches existing regret upper bounds for all parameters (time horizon T, number of items N and maximum assortment capacity K)…
We propose minimum regret search (MRS), a novel acquisition function for Bayesian optimization. MRS bears similarities with information-theoretic approaches such as entropy search (ES). However, while ES aims in each query at maximizing the information gain with respect to the global maximum, MRS aims at minimizing the…
Algorithm BGLM-OFU minimizes regret in combinatorial causal bandits with binary models.
problem Minimizing expected regret in combinatorial causal bandits with binary generalized linear models.
method BGLM-OFU algorithm based on maximum likelihood estimation for Markovian BGLMs, and causal inference techniques for linear models with hidden variables.
result Achieves O(TlogT) regret for binary generalized linear models.
Unified framework for ensemble sampling in nonlinear contextual bandits with provable regret bounds.
problem Efficient exploration in nonlinear contextual bandits with unknown feature dimensions.
method Developed GLM-ES and Neural-ES for generalized linear and neural contextual bandits, respectively, using maximum likelihood estimation on randomly perturbed data.
result Unified high-probability frequentist regret bounds for GLM-ES and Neural-ES, matching state-of-the-art results.
We study the problem of selling an asset near its ultimate maximum in the minimax setting. The regret-based notion of a perfect stopping time is introduced. A perfect stopping time is uniquely characterized by its optimality properties and has the following form: one should sell the asset if its price deviates from the…
We study the regret of optimal strategies for online convex optimization games. Using von Neumann's minimax theorem, we show that the optimal regret in this adversarial setting is closely related to the behavior of the empirical minimization algorithm in a stochastic process setting: it is equal to the maximum, over jo…
To deal with changing environments, a new performance measure -- adaptive regret, defined as the maximum static regret over any interval, was proposed in online learning. Under the setting of online convex optimization, several algorithms have been successfully developed to minimize the adaptive regret. However, existi…
We consider combinatorial online learning with subset choices when only relative feedback information from subsets is available, instead of bandit or semi-bandit feedback which is absolute. Specifically, we study two regret minimisation problems over subsets of a finite ground set [n], with subset-wise relative prefe…
We improve the efficiency of algorithms for stochastic \emph{combinatorial semi-bandits}. In most interesting problems, state-of-the-art algorithms take advantage of structural properties of rewards, such as \emph{independence}. However, while being optimal in terms of asymptotic regret, these algorithms are inefficien…
Study optimal policy regret in partially observable Markov games with adaptive opponents.
problem Optimal sequential decision-making in partially observable environments against strategic, adaptive opponents.
method An epoch-based optimistic maximum-likelihood algorithm that selects one policy per epoch using confidence sets built cumulatively from past data.
result Achieves ildeO(T) policy regret for fixed problem parameters, with explicit dependence on horizon, adversary memory, confidence radius, and aggregate Eluder dimension.
Considering mean-variance portfolio problems with uncertain model parameters, we contrast the classical absolute robust optimization approach with the relative robust approach based on a maximum regret function. Although the latter problems are NP-hard in general, we show that tractable inner and outer approximations e…
Inspired by the Reward-Biased Maximum Likelihood Estimate method of adaptive control, we propose RBMLE -- a novel family of learning algorithms for stochastic multi-armed bandits (SMABs). For a broad range of SMABs including both the parametric Exponential Family as well as the non-parametric sub-Gaussian/Exponential f…
The paper improves on existing algorithms for minimizing different types of regret in online learning.
problem Minimizing external, internal, and swap regret in online learning with multiple experts.
method Develops a single algorithm using φ-regret minimization and Haar-wavelet-inspired matrix features to achieve optimal bounds in various scenarios.
result Achieves optimal bounds for external, internal, and swap regrets in different expert scenarios.
We consider revenue maximization in online auction/pricing problems. A seller sells an identical item in each period to a new buyer, or a new set of buyers. For the online posted pricing problem, we show regret bounds that scale with the best fixed price, rather than the range of the values. We also show regret bounds …
This paper analyses the problem of Gaussian process (GP) bandits with deterministic observations. The analysis uses a branch and bound algorithm that is related to the UCB algorithm of (Srinivas et al., 2010). For GPs with Gaussian observation noise, with variance strictly greater than zero, (Srinivas et al., 2010) pro…
The paper explores how over-parameterized linear regression models generalize without violating learning theory principles.
problem Understanding how over-parameterized linear regression models generalize without violating learning theory principles.
method The paper uses the predictive normalized maximum likelihood (pNML) learner to investigate the minimum norm solution of over-parameterized linear regression models.
result The model generalizes well when the test sample lies in a subspace spanned by eigenvectors associated with large eigenvalues of the training data.
This paper analyzes the problem of Gaussian process (GP) bandits with deterministic observations. The analysis uses a branch and bound algorithm that is related to the UCB algorithm of (Srinivas et al, 2010). For GPs with Gaussian observation noise, with variance strictly greater than zero, Srinivas et al proved that t…
The normalized maximized likelihood (NML) provides the minimax regret solution in universal data compression, gambling, and prediction, and it plays an essential role in the minimum description length (MDL) method of statistical modeling and estimation. Here we show that the normalized maximum likelihood has a Bayes-li…