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.
Transforms offline algorithms to online with low regret in random order model.
problem Developing online algorithms with low approximate regret from offline approximation algorithms.
method General reduction theorem and coreset construction method.
result Achieves polylogarithmic ε-approximate regret for various online problems.
New reinforcement learning algorithm achieves instance-optimal sample complexity.
problem Achieving low regret and identifying optimal policies in reinforcement learning.
method A novel planning-based algorithm that explicitly accounts for state visitation distributions.
result The proposed algorithm attains nearly minimax optimal sample complexity, improving over worst-case bounds.
New method for online low-rank matrix completion with improved regret.
problem Designing an efficient algorithm for online recommendation systems with low regret.
method Explore-then-commit (ETC) approach and iterative user clustering (OCTAL) for rank-1 setting.
result Nearly optimal regret bounds for online low-rank matrix completion.
Algorithm POLO learns low-rank MDPs with adversarial changes in full-info feedback.
problem Learning low-rank MDPs with adversarial changes and unknown transition probabilities.
method Policy optimization-based algorithm POLO with regret guarantee.
result POLO achieves sublinear regret guarantee with no dependence on state space size.
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 } . Agents collaborate to reduce regret in a multi-agent linear bandit problem with side information.
problem Reducing regret in a multi-agent stochastic linear bandit with side information.
method A decentralized algorithm where agents communicate subspace indices and each plays a projected LinUCB on the corresponding low-dimensional subspace.
result Per-agent finite-time regret is much smaller when agents communicate compared to non-communicating case.
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.
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 i l d e O ( s M T ) ilde{\mathcal O}(s\sqrt{M T}) i l d e O ( s M T ) . Proposes MRO to achieve uniformly low regret in distributionally robust learning.
problem Learning under unknown test distributions (distribution shift).
method Minimax Regret Optimization (MRO) for robust machine learning.
result MRO achieves uniformly low regret across all test distributions.
RL-LOW algorithm achieves exponential simple regret in offline RLHF with pairwise comparisons.
problem Offline reinforcement learning from human feedback with pairwise comparisons.
method Proposes RL-LOW algorithm to minimize simple regret with exponential convergence.
result Achieves an exponential form of simple regret of \(\exp ( - Ω(n/H) )\).
Paper presents an efficient algorithm for linear MDP with low switching cost.
problem Large state space reinforcement learning problems with low switching cost.
method First algorithm for linear MDP with low switching cost, achieving near-optimal regret and switching cost.
result Regret bound of $\widetilde{O}\left(\sqrt{d^3H^4K}
ight)$ and near-optimal switching cost of $O\left(d H\log K
ight)$ .
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 T T T . 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. Paper proposes FedQ-Advantage for federated Q-learning with near-optimal regret and low communication cost.
problem Near-optimal federated Q-learning with low communication cost.
method Reference-advantage decomposition for variance reduction, synchronization between agents and server, policy update.
result Achieves almost optimal regret and near-linear regret speedup compared to single-agent learning.
In this paper, we consider the problem of online learning of Markov decision processes (MDPs) with very large state spaces. Under the assumptions of realizable function approximation and low Bellman ranks, we develop an online learning algorithm that learns the optimal value function while at the same time achieving ve…
Federated Q-Learning achieves linear regret speedup with low communication cost.
problem Achieving linear regret speedup in federated reinforcement learning without high communication costs.
method Proposed two federated Q-Learning algorithms: FedQ-Hoeffding and FedQ-Bernstein, using event-triggered synchronization, novel step size selection, and concentration inequalities.
result Total regrets achieve linear speedup compared to single-agent counterparts with logarithmic communication cost.
Efficient binary sampling method for global optimization of univariate functions with low regret.
problem Global optimization of univariate loss functions.
method Binary sampling approach to circumvent hard-to-determine query points in traditional methods.
result At most L log ( 3 T ) L\log (3T) L log ( 3 T ) and 2.25 H 2.25H 2.25 H regret for L L L -Lipschitz continuous and H H H -Lipschitz smooth functions respectively. Study shows how competition affects learning in matching markets, proving it's possible to balance stability, fairness, and regret.
problem How competition affects learning in matching markets and the impossibility of simultaneously guaranteeing stability and low optimal regret.
method Modeling a two-sided matching market with bandit learners and adding components of costs and transfers.
result It is possible to simultaneously guarantee stability, low optimal regret, fairness in the distribution of regret, and high social welfare.
Paper tackles robust knowledge transfer in parallel RL tasks.
problem Transfer knowledge from low-tier to high-tier tasks in parallel RL without shared dynamics or reward functions.
method Identifies Optimal Value Dominance condition and proposes online learning algorithms for both tasks.
result Achieves constant regret on partial states and near-optimal regret when tasks are dissimilar.
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.
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 O ( d ( ln N ) / n ) O(d\sqrt{(\ln N)/n}) O ( d ( ln N ) / n ) for both time-varying and fixed cases, with a lower bound gap of O ( ln N ) O(\sqrt{\ln N}) O ( ln N ) . Study symmetric linear bandits with hidden symmetry, achieving improved regret bounds.
problem High-dimensional linear bandits with hidden symmetry.
method Model selection within low-dimensional subspaces to learn hidden symmetry.
result Achieved improved regret bounds of O ( d 0 2 / 3 T 2 / 3 log ( d ) ) O(d_0^{2/3} T^{2/3} \log(d)) O ( d 0 2/3 T 2/3 log ( d )) and O ( d 0 T log ( d ) ) O(d_0\sqrt{T\log(d)} ) O ( d 0 T log ( d ) ) . 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 N d T ( T + d ) r \sqrt{NdT(T+d)r} N d T ( T + d ) r , showing benefit over independent task solving. We introduce the bilinear bandit problem with low-rank structure in which an action takes the form of a pair of arms from two different entity types, and the reward is a bilinear function of the known feature vectors of the arms. The unknown in the problem is a d 1 d_1 d 1 by d 2 d_2 d 2 matrix Θ ∗ \mathbfΘ^* Θ ∗ that defines the reward…
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 O ( r T ) O(r\sqrt{T}) O ( r T ) . The paper tackles robust policy learning from multiple data sources.
problem Learning a policy that generalizes across diverse settings from multiple heterogeneous data sources.
method Proposes a minimax regret optimization objective and a policy learning algorithm combining doubly robust offline policy evaluation and no-regret learning.
result Achieves minimal worst-case mixture regret up to a moderated vanishing rate of the total data across all sources.
Paper finds algorithms with both low regret and high exploitation.
problem Finding algorithms with both low regret and high exploitation.
method Investigates online learning algorithms with bandit feedback.
result First affirmative answer to guaranteeing both O ( 1 ) O(1) O ( 1 ) regret and i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) regret. In this paper, we propose and study opportunistic bandits - a new variant of bandits where the regret of pulling a suboptimal arm varies under different environmental conditions, such as network load or produce price. When the load/price is low, so is the cost/regret of pulling a suboptimal arm (e.g., trying a suboptim…
New algorithm reduces individual regret and communication costs in cooperative bandits.
problem Optimal individual and group regret in cooperative multi-agent bandits.
method Integrates a new communication policy into a learning algorithm.
result Achieves optimal individual regret and constant communication costs.
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.
This thesis analyzes MACL systems with low-regret learning algorithms for sequential decision making.
problem Designing efficient learning algorithms for multi-agent cooperative systems to minimize regret.
method Analyzes and develops algorithms for cooperative multi-agent multi-armed bandit problems and online convex optimization in distributed settings.
result Presented regret lower bounds and efficient algorithms for achieving these bounds, providing guidance on communication protocols.
TOFU-POV tackles partially observed linear bandits, achieving sublinear regret with low-dimensional action vectors.
problem Stochastic linear bandits with partially observed actions in settings like recommendation and healthcare.
method TOFU-POV estimates latent action subspace, imputes missing actions, and runs OFUL in low-dimensional coordinates.
result TOFU-POV achieves T \sqrt{T} T regret scaling with intrinsic subspace dimension, improving upon natural baselines. New RL algorithm reduces policy switching cost to loglog(T) with similar regret.
problem Low policy switching cost in real-life RL applications.
method Stage-wise exploration and adaptive policy elimination.
result Regret of O ( H S A log log T ) O(HSA \log\log T) O ( H S A log log T ) with O ( H S A log log T ) O(HSA \log\log T) O ( H S A log log T ) switching cost. New algorithm reduces regret from sqrt(T) to polylog(T) in stochastic contextual linear bandits.
problem Achieving logarithmic regret in stochastic contextual linear bandits.
method Low Regret Stochastic Contextual Bandits ( exttt{LR-SCB}) algorithm, exploiting stochastic contexts and parameter estimation.
result Logarithmic regret (polylog(T)) achieved, improving over sqrt(T) lower bound.
New RL algorithms reduce costs for single-agent and federated learning.
problem Minimizing costs in RL and federated RL settings.
method Q-EarlySettled-LowCost and FedQ-EarlySettled-LowCost algorithms.
result First algorithms to achieve low burn-in and logarithmic switching costs.
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.
This paper analyzes data-driven Newsvendor problems and finds a wide range of possible regrets.
problem Guessing the number drawn from an unknown distribution with asymmetric costs.
method Unified analysis using the notion of clustered distributions and new lower bounds.
result The entire spectrum of achievable regrets from 1 / n 1/\sqrt{n} 1/ n to 1 / n 1/n 1/ n is possible. Algorithm achieves comparable performance to fully dynamic data with only a few batches.
problem High-dimensional multi-armed contextual bandits with batched feedback.
method Provable sample-efficient algorithm using batch allocation method.
result Achieves regret bounds comparable to fully sequential setting with only L = O(log T) batches.
Study online learning in MDPs with aggregate bandit feedback, achieving low regret in both stochastic and adversarial settings.
problem Online learning in finite-horizon episodic MDPs with aggregate bandit feedback.
method Best-of-both-worlds (BOBW) algorithms using FTRL over occupancy measures, self-bounding techniques, and new loss estimators.
result First BOBW algorithms for episodic tabular MDPs with aggregate bandit feedback achieving O ( log T ) O(\log T) O ( log T ) regret in stochastic and O ( T ) {O}(\sqrt{T}) O ( T ) regret in adversarial settings. 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.
Methods for learning to search for structured prediction typically imitate a reference policy, with existing theoretical guarantees demonstrating low regret compared to that reference. This is unsatisfactory in many applications where the reference policy is suboptimal and the goal of learning is to improve upon it. Ca…
New method constructs confidence sets for GLMs via game theory.
problem Developing reliable confidence intervals for GLM parameters.
method Reduction to sequential prediction games with low regret.
result Online-to-confidence-set conversions provide new types of intervals.
A new algorithm learns optimal personalized treatment plans online with low regret.
problem Learning optimal dynamic treatment regimes in an online setting.
method Developed a novel algorithm balancing exploration and exploitation for rate-optimal regret.
result Guaranteed rate-optimal regret for linear transition and reward models.
New algorithm reduces online learning regret for bounded recall games.
problem Reducing regret in online learning with limited past information.
method Constructing a stationary bounded-recall algorithm with O ( 1 / M ) O(1/\sqrt{M}) O ( 1/ M ) regret. result Any low regret bounded-recall algorithm must be aware of past losses' order.
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.
A method to minimize regret in multi-agent control systems with adversarial disturbances.
problem Optimal control of dynamical systems with adversarial disturbances and multiple agents.
method Reduction from online convex optimization to a distributed algorithm for multi-agent control.
result The resulting distributed algorithm has low regret relative to the optimal precomputed joint policy.
The paper tackles lifelong learning in multi-armed bandits, aiming to minimize average regret over multiple tasks.
problem Minimizing average regret in multi-armed bandits over multiple tasks.
method Confidence interval tuning of UCB algorithms and greedy algorithms applied to a bandit over bandit approach.
result Empirical improvement over previous work in the mortal bandit problem.