Improved regret bound for linear ensemble sampling.
problem Closing the gap between theory and practice in linear ensemble sampling.
method General regret analysis framework for linear bandit algorithms, revealing a relationship with LinPHE.
result Achieves a frequentist regret bound of i l d e O ( d 3 / 2 T ) ilde{O}(d^{3/2}\sqrt{T}) i l d e O ( d 3/2 T ) for linear ensemble sampling. We establish linear regret bounds for convex smooth losses using Fenchel-Young losses.
problem Establishing linear regret bounds for convex smooth losses.
method Constructing a convex smooth surrogate loss using Fenchel-Young losses generated by the convolutional negentropy.
result We derive a smooth loss with a linear surrogate regret bound.
A new linear contextual bandit algorithm with improved regret bound.
problem Efficiently solving linear contextual bandit problems with reduced regret.
method Proposes a novel estimator embedded with exploration and a self-normalized bound.
result Regret bound matches lower bound of Ω ( d T ) Ω(\sqrt{dT}) Ω ( d T ) up to logarithmic factors. The paper tightens the regret rate for linear bandit problems.
problem Bayesian regret in linear bandit problems.
method Information-theoretic framework and chaining argument.
result Established a new bound with a tight rate of O ( d T ) O(d\sqrt{T}) O ( d T ) . This paper achieves optimal regret bounds for locally private linear contextual bandit.
problem Designing locally private linear contextual bandit algorithms with optimal regret bounds.
method New algorithmic and analytical ideas, including mean absolute deviation analysis and layered principal component regression.
result Achieves an i l d e O ( T ) ilde O(\sqrt{T}) i l d e O ( T ) regret upper bound for locally private linear contextual bandit. Bayesian bandit algorithms with approximate inference improve regret bounds in stochastic linear bandits.
problem Theoretical justification for Bayesian bandit algorithms with approximate inference in stochastic linear bandits.
method Proposed a theoretical framework to analyze approximate inference impact and conducted frequentist regret analysis on LinTS and LinBUCB.
result LinTS and LinBUCB preserve their original regret upper bounds with larger constant terms in approximate inference settings.
The paper addresses frequentist regret of Linear Thompson Sampling in stochastic linear bandits.
problem The frequentist regret of Linear Thompson Sampling (LinTS) is worse than its Bayesian counterpart.
method The paper proves the fundamental nature of the frequentist regret bound for LinTS and proposes a data-driven version of LinTS to achieve minimax optimal frequentist regret.
result The frequentist regret bound for LinTS is O ~ ( d d T ) \widetilde{\mathcal{O}}(d\sqrt{dT}) O ( d d T ) , which is the best possible under certain conditions. New algorithms for linear bandits avoid norm knowledge, reducing regret.
problem Linear bandits require knowledge of norm bound S S S on parameter θ ∗ θ^* θ ∗ , leading to high regret. method Proposes two novel algorithms for changing and fixed arm sets, analyzing their regret bounds.
result Regret bounds show no significant price for not knowing S S S , with no price for fixed arm sets. Logarithmic regret achieved in RL with linear function approximation.
problem Achieving logarithmic regret in reinforcement learning with linear function approximation.
method LSVI-UCB for linear MDP assumption, UCRL-VTR for linear mixture MDP assumption.
result Logarithmic regret bounds established for RL with linear function approximation.
Balances and eliminates base algorithms in bandits and RL to bound total regret.
problem Model selection in bandits and reinforcement learning with unknown optimal regret.
method Balances and eliminates base algorithms based on candidate regret bounds.
result Total regret bound is the best valid candidate regret bound times a small multiplicative factor.
Study linear contextual bandits with confounded offline data, improving regret bounds.
problem Linear contextual bandits with confounded offline data.
method Construct a linear bandit algorithm that utilizes projected information.
result Proved regret bounds that improve current bounds by a factor related to visible dimensionality.
This paper improves online learning algorithms for LP problems, achieving better regret bounds.
problem Achieving optimal regret bounds in online linear programming.
method Develops a new framework for first-order online learning algorithms under certain error bound conditions.
result First-order learning algorithms achieve o ( T ) o(\sqrt{T}) o ( T ) regret in continuous support and O ( log T ) \mathcal{O}(\log T) O ( log T ) regret in finite support, improving over O ( T ) \mathcal{O}(\sqrt{T}) O ( T ) . New algorithm reduces regret in delayed feedback generalised linear bandits.
problem Regret in delayed feedback generalised linear bandits.
method Adaptation of optimistic algorithm to delayed feedback.
result Achieves a regret bound independent of the horizon's delay penalty.
New algorithm reduces regret in linear mixture SSPs without cost bounds.
problem Learning optimal paths in stochastic environments with cost constraints.
method Extended value iteration with variance-aware confidence set.
result Achieves nearly minimax optimal regret bound of O ( d B ∗ K ) O(dB_*\sqrt{K}) O ( d B ∗ K ) . New bounds for high-dimensional sparse linear bandits, balancing information and regret.
problem Stochastic linear bandits with high-dimensional sparse features.
method Derivation of minimax regret lower and upper bounds for explore-then-commit algorithm.
result Optimal rate of Θ ( n 2 / 3 ) Θ(n^{2/3}) Θ ( n 2/3 ) for data-poor regime, complemented by O ( n ) O(\sqrt{n}) O ( n ) under signal magnitude assumption. Algorithm reduces regret in SSP problems with LFA.
problem Finding shortest paths in stochastic environments with linear approximations.
method Uses linear function approximation and stationary policies to minimize regret.
result Achieves sublinear regret under minimal assumptions.
New algorithm reduces regret in GLM bandits with tighter bounds.
problem Reducing regret in generalized linear contextual bandits.
method Double Doubly Robust (DDR) estimator for independence.
result First d \sqrt{d} d regret bound for GLM bandits. New bounds on self-normalized martingales improve online linear regression performance.
problem Improving regret bounds in online linear regression.
method Characterizing scale-invariant bounds on self-normalized martingales.
result For d = 1 d=1 d = 1 , O ( log T ) O(\log T) O ( log T ) doubly-uniform regret is possible; for d > 1 d>1 d > 1 , sublinear doubly-uniform regret is impossible. Improved regret bounds for linear bandits with heavy-tailed rewards.
problem Stochastic linear bandits with heavy-tailed rewards.
method Elimination-based algorithm guided by experimental design.
result Regret bound of \(\tilde{\mathcal{O}}(d^\frac{1+3ε}{2(1+ε)} T^\frac{1}{1+ε})\) for \(ε\in (0,1)\).
An algorithm for maximizing rewards under linear cost constraints.
problem Maximizing rewards while adhering to cost constraints in a linear bandit problem.
method Proposes an upper-confidence bound algorithm called optimistic pessimistic linear bandit (OPLB) for constrained contextual linear bandits.
result Proves an O ~ ( d T τ − c 0 ) \widetilde{\mathcal{O}}(\frac{d\sqrt{T}}{τ-c_0}) O ( τ − c 0 d T ) bound on regret for the proposed algorithm. New algorithm reduces control error in systems with changing dynamics.
problem Online control of systems with time-varying linear dynamics.
method Introduces adaptive regret metric and a novel meta-algorithm.
result First adaptive regret bound for online convex optimization with memory.
New algorithm learns optimal path in reinforcement learning with linear approximations.
problem Optimal path learning in reinforcement learning with linear approximations.
method Proposes novel algorithm with Hoeffding-type and Bernstein-type confidence sets.
result Achieves near-optimal regret guarantee for linear mixture SSP.
IDS improves sparse linear bandits by balancing information and regret.
problem Sparse linear bandits in high-dimensional decision-making.
method Information-directed sampling (IDS) with Bayesian regret bounds and empirical Bayesian sparse posterior sampling.
result IDS nearly matches existing lower bounds and significantly reduces regret.
Randomized exploration in linear bandits achieves optimal regret bounds.
problem Optimizing exploration in high-dimensional linear bandit problems.
method Analysis of Thompson sampling without forced optimism.
result Randomized exploration algorithms achieve an O ( d n log ( n ) ) O(d\sqrt{n} \log(n)) O ( d n log ( n )) regret bound in smooth, strongly convex action spaces. Significant improvements in regret analysis for adaptive online learning problems.
problem Exploiting low variance in online learning problems without known variances.
method Novel peeling-based regret analysis leveraging elliptical potential `count` lemma.
result Significant improvements in regret bounds for linear bandits and linear mixture MDPs.
TRAiL is a linear bandit algorithm that ensures optimal regret and guarantees inference quality.
problem Optimal regret and inference quality in linear bandits with convex action sets.
method TRAiL estimates the parameter through regularized least squares and perturbs the action set along the tangent plane.
result TRAiL achieves an Ω ( T ) Ω(\sqrt{T}) Ω ( T ) upper bound on cumulative regret with high probability. New method for linear bandits with unknown sparsity, improving sparse regret bounds.
problem Sparse regret bounds for unknown sparsity and adversarial action sets.
method Combines online to confidence set conversions with randomized model selection over nested confidence sets.
result First sparse regret bounds for unknown sparsity and adversarial action sets.
We study the problem of regret minimization in partially observable linear quadratic control systems when the model dynamics are unknown a priori. We propose ExpCommit, an explore-then-commit algorithm that learns the model Markov parameters and then follows the principle of optimism in the face of uncertainty to desig…
New algorithm reduces regret in CBs with time-varying models.
problem Designing robust interventions in CBs with unknown, fluctuating causal models.
method Proposes a robust CB algorithm with upper and lower bounds on regret.
result Achieves nearly optimal i l d e O ( T ) ilde{\mathcal{O}}(\sqrt{T}) i l d e O ( T ) regret under certain conditions. We achieve a finite regret bound of O(dlogd) for online inverse linear optimization with M-convex action sets.
problem Online inverse linear optimization with M-convex action sets.
method Combining structural characterization of optimal solutions on M-convex sets with geometric volume argument.
result Finite regret bound of O(dlogd) for online inverse linear optimization with M-convex action sets.
VO Q Q Q L optimizes RL with sparse rewards using weighted bounds.
problem Sparse rewards and non-linear function approximation in RL.
method VO Q Q Q L combines Q Q Q -learning with weighted bounds for optimal regret. result Achieves asymptotically optimal regret for linear function approximation.
Study on online regression with noise, achieving near-optimal regret bounds.
problem Online generalized linear regression with stochastic noise.
method Sharp analysis of FTRL algorithm for stochastic label noise.
result Achieved near-optimal regret bounds for O ( σ 2 d log T ) + o ( log T ) O(σ^2 d \log T) + o(\log T) O ( σ 2 d log T ) + o ( log T ) . New algorithm minimizes Bayesian regret in offline linear bandits.
problem Minimizing Bayesian regret in offline linear bandits.
method Proposes a new algorithm that directly minimizes upper bounds on Bayesian regret using conic optimization.
result Upper bounds are tight and guarantee superior performance compared to LCB.
This paper addresses robust CBs for linear SEMs with model fluctuations.
problem Designing interventions in causal systems with linear SEMs that are robust to model fluctuations.
method Develops a robust CB algorithm and analyzes its regret under model deviation.
result The proposed algorithm achieves nearly optimal i l d e O ( T ) ilde{\mathcal{O}}(\sqrt{T}) i l d e O ( T ) regret when C C C is o ( T ) o(\sqrt{T}) o ( T ) and maintains sub-linear regret for a broader range of C C C . An algorithm tackles low-rank linear bandit problems with improved regret bounds.
problem Low-rank linear bandit problems where rewards are inner products with an unknown low-rank matrix.
method Combines online-to-confidence-set conversion and exponentially weighted average forecaster with a covering of low-rank matrices.
result Achieves O ~ ( ( d 1 + d 2 ) 3 / 2 r T ) \widetilde{O}((d_1+d_2)^{3/2}\sqrt{rT}) O (( d 1 + d 2 ) 3/2 r T ) regret, improving over standard bounds when r ≪ min { d 1 , d 2 } r \ll \min\{d_1,d_2\} r ≪ min { d 1 , d 2 } . We study optimal regret bounds for control in linear dynamical systems under adversarially changing strongly convex cost functions, given the knowledge of transition dynamics. This includes several well studied and fundamental frameworks such as the Kalman filter and the linear quadratic regulator. State of the art met…
New bounds show polyhedral surrogates are optimal for generalization.
problem Proving generalization rates for polyhedral loss functions.
method Developed two general results for polyhedral surrogates.
result Polyhedral surrogates provide linear surrogate regret bounds, translating directly to target rates.
Study online control of unknown time-varying systems with negative and positive results.
problem Online control of time-varying systems with unknown dynamics.
method Algorithmic upper bounds and lower bounds for different policy classes.
result Sublinear adaptive regret bounds for Disturbance Response policies.
New algorithm learns LQR with O ( T ) O(\sqrt{T}) O ( T ) regret using Langevin dynamics and excitation.
problem Learning LQR with a O ( T ) O(\sqrt{T}) O ( T ) regret bound. method Thompson sampling with Langevin dynamics and excitation mechanism.
result Achieved O ( T ) O(\sqrt{T}) O ( T ) regret bound for LQR learning. New method for semiparametric bandits reduces regret to optimal levels.
problem Complex reward structures in semiparametric bandits.
method Experimental-design approach with sharp regret bound and PAC bound.
result Minimax regret of i l d e O ( d T ) ilde{O}(\sqrt{dT}) i l d e O ( d T ) and logarithmic regret under positive suboptimality gap. New RL algorithm tackles nonstationary MDPs with linear approximations and varying rewards.
problem Nonstationary reinforcement learning with evolving reward and state transition functions.
method Developed a new algorithm LSVI-UCB-Restart with periodic restart, and parameter-free Ada-LSVI-UCB-Restart for unknown variation budgets.
result First minimax dynamic regret lower bound for nonstationary linear MDPs and linear MDPs lower bound.
Linear contextual bandit is an important class of sequential decision making problems with a wide range of applications to recommender systems, online advertising, healthcare, and many other machine learning related tasks. While there is a lot of prior research, tight regret bounds of linear contextual bandit with infi…
New algorithm reduces regret for linear bandits with unknown noise variance.
problem Finding optimal actions in linear bandits with varying noise variance.
method Adaptive algorithm with Freedman-type concentration inequality and multi-layer structure.
result Achieves i l d e O ( d ∑ k = 1 K σ k 2 + d ) ilde{O}(d \sqrt{\sum_{k = 1}^K σ_k^2} + d) i l d e O ( d ∑ k = 1 K σ k 2 + d ) regret for linear bandits. We consider adaptive control of the Linear Quadratic Regulator (LQR), where an unknown linear system is controlled subject to quadratic costs. Leveraging recent developments in the estimation of linear systems and in robust controller synthesis, we present the first provably polynomial time algorithm that provides high…
Improved privacy in RL with near-optimal regret bounds.
problem Privacy-preserving reinforcement learning in personalized decision-making systems.
method Differentially private algorithm based on LSVI-UCB++ with privacy-preserving techniques.
result Achieved a near-optimal regret bound of O(d * sqrt(H^3 * K) + H^(15/4) * d^(7/6) * K^(1/2) / ε).
We consider the setting of online linear regression for arbitrary deterministic sequences, with the square loss. We are interested in the aim set by Bartlett et al. (2015): obtain regret bounds that hold uniformly over all competitor vectors. When the feature sequence is known at the beginning of the game, they provide…
The paper minimizes Borda regret in dueling bandits models.
problem Minimizing Borda regret in dueling bandits models.
method Proposes explore-then-commit and EXP3-type algorithms for stochastic and adversarial settings respectively.
result Achieves nearly matching regret upper bounds of O ( d 2 / 3 T 2 / 3 ) O(d^{2/3} T^{2/3}) O ( d 2/3 T 2/3 ) for both settings. LinMED is a new linear bandit algorithm with near-optimal regret bound.
problem Optimizing decision-making in linear bandit problems with sub-Gaussian distributions.
method LinMED is a randomized linear bandit algorithm with closed-form arm sampling probabilities.
result LinMED achieves a near-optimal regret bound of d n d\sqrt{n} d n up to logarithmic factors.