Paper addresses regret minimization and inference in high-dimensional online decision-making.
problem Regret minimization and statistical inference in high-dimensional online decision-making.
method Integrates ε-greedy bandit algorithm with hard thresholding for sparse bandit parameters and debiasing method for inference.
result Achieves either O ( T 1 / 2 ) O(T^{1/2}) O ( T 1/2 ) regret or O ( T 1 / 2 ) O(T^{1/2}) O ( T 1/2 ) -consistent inference, with trade-off between exploration and exploitation. New algorithm reduces online decision-making regret with efficient LP re-solving and parallel first-order method.
problem Worse regret guarantees and high computational cost of LP-based OLP algorithms.
method Combines LP-based and first-order OLP methods, re-solving LP subproblems periodically and using parallel first-order method.
result Achieves O ( log ( T / f ) + f ) \mathscr{O}(\log (T/f) + \sqrt{f}) O ( log ( T / f ) + f ) regret, balancing computational efficiency and superior regret guarantee. Study shows how AI model can improve decision-making with missing data.
problem Sequential decision-making with missing covariates.
method Introduced model elasticity to quantify imputation discrepancy; used statistical learning and regression for calibration.
result Calibrating pre-trained models can significantly reduce regret in decision-making.
As a metric to measure the performance of an online method, dynamic regret with switching cost has drawn much attention for online decision making problems. Although the sublinear regret has been provided in many previous researches, we still have little knowledge about the relation between the dynamic regret and the s…
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.
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 ) . Data-driven model selection reduces regret in sequential decisions.
problem Optimizing model selection in stochastic environments with bandit feedback.
method Data-driven regret balancing for model selection.
result Meta-learner selects the best base learner based on actual realized regret.
New complexity measure for interactive learning reduces regret to near-optimal levels.
problem Challenges in sample-efficient, adaptive learning algorithms for interactive decision making.
method Introduces the Decision-Estimation Coefficient and the Estimation-to-Decisions (E2D) principle.
result Unified algorithm design principle E2D achieves optimal sample-efficient learning.
ERTS uses Thompson sampling for Gaussian entropic risk bandits, achieving regret bounds.
problem Risk in decision making complicates reward maximization in MAB problems.
method ERTS (Entropic Risk Thompson Sampling) using Thompson sampling with an entropic risk measure.
result Regret bounds for ERTS under entropic risk measure provided.
Universal algorithm learns unknown distribution for various decision-making problems.
problem Various statistical measures in contextual sequential decision-making.
method Infinite-dimensional functional regression oracle for cumulative distribution functions.
result Utility regret rate bounded by polynomial decay of eigenvalue sequence.
Improved model-free reinforcement learning with decision-estimation coefficient.
problem Interactive decision making, including structured bandits and reinforcement learning.
method Combining Estimation-to-Decisions with optimistic estimation to achieve better regret bounds.
result Regret bounds for model-free reinforcement learning with value function approximation.
New framework tackles stochastic latent subgroup heterogeneity in online decision-making.
problem Stochastic latent heterogeneity in online decision-making where individual responses vary with unobserved subgroups.
method Latent heterogeneous bandit framework using EM-greedy algorithm to learn subgroup probabilities and reward parameters.
result Achieves optimal estimation and classification guarantees, revealing a fundamental stochastic barrier in online decision-making.
Algorithm reduces decision-making errors in multi-agent bandit problems.
problem Minimizing decision errors in multi-agent multi-armed bandit problems.
method RBO-Coop-UCB algorithm with Bayesian change point detection.
result Expected group regret is upper bounded by O ( K N M log T + K M T log T ) \mathcal{O}(KNM\log T + K\sqrt{MT\log T}) O ( K N M log T + K M T log T ) . IDS algorithm optimizes sequential decisions in various monitoring settings.
problem Optimizing sequential decisions in complex monitoring scenarios.
method Information-directed sampling (IDS) algorithm for linear partial monitoring.
result IDS achieves nearly worst-case rate optimality in finite-action games.
The study quantifies decision-making risks from suboptimal classifiers and proposes methods to reduce these risks.
problem Excess risk in decision-making from suboptimal probabilistic classifiers.
method Analytical expressions and upper/lower bounds for excess risk, calibration curve estimation, grouping loss estimator.
result Identifies regimes where recalibration alone or post-training is more effective.
The paper shows optimal robustness against adversarial corruption in sequential decision-making problems.
problem Optimal robustness to adversarial corruption in online decision-making problems.
method Investigates prediction with expert advice and multi-armed bandit problems, focusing on algorithms with decreasing learning rates and second-order regret bounds.
result Optimal robustness can be expressed by a square-root dependency on the amount of corruption, achieving O ( log N Δ + C log N Δ ) O(\frac{\log N}{\Delta} + \sqrt{\frac{C \log N}{\Delta}}) O ( Δ l o g N + Δ C l o g N ) -regret. The paper tackles fair sequential decision making with biased linear bandit feedback.
problem Fair sequential decision making with biased linear bandit feedback.
method Phased elimination algorithm to correct unfair evaluations, establishing upper bounds on regret.
result The worst-case regret is smaller than O ( κ ∗ 1 / 3 log ( T ) 1 / 3 T 2 / 3 ) \mathcal{O}(κ_*^{1/3}\log(T)^{1/3}T^{2/3}) O ( κ ∗ 1/3 log ( T ) 1/3 T 2/3 ) . New algorithms handle missing outcomes in MAB, reducing regret.
problem Missing outcomes in real-world MAB scenarios lead to biased estimates and linear regret.
method Introduced algorithms for MAR and MNAR missingness mechanisms in MAB.
result Significant improvements in decision-making by accounting for missingness.
Paper tackles non-monotonic resource utilization in sequential decision-making.
problem Sequential decision-making under uncertainty with resource constraints.
method Introduces a new MDP policy with constant regret against LP relaxation.
result Develops a learning algorithm with logarithmic regret for unknown outcome distributions.
The paper provides a method to minimize regret in estimate-then-optimize decision-making.
problem Errors in estimation lead to sub-optimal decisions in data-driven decision-making.
method A novel bound on regret for smooth and unconstrained optimization problems, followed by experimental design to minimize this regret.
result A general procedure for experimental design to minimize regret resulting from estimate-then-optimize.
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 i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) policy regret for fixed problem parameters, with explicit dependence on horizon, adversary memory, confidence radius, and aggregate Eluder dimension. This paper analyzes the multi-armed bandit model using path-integral methods.
problem Understanding the stochastic dynamics and optimal strategies in multi-armed bandit problems.
method Path-integral analysis of statistical physics.
result Emergence of multimodal regret distribution with large regrets from exploitation of sub-optimal arms.
Improved ExO method achieves near-optimal bounds in both stochastic and adversarial settings.
problem Finding optimal exploration strategies in online decision-making with limited feedback.
method Exploration by Optimization with hybrid regularizers for locally observable games.
result Achieved nearly optimal bounds of O ( ∑ a e q a ∗ k 2 m 2 log T / Δ a ) O(\sum_{a
eq a^*} k^2 m^2 \log T / Δ_a) O ( ∑ a e q a ∗ k 2 m 2 log T / Δ a ) in stochastic and adversarial environments. 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) / ε).
New algorithm reduces regret in noisy context bandits.
problem Online decision-making with noisy context predictions.
method Extends classical statistics measurement error model to online decision-making.
result Achieves sublinear regret guarantees under mild conditions.
New algorithm reduces dynamic regret by adapting to comparator complexity.
problem Nonstationary sequential decision making with unbounded domains.
method Sparse coding framework to adapt to comparator complexity.
result Improves dynamic regret bounds by adapting to comparator energy and sparsity.
A new algorithm reduces communication costs for collaborative decision-making across clients.
problem Collaborative decision-making with sparse rewards and heterogeneous contexts.
method Federated Lasso algorithm for sparse linear contextual bandits.
result Achieves near-optimal regret with logarithmic communication costs.
New bounds show complexity of adversarial decision making.
problem Understanding sample efficiency in adversarial decision making.
method New upper and lower bounds on Decision-Estimation Coefficient.
result Decision-Estimation Coefficient is necessary and sufficient for low regret in adversarial decision making.
This review examines bandit problems in AI using statistical methods.
problem Sequential decision-making under uncertainty in AI environments.
method Foundational models, concentration inequalities, minimax regret bounds, frequentist and Bayesian algorithms, K-armed contextual bandits, SCAB, functional data analysis.
result Exploration-exploitation trade-offs and regret analyses in various bandit problems.
A new UCB algorithm for heavy-tailed bandits with near-optimal regret.
problem Sequential decision making in uncertain environments with heavy-tailed rewards.
method Data-driven, distribution-free UCB algorithm combining resampled median-of-means and UCB.
result Near-optimal regret bound for heavy-tailed distributions.
The study proves necessary conditions for robust decision-making in uncertain environments.
problem Conditions for robust decision-making in uncertain environments.
method Quantitative selection theorems and binary betting decisions.
result World models, belief-like memory, and persistent variables are necessary for strong task performance.
Unified analysis of Gaussian Process Thompson Sampling without discretization.
problem Sequential decision-making over continuous action spaces.
method Frequentist regret analysis based on fractional Gaussian process posteriors.
result Unified discretization-free regret bound for various kernel classes.
New algorithm reduces regret in bandit optimization for high-dimensional data.
problem Optimizing decisions in uncertain environments with high-dimensional data.
method Inspired by online Newton step, proposes a simple and efficient BCO algorithm.
result Achieves optimal regret bounds for κ κ κ -convex functions. Algorithm reduces long-term policy regret in ML decision-making.
problem Capturing long-term impacts of ML decisions in communities.
method Modeling communities as arms in a multi-armed bandit problem, defining policy regret as a stronger metric than external regret.
result Algorithm achieves provably sub-linear policy regret for long time horizons.
Batched Neural Bandits reduces policy updates in sequential decision-making.
problem Sequential decision-making with batched policy changes.
method BatchNeuralUCB algorithm combining neural networks and optimism.
result Achieves similar regret as fully sequential version with fewer policy updates.
This paper begins with a study on the dual representations of risk and regret measures and their impact on modeling multistage decision making under uncertainty. A relationship between risk envelopes and regret envelopes is established by using the Lagrangian duality theory. Such a relationship opens a door to a decomp…
We consider a setting where an agent's uncertainty is represented by a set of probability measures, rather than a single measure. Measure-bymeasure updating of such a set of measures upon acquiring new information is well-known to suffer from problems; agents are not always able to learn appropriately. To deal with the…
MINTS uses a minimalist Bayesian framework to tackle multi-armed bandits with structural constraints.
problem Sequential decision-making under uncertainty with complex structural constraints.
method Minimalist Bayesian framework with profile likelihood to eliminate nuisance parameters.
result MINTS achieves near-optimal regret guarantees and adapts to unimodal structure.
New method reduces regret in budgeted learning problems.
problem Decision-making with limited reward queries.
method Confidence-Budget Matching (CBM) principle.
result CBM-based algorithms perform well in adversarial settings.
New algorithm reduces regret in sequential decision-making problems.
problem Balancing exploration and exploitation in online sequential decision problems.
method Variational Bayesian optimistic sampling (VBOS) for optimizing policies.
result VBOS achieves i l d e O ( A T ) ilde O(\sqrt{AT}) i l d e O ( A T ) Bayesian regret for stochastic multi-armed bandits. A new algorithm balances exploration and exploitation in online decision-making.
problem Balancing exploration and exploitation in online decision-making.
method Proposed C 4 C^4 C 4 -UCB algorithm incorporating conservative mechanism. result Proved n-step upper regret bound for two situations.
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.
End-to-end framework learns LLM routing from observational data.
problem Compounding errors in decoupled approaches and reliance on full-feedback data.
method Causal end-to-end framework minimizing decision-making regret from observational data.
result Method outperforms existing baselines across different embedding models.
UCB-V algorithm improves on UCB for MAB problems with variance estimates.
problem Optimizing arm selection in MAB problems with variance information.
method Asymptotic and high probability analysis of UCB-V algorithm.
result UCB-V can exhibit instability in arm-pulling rates but achieves refined regret bounds.
Study how communication and feedback graphs affect learning outcomes.
problem Understanding the impact of feedback graphs on cooperative online learning.
method Analyzed network regret in terms of the independence number of the strong product of communication and feedback graphs.
result Proved bounds for network regret and demonstrated the non-improvable nature of positive results in pathological cases.
New algorithm optimizes online decision-making with dynamically generated actions.
problem Balancing action generation costs with optimal decision-making in online learning.
method Doubly-optimistic algorithm using LCB for action selection and UCB for action generation.
result Achieves optimal regret bound of O ( T d d + 2 d d d + 2 + d T log T ) O(T^{\frac{d}{d+2}}d^{\frac{d}{d+2}} + d\sqrt{T\log T}) O ( T d + 2 d d d + 2 d + d T log T ) . Boosting improves online decision-making for large expert sets.
problem Online convex optimization with many experts is infeasible.
method Generalizes online boosting to online convex optimization and bandit linear optimization settings.
result Near-optimal regret guarantees for various feedback models.
AAggFF improves federated learning fairness through sequential decision making.
problem Achieving client-level fairness in federated learning systems.
method Unified online convex optimization framework for adaptive aggregation strategies.
result AAggFF achieves better client-level fairness in federated learning.