New method improves on existing algorithms for rank-one bandits.
problem Minimizing regret in stochastic rank-one bandits.
method Unimodal Thompson Sampling (UTS) with new analysis.
result UTS provides an asymptotically optimal regret bound.
On-device research index
arXiv research
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.
169,341 papers · 148 categories
Trend · papers per month
48 results for “rank-$1$ bandit”
Efficient Low-Rank Matrix Estimation, Experimental Design, and Arm-Set-Dependent Low-Rank Banditsstat.ML
Novel method for efficient low-rank matrix estimation and bandit algorithms.
problem Low-rank matrix estimation and bandit problems.
method LowPopArt method for low-rank matrix estimation and novel experimental design criterion.
result Improved recovery guarantees and regret bounds for low-rank bandit algorithms.
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 regret, improving over standard bounds when .
New algorithm tackles bilinear bandit problem with low-rank structure.
problem Finding the optimal action in a bilinear bandit problem with low-rank reward matrix.
method Two-stage algorithm: subspace exploration followed by linear bandit refinement.
result Regret bound of ESTR is .
Paper introduces G-LowTESTR for efficient tensor bandits.
problem Efficient decision-making in multi-dimensional data with non-linear reward functions.
method Generalized low-rank tensor contextual bandits model and G-LowTESTR algorithm.
result G-LowTESTR achieves superior regret bound compared to vectorization and matricization methods.
Study ranking in generalized linear bandits with position and item dependencies.
problem Complex reward function due to position and item dependencies in recommendation systems.
method Model position and item dependencies, design UCB and Thompson Sampling algorithms.
result Generalizes existing studies in position dependencies and graph theory.
Develops TOFU for tensor bandits with low-rank structure.
problem Linear bandit models fail to capture high-dimensional, low-rank tensor structures.
method Develops TOFU, a tensor bandit algorithm that estimates low-dimensional subspaces and uses norm constraints.
result Improves regret bound by a multiplicative factor that grows exponentially in system order.
New algorithm catches moving subspaces in bandit problems.
problem Adapt to changing low-dimensional latent subspaces in bandit settings.
method Piecewise-stationary low-rank linear contextual bandits with CUSUM-style boundary detection.
result Achieves intrinsic rank dynamic regret rate of .
Introduces tensor bandits for multi-dimensional online decision making.
problem Optimal decision making in multi-dimensional online scenarios.
method Stochastic low-rank tensor bandits, tensor elimination, tensor epoch-greedy, tensor ensemble sampling.
result Tensor elimination and tensor epoch-greedy algorithms outperform existing methods.
The paper tackles pure exploration in multi-armed bandits with low rank structure using oblivious sampling.
problem Pure exploration in multi-armed bandits with low rank reward sequences.
method The approach involves separating the exploration strategy from feedback, using oblivious sampling, and incorporating kernel information of reward vectors.
result Efficient algorithms with regret bound for both time-varying and fixed cases, with a lower bound gap of .
Unified approach tackles high-dimensional tensor bandits with convex optimization and weakly decomposable regularizers.
problem Challenges in high-dimensional generalized tensor bandits where existing algorithms fail.
method Proposes a generalized linear tensor bandits algorithm with a unified analytical framework using convex optimization and weakly decomposable regularizers.
result Unified analytical framework provides better bounds and broader applicability compared to existing methods.
Formulates a Dueling Bandits problem for eliciting Kemeny rankings.
problem Eliciting preferences to find a Kemeny ranking.
method Formulates the problem as a Dueling Bandits problem, considering sampling with and without replacement.
result Approximation bounds and algorithms for finding PAC solutions with sample complexity.
New algorithm for fair ranking in contextual bandits with concave rewards.
problem Fair ranking in recommendation systems.
method Geometric interpretation of CBCR as optimization, Frank-Wolfe analyses.
result First algorithm with provably vanishing regret for CBCR.
New method for dynamic pricing with many products using low-rank demand structure.
problem Maximizing revenue in dynamic pricing with many products and evolving demand.
method Online bandit convex optimization with side information from observed demands, using low-rank structure of demand model.
result Revenue maximization approaches that of the best fixed price vector in hindsight, with rate dependent on demand model rank.
New ranking algorithms improve online content delivery by learning from click data.
problem Bias in ranking systems due to production system biases.
method Proposed novel extensions of LinUCB and Linear Thompson Sampling algorithms to handle position-based click model.
result Validated the proposed algorithms through offline and online experiments.
Paper tackles online ranking and diversification in recommender systems.
problem Maximizing relevance and diversity in ranked lists for online recommendation.
method CascadeHybrid approach that combines contextual bandits for relevance and topical diversity.
result CascadeHybrid outperforms baselines in real-world datasets.
Efficient algorithms for low-rank bandits using subspace recovery.
problem Contextual bandits with low-rank reward matrices.
method Spectral methods for subspace recovery, reformulating as linear bandits.
result Nearly optimal policy evaluation and best policy identification, minimax guarantees for regret minimization.
Optimizes matching in weighted graphs with semi-bandit sampling.
problem Finding optimal pairings in weighted graphs with sequential sampling.
method Leverages rank-1 assumption on adjacency matrix to reduce sample complexity and regret.
result Achieves linear dependency in the number of vertices for sample complexity and regret.
Paper presents a reduction-based framework for conservative bandits and RL with improved lower and upper bounds.
problem Conservative bandits and reinforcement learning problems.
method Reduction technique to calculate necessary and sufficient budget from baseline policy.
result Improved lower and upper bounds for various conservative settings.
Paper tackles adaptive sampling for identifying largest gaps between distributions.
problem Adaptive sampling from K distributions to identify the largest gap between any two adjacent means.
method Proposes elimination and UCB-style algorithms, showing minimax optimality.
result UCB-style algorithms require 6-8x fewer samples than non-adaptive sampling.
Study multi-task learning with low-rank representation in stochastic linear bandits.
problem Transfer learning across multiple linear bandit tasks with shared low-dimensional representation.
method Proposes a greedy policy with trace norm regularization to implicitly learn a low-rank representation without knowing the rank.
result Upper bound on multi-task regret of , showing benefit over independent task solving.
Algorithm for low-rank matrix bandits with heavy-tailed rewards, achieving nearly optimal regret bound.
problem Stochastic low-rank matrix bandit with heavy-tailed rewards.
method LOTUS algorithm using truncation and dynamic exploration.
result Regret bound of order $ ilde O(d^ rac{3}{2}r^ rac{1}{2}T^ rac{1}{1+δ}/ ilde{D}_{rr})$ without knowing .
A new bandit algorithm finds the max entry of a rank-1 matrix efficiently.
problem Online learning with unobserved values in matrix products.
method Rank1Elim algorithm for stochastic rank-1 bandits.
result Rank1Elim achieves linear regret bound in , , and .
New algorithm tackles dynamic query routing to multiple embedding models.
problem Dynamic query routing to multiple embedding models under adversarial conditions.
method Formalized as adversarial contextual linear bandit with low-rank experts, proposed HPG algorithm.
result HPG algorithm achieves linearized policy regret of .
Optimizes ranking from click feedback in a bandit setting.
problem Learning to rank from Bernoulli click feedback in a bandit setting.
method Variance-aware confidence sets derived from Bernstein and Chernoff bounds for optimal algorithms.
result Optimal algorithms for the case of small mean rewards, improving on previous suboptimal results.
Solves a new bandit problem with duels and pulls for crowdsourcing.
problem Finding the best arms with mean rewards above a threshold.
method Alternates between ranking and binary search to solve TBP-DC.
result Proves optimality of the Rank-Search algorithm.
Algorithm reduces high-dimensional SLB regret by exploiting hidden low-rank structure.
problem High-dimensional stochastic linear bandits with hidden low-rank structure.
method Projective Stochastic Linear Bandit (PSLB) using PCA projection.
result PSLB achieves tighter regret bound and faster convergence.
New algorithms minimize regret in multi-task and lifelong linear bandits with shared representation.
problem Minimizing regret in multi-task and lifelong linear bandits with shared representation.
method Novel algorithms using efficient estimator for low-rank linear feature extractor and novel analysis.
result Achieved regret bounds matching minimax lower bound up to logarithmic factors.
New framework improves efficiency in low-rank matrix bandit problems.
problem Stochastic contextual low-rank matrix bandit problem with unknown rank matrices.
method G-ESTT and G-ESTS frameworks using Stein's method and regularization.
result Achieved improved regret bounds for low-rank matrix bandit problems.
Optimizes algorithms for non-concave bandit problems.
problem Optimizing algorithms for non-concave bandit problems.
method Unified zeroth-order optimization paradigm.
result Minimax-optimal algorithms in the dimension for low-rank generalized linear bandit problems.
New algorithms minimize regret in combinatorial online learning with relative feedback.
problem Minimizing regret in online learning with subset-wise relative preference feedback.
method Instance-dependent and order-optimal regret algorithms for two settings: bounded size subsets and fixed size subsets.
result Regret bounds of and for respective settings.
Study online ranking in non-stationary environments with abrupt preference changes.
problem Online learning to rank in a non-stationary cascade model where user preferences change abruptly.
method Cascading non-stationary bandits, proposing CascadeDUCB and CascadeSWUCB algorithms.
result Upper and lower bounds on regret for cascading non-stationary bandits algorithms.
BubbleRank improves online search results using safe exploration.
problem Learning user preferences from scratch in online ranking is costly and risky.
method BubbleRank combines offline and online learning, starting with an initial base list and improving it online by exchanging items.
result BubbleRank achieves a graceful degradation of n-step regret with a good initial base list.
New algorithm achieves near-optimal performance in dueling bandit problem.
problem Optimizing decision-making in dueling bandit problems with limited adaptive rounds.
method Developed a batched algorithm that matches the asymptotic regret bounds of sequential algorithms under the Condorcet condition.
result Asymptotic regret of in rounds.
Factored Banditscs.LG
Factored bandits model learns with limited feedback using decomposable actions.
problem Limited feedback learning with decomposable actions.
method Introduces factored bandits model, provides anytime algorithm, and matching upper and lower bounds.
result Improves regret bounds for utility-based dueling bandits.
Unified framework for high-dimensional bandit problems with low-dimensional structures.
problem Stochastic high-dimensional bandit problems with low-dimensional structures.
method Proposed a simple unified algorithm and a general analysis framework for the regret upper bound.
result Unified algorithm achieves comparable regret bounds in various high-dimensional bandit problems.
Proposes a new algorithm for click feedback in search results.
problem Learning to predict user clicks based on relevance and position.
method Developed a Bernoulli rank- bandit learning problem and proposed Rank1ElimKL to improve performance.
result Rank1ElimKL outperforms Rank1Elim in various scenarios, including real-world data.
New algorithm improves learning efficiency in multi-task contextual bandits.
problem Improving learning efficiency in multi-task contextual bandits.
method Alternating projected gradient descent (GD) and minimization estimator for low-rank feature matrix recovery.
result Proved regret bound for multi-task learning algorithm.
A new framework for structured bandits using influence diagrams and variational Thompson sampling.
problem Complex statistical dependencies in structured bandit problems.
method Influence diagram framework, variational Thompson sampling, tracking structured posterior distribution.
result Empirically evaluated algorithms perform as well as or better than existing baselines.
First online learning to rank algorithm for broad click models.
problem Online learning to rank in stochastic click models.
method BatchRank, an algorithm for a broad class of click models.
result Derives a gap-dependent upper bound on the -step regret of BatchRank.
New spectral methods improve matrix estimation in RL with low-rank structure.
problem Estimating matrices with low-rank structure in reinforcement learning.
method Spectral-based matrix estimation approaches.
result Spectral methods efficiently recover singular subspaces and minimize entry-wise error.
PAC Battling-Bandit tackles online learning with subset choice and Plackett-Luce feedback.
problem Identify near-best items in a PL model with subset choice and stochastic feedback.
method Introduces PAC Battling-Bandit problem, studies various feedback models, proposes algorithms with optimal sample complexity.
result Sample complexity is $O\left( \frac{n}{ε^2} \ln \frac{1}δ
ight)$ for WI feedback, for TR feedback.
ACP-UCB1 ranks arms based on upper-tail performance, improving stochastic bandit algorithms.
problem Stochastic bandit algorithms often favor arms with strong upper-tail performance, which is not well-addressed by classical mean-reward criteria.
method ACP-UCB1 combines an adaptive conformal estimate of the upper endpoint with a UCB-type optimism bonus.
result ACP-UCB1 achieves logarithmic upper-quantile regret with per-arm contribution \(O(
icefrac{\log n}{Δ_j^{\mathrm{ACP}}})\).
Optimizes COVID-19 testing policy using a Multi-Armed Bandit approach.
problem Balancing discovery of positive cases with population surveillance.
method Risk scoring and random sampling based on Multi-Armed Bandit theory.
result Effective prioritization captures 65-92% of positive cases with varying testing capacity.
Doubly High-Dimensional Contextual Bandits: An Interpretable Model for Joint Assortment-Pricingstat.ML
Jointly tackles assortment and pricing in retail, using bandit models.
problem Maximizing revenue or profit in retail through optimal assortment and pricing.
method Contextual bandits with a flexible, interpretable model for high-dimensional contexts and actions.
result Proves lower regret compared to state-of-the-art methods in various bandit and pricing models.
Meta-algorithm optimizes nonstochastic bandits with infinitely many experts.
problem Maximizing reward by choosing actions sequentially from a set of experts.
method Proposed a variant of Exp4.P for infinitely many experts and a meta-algorithm.
result Proved high-probability upper bound of on regret.
Paper introduces Decentralized Non-stationary Competing Bandits ( exttt{DNCB}) for dynamic matching markets.
problem Understanding dynamic two-sided matching markets with competing agents.
method Proposes a decentralized asynchronous learning algorithm ( exttt{DNCB}) for non-stationary environments.
result Obtains sub-linear (logarithmic) regret of exttt{DNCB} in dynamic settings.
An algorithm finds the maximum entry of a stochastic low-rank matrix from noisy observations.
problem Finding the maximum entry of a stochastic low-rank matrix from sequential observations.
method LowRankElim algorithm, which is a statistical approach to find the maximum entry of a non-negative matrix.
result An upper bound on the regret of $O((K + L) \poly(d) Δ^{-1} \log n)$, where and are the number of rows and columns, is the rank of the matrix, and is the minimum gap.