Novel algorithm reduces feature inclusion in online decision-making.
problem Optimizing decision-making for personalized user experiences with fairness.
method Online Batched Sequential Inclusion (OBSI) algorithm for sequential feature inclusion.
result OBSI outperforms other algorithms in terms of regret, relevance of features, and compute.
An online decision-making algorithm using stochastic gradient descent for big data.
problem Efficiently updating decision rules in online decision making with big data.
method Stochastic gradient descent for online updates, asymptotic normality of estimators.
result Asymptotic normality of parameter and value estimators, enabling statistical inference.
New algorithms for fast online decision making using neural networks and martingale posteriors.
problem Online sequential decision making under uncertainty.
method Martingale posterior neural networks for fast online learning and decision making.
result Achieves competitive performance-speed trade-offs in non-stationary contextual bandits and Bayesian optimization.
New online method for statistical inference with matrix context in decision-making.
problem Statistical inference in decision-making with matrix context.
method Proposes a fully online procedure to conduct statistical inference with adaptive data collection, handling low-rank structure.
result Establishes asymptotic normality of debiased estimators and proves validity of confidence intervals.
New method learns decisions from collective preferences without individual covariates.
problem Making decisions online without individual covariates.
method Collaborative filtering, matrix completion bandit, ε-greedy policy, online gradient descent, inverse propensity weighting.
result Method outperforms benchmarks and reveals new discoveries.
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. A scalable online method for Gaussian processes that improves decision-making in various applications.
problem Scalability issues with Gaussian processes for online decision-making.
method Online variational conditioning (OVC) for SVGPs.
result OVC enables efficient online learning and decision-making with SVGPs.
Unified framework for constrained online decision-making.
problem Sequential decisions under stage-wise feasibility constraints.
method Upper counterfactual confidence bounds and generalized eluder dimension.
result Principled foundation for constrained sequential decision-making.
Batch Thompson Sampling reduces exploration-exploitation trade-off in online decision making.
problem Balancing exploration and exploitation in online decision making.
method Introducing a batch Thompson Sampling framework for stochastic multi-arm bandit and linear contextual bandit problems.
result Achieves asymptotic regret bound with O ( log T ) O(\log T) O ( log T ) batch queries, significantly reducing interactions. The paper addresses statistical inference for online decision-making in a contextual bandit setting.
problem Understanding the performance of reward models in online decision-making with contextual information.
method The paper uses the contextual bandit framework with a linear reward model and the ε \varepsilon ε -greedy policy to address the exploration-exploitation dilemma. It employs the martingale central limit theorem and inverse propensity score weighting to establish asymptotic normality of parameter estimators. result The online ordinary least squares estimator and the online weighted least squares estimator are asymptotically normal, providing insights into the performance of the reward model.
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. 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…
New online GP algorithm offers performance guarantees for streaming data.
problem Training and inference of GPs require all historic data, limiting online decision-making.
method Developed a new theoretical framework based on PAC-Bayes theory, optimizing empirical risk and parameter divergence.
result Offers both a guarantee of generalized performance and good accuracy.
New method controls false discoveries in real-time data streams.
problem Online testing of hypotheses with strict error constraints and no future data.
method Structure-adaptive sequential testing (SAST) with alpha-investment algorithm.
result Substantial power gain over existing online testing rules.
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 ) . Online anomaly detection in surveillance videos with false alarm rate bounds.
problem Lack of theoretical performance analysis and online decision making in anomaly detection.
method Proposes an online anomaly detection method with asymptotic bounds on false alarm rate.
result Demonstrates effectiveness on publicly available data sets, outperforming state-of-the-art algorithms.
New framework converts offline to online estimation using black-box offline estimators.
problem Convert offline estimation algorithms to online estimation algorithms.
method Oracle-Efficient Online Estimation (OEOE) framework.
result Achieves near-optimal online estimation error via black-box offline estimators.
This paper tackles online strategic decision making with asymmetry and knowledge transportability.
problem Strategic decision making with information asymmetry and knowledge transportability challenges.
method Developed a sample-efficient algorithm for online learning under these conditions.
result Proved sample complexity of O ( 1 / ε 2 ) O(1/ε^2) O ( 1/ ε 2 ) for learning an ε ε ε -optimal policy. Develops a new framework for analyzing sequential decision-making problems using information theory.
problem Lack of information-theoretic generalization bounds for sequential decision-making problems.
method Introduces a sequential supersample framework that separates learner filtration from proof-side enlargement, controlling the generalization gap by sequential CMI.
result Establishes a sequential CMI that controls the generalization gap in sequential decision-making problems.
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.
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.
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 ) . Post-processing predictors reduces calibration errors for decision-making.
problem Predictors with low calibration error for machine learning may have high error for decision-making.
method Post-processing with ε distance to calibration adds noise to make predictions differentially private.
result Post-processing achieves O(√ε) ECE and CDL, asymptotically optimal.
Optimistic pricing algorithm handles online dynamic pricing with censored demand.
problem Online dynamic pricing with censoring of potential demand.
method Optimistic estimates of derivatives for pricing algorithm.
result Achieves i l d e O ( T ) ilde{O}(\sqrt{T}) i l d e O ( T ) optimal regret against adversarial inventory series. Study noisy rewards in online decision-making with unknown distributions.
problem Learning optimal decisions in online settings with noisy and unknown reward distributions.
method Proposes algorithms integrating learning and decision-making via LCB thresholding.
result Achieves competitive ratios of 1 - 1/e and 1/2 in various settings.
Algorithm improves decision-making with partially observed contexts using pretrained models.
problem Improving decision-making with partially observed contexts in online linear contextual bandits.
method PULSE-UCB algorithm that uses pretrained models trained on auxiliary data to impute missing features.
result Achieves near-optimal performance in i.i.d. context case with Hölder-smooth missing features.
Enhanced decision-making through Dreamer's anticipatory trajectories and Online Decision Transformer.
problem Efficiently integrating world models with decision transformers.
method Combining Dreamer's trajectory forecasting with Online Decision Transformer's adaptive learning.
result Notable improvements in sample efficiency and reward maximization.
Graph neural Thompson Sampling improves online decision-making for graph data.
problem Online decision-making with graph-structured rewards.
method GNN-TS algorithm using GNN for mean reward estimation and graph neural tangent features for uncertainty.
result GNN-TS achieves a state-of-the-art regret bound of i l d e O ( ( i l d e d T ) 1 / 2 ) ilde{\mathcal{O}}(( ilde{d} T)^{1/2}) i l d e O (( i l d e d T ) 1/2 ) . We introduce a novel theoretical framework for Return On Investment (ROI) maximization in repeated decision-making. Our setting is motivated by the use case of companies that regularly receive proposals for technological innovations and want to quickly decide whether they are worth implementing. We design an algorithm …
The paper improves Bayesian optimization by calibrating uncertainty estimates.
problem Improper uncertainty estimates in Bayesian optimization when data is non-stationary.
method Proposes online learning algorithms to maintain calibration on non-i.i.d. data and integrates them into Bayesian optimization.
result Calibrated Bayesian optimization converges to better optima in fewer steps.
Study minimax-optimal rates for offline decision-making with function approximation.
problem Statistical complexity of offline decision-making with function approximation.
method Near minimax-optimal rates for stochastic contextual bandits and Markov decision processes, using pseudo-dimension and behavior policy.
result Established performance limits and new characterization of behavior policy.
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.
SPARKLE handles high-dimensional covariates for online decision-making.
problem Complex reward-covariate relationships in high-dimensional settings.
method SPARKLE uses a sparse additive reward model with doubly penalized estimator and adaptive screening.
result SPARKLE achieves sublinear regret bound logarithmic in covariate dimensionality.
A smart method predicts and optimizes decisions online with resource constraints.
problem Online decision-making with resource constraints.
method Combines prediction and optimization with dual update using mirror descent.
result Regret bounds and convergence rates for general convex feasible regions.
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.
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.
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.
New approach uses autoregressive models to explore and quantify uncertainty in decision-making.
problem Quantifying and exploring uncertainty in online decision-making.
method Reformulates uncertainty as missing future outcomes, training autoregressive models for next-outcome prediction.
result Establishes a reduction from online learning to offline next-outcome prediction, controlling Bayesian regret by sequence prediction loss.
Anchor-TS uses median anchoring to improve online decision-making from offline data with distribution shift.
problem Improving online decision-making from offline data with distribution shift.
method Sample-Mean Anchored Thompson Sampling (Anchor-TS) with median anchoring.
result Anchor-TS safely leverages offline data to accelerate online learning and reduces regret.
The paper proposes a method to construct confidence sets using likelihood ratios for sequential decision-making.
problem Constructing valid uncertainty estimates for unknown quantities in sequential decision-making.
method The method uses likelihood ratios to create any-time valid confidence sequences without specialized treatment for each application.
result The proposed confidence sets maintain the prescribed coverage in a model-agnostic manner and their size depends on the choice of estimator sequence.
OLPA optimizes online user-centric selection with probing, achieving near-optimal regret bounds.
problem Sequential decision-making with unknown resources and rewards.
method Probing-augmented user-centric selection (PUCS) framework, greedy probing algorithm, OLPA algorithm.
result OLPA achieves a near-optimal regret bound of O ( T + ln 2 T ) \mathcal{O}(\sqrt{T} + \ln^{2} T) O ( T + ln 2 T ) for online settings. Proposes Genetic Thompson Sampling for multi-armed bandits, improving performance in nonstationary settings.
problem Improving sequential decision making tasks of online learning agents using multi-armed bandits.
method Integrates genetic principles into Thompson Sampling for multi-armed bandits.
result Significantly outperforms baselines in nonstationary settings.
New algorithms use offline data to improve online decision-making with latent states.
problem Accelerating online sequential decision-making with latent states in offline data.
method Design end-to-end latent bandit algorithms for linear latent contextual bandits, learning latent subspace offline and using it online.
result Proves minimax optimal regret guarantees for online algorithms and practical efficiency.
Bridges uplift modeling and sequential decision-making with online budget allocation.
problem Treatment allocation under budget constraints in digital advertising.
method Budget-Constrained Causal Bandits (BCCB) integrates learning, exploration, and budget pacing.
result Data-efficiency crossover: BCCB operates effectively from the first user, 3-5x lower performance variance.
Paper proposes using unlabeled data for fair decision-making.
problem Bias in decision-making algorithms due to biased labels and selective labeling.
method Variational autoencoder for learning unbiased data representations from both labeled and unlabeled data.
result Method learns fair and stable decision policies with high utility.
New method tackles anomaly detection in video surveillance using continual learning.
problem Challenges in continual learning for high-dimensional applications like video surveillance.
method Transfer learning and continual learning for online anomaly detection.
result Significantly reduces training complexity and continual learning from recent data.
New methods improve Bayesian inference and decision-making in online learning.
problem Current Bayesian deep learning does not fully utilize joint predictives for sequential decision-making.
method Proposes new evaluation settings for active learning and active sampling, focusing on marginal and joint cross-entropies.
result Initial experiments suggest challenges in applying current BDL inference techniques in high-dimensional spaces.