The paper explores dynamic regret with switching cost in online decision making.
problem The relation between dynamic regret and switching cost in online decision making.
method Investigates two classic online settings: Online Algorithms (OA) and Online Convex Optimization (OCO). Provides a new theoretical analysis framework.
result The switching cost impacts dynamic regret differently in OA and has no impact in OCO.
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 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.
OLBoost improves online decision tree performance without increasing memory or time costs.
problem Improving predictive performance in online decision trees without high memory or time costs.
method OLBoost applies boosting to small regions of the instances space within online decision tree algorithms.
result OLBoost can significantly improve online learning decision tree performance without increasing tree size.
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.
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 proposes a new dynamic pricing method with always-valid online statistical learning.
problem Designing dynamic pricing policies that adapt to online uncertainty and maintain validity.
method Regularized online statistical learning with theoretical guarantees and three major advantages.
result Proposed OORMLP pricing policy secures logarithmic regret in decision horizon.
New algorithms for privately learning decision lists and halfspaces.
problem Private learning of decision lists and halfspaces.
method Differentially private algorithms for PAC and online models.
result Private algorithms match or surpass non-private guarantees.
New online algorithms tackle dynamic decision-focused learning.
problem Dynamic decision-focused learning in evolving environments.
method Regularization and perturbation techniques for non-convex optimization.
result First provable guarantees for online decision-focused learning.
This paper studies risk-averse online learning, showing differences from risk-neutral approaches.
problem Risk-averse online learning under mean-variance performance measure.
method Analyzes bandit and full information settings, establishes fundamental limitations.
result Worst-case regret is lower bounded by Ω ( T ) Ω(T) Ω ( T ) , contrasting with Ω ( T ) Ω(\sqrt{T}) Ω ( T ) for risk-neutral learning. New framework captures long-term decision dependence in online learning.
problem Long-term dependence on past decisions in online learning.
method Introduces Online Convex Optimization with Unbounded Memory (OCO-UMB) and p p p -effective memory capacity. result Proves O ( H p T ) O(\sqrt{H_p T}) O ( H p T ) upper bound on policy regret and matching lower bound. Paper tackles online convex optimization with stochastic constraints.
problem Online convex optimization with stochastic constraints.
method Proposes a new algorithm achieving O ( T ) O(\sqrt{T}) O ( T ) expected regret and constraint violations and O ( T log ( T ) ) O(\sqrt{T}\log(T)) O ( T log ( T )) high probability regret and constraint violations. result Achieves optimal regret and constraint violation bounds.
The paper addresses contextual optimization problems with feedback, aiming to minimize regret.
problem Contextual optimization with feedback information.
method Characterizing the optimal minimax policy in offline setting and leveraging geometric characterization in online setting to optimize cumulative regret.
result Developed an algorithm yielding logarithmic regret bound in the online setting.
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.
Converts GBDT trees to neural networks for online updates.
problem Performance loss in converting GBDT trees to neural networks.
method Converts existing GBDT implementations to neural network architectures, allowing online updates of decision splits.
result Learning bounds for neural network architecture with updated splits.
The paper tackles online decision making with costly information acquisition.
problem Collecting useful information is costly and requires active decision-making.
method Proposes two algorithms, Sim-OOS and Seq-OOS, for simultaneous and sequential observation making.
result Both algorithms achieve sublinear regret in time.
Paper proposes RL for real-time smart grid cyber attack detection.
problem Real-time detection of cyber-attacks in smart grids.
method Formulated as POMDP, uses model-free reinforcement learning.
result Effective in timely and accurate detection of cyber-attacks.
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 ) . 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.
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. 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 ) . 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.
Proposes a new UCB algorithm using bootstrap for online decision making.
problem Improving exploration in online decision making with partial feedback.
method Non-parametric, data-dependent UCB algorithm based on multiplier bootstrap with second-order correction.
result Significant regret reductions in multi-armed and linear bandit problems.
Continuous-time algorithms improve online learning performance.
problem Online learning with sequential data and minimizing overall regret.
method Extending discrete-time algorithms to continuous-time models for online linear optimization, adversarial bandit, and adversarial linear bandit.
result Optimal regret bounds are proven for continuous-time settings.
New algorithm reduces decision switching in dynamic environments.
problem Online learning with memory and non-stationary environments.
method Dynamic policy regret, novel ensemble approach, meta-base decomposition.
result Proves optimal dynamic policy regret for memory length, non-stationarity, and time horizon.
Combines offline causal inference and online bandit learning for better decision-making.
problem Making adaptive decisions using both logged and streaming data to avoid user harm.
method Unified offline causal inference and online learning algorithms, deriving bounds on decision accuracy.
result First upper regret bound for forest-based online bandit algorithms.
New algorithms learn in complex decision-making problems with smooth transitions.
problem Learning in complex decision-making problems with smooth transitions.
method UCB and PSRL philosophies applied to episodic Markov decision processes with kernel approximation.
result Low regret learning achieved in continuous state and action spaces.
New algorithm for online convex minimization over integer lattice.
problem Online decision-making with nonlinear combinatorial objectives.
method Introduces online L a t u r a l \mathrm{L}^{
atural} L a t u r a l -convex minimization and proposes efficient algorithms. result Tight regret bound for full information setting algorithm.
Improved online learning for MDPs with changing costs.
problem Online learning in linearly solvable MDPs with changing state costs.
method Following the leader algorithm with logarithmic regret bound.
result Achieved regret of order log^2 T, significantly better than previous bounds.
Paper tackles robust online learning with worst-case distributions.
problem Distributionally robust online learning with worst-case Wasserstein ambiguity sets.
method Formulated as an online saddle-point stochastic game, proposed a general framework converging to robust Nash equilibrium.
result Proposed a tailored algorithm for piecewise concave loss functions, achieving substantial speedups.
TopRank algorithm improves online ranking with better performance and insights.
problem Sequential decision-making in online learning to rank with user feedback.
method Generalized click model and topological sort-based algorithm.
result TopRank outperforms existing algorithms in terms of performance and proof insight.
The paper presents algorithms to learn decision-maker's objective function from observed data.
problem Learning the objective function of a decision-maker from observed data and decisions.
method Online learning algorithms for inverse optimization with convergence rate O ( 1 / T ) \mathcal{O}(1/\sqrt{T}) O ( 1/ T ) . result The algorithms allow decisions as good as the observed decision-maker's after few iterations.
Paper tackles online optimization with memory and competitive control.
problem Minimizing hitting and switching costs in online optimization problems.
method Optimistic Regularized Online Balanced Descent algorithm.
result Achieves a constant, dimension-free competitive ratio.
Efficient algorithms for online convex optimization with limited switching decisions.
problem Online convex optimization with limited switching decisions.
method Presented computationally efficient algorithms for both general and strongly convex losses.
result Regret bounds of O ( T / S ) O(T/S) O ( T / S ) for general convex losses and O ~ ( T / S 2 ) \widetilde O(T/S^2) O ( T / S 2 ) for strongly convex losses. 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.
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 ) . New algorithm for online learning in episodic MDPs with convex objectives.
problem Online episodic convex reinforcement learning.
method Online mirror descent algorithm with varying constraint sets and exploration bonus.
result Near-optimal regret bounds for online CURL without prior knowledge of transition function.
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.
A new sequential method estimates Poisson means in streaming data, achieving optimality and efficiency.
problem Estimating Poisson means in a streaming, or online, framework.
method A quasi-Bayesian approach based on Newton's algorithm for a sequential estimate.
result Established frequentist guarantees including consistency and asymptotic optimality.
New algorithm for quickly deciding on tech innovations to maximize ROI.
problem Maximizing ROI in repeated decision-making for tech innovations.
method Developed a novel algorithm for learning optimal decision-making policies over innovation proposals.
result Algorithm converges to optimal policy with a rate of order m i n { 1 / ( N Δ 2 ) , N − 1 / 3 } min\{1/(NΔ^2),N^{-1/3}\} min { 1/ ( N Δ 2 ) , N − 1/3 } . MOANOFS tackles online feature selection for big data classification.
problem Online supervised feature selection for binary classification in big data.
method Hybrid of online learning and automated negotiation.
result MOANOFS achieves high accuracy with real-world applications.
We address online linear optimization problems when the possible actions of the decision maker are represented by binary vectors. The regret of the decision maker is the difference between her realized loss and the best loss she would have achieved by picking, in hindsight, the best possible action. Our goal is to unde…
Adaptive robust strategy improves online portfolio selection by managing market trends and costs.
problem Optimizing sequential investment decisions in volatile markets.
method Robust optimization with adaptive parameter adjustment.
result Adaptive scheme outperforms existing strategies in cumulative returns and Sharpe ratios.
Proposes an online model for LLM cascading with adaptive API selection.
problem Adaptive querying and selection of LLM APIs in a context-dependent environment.
method Develops a learning approach combining GMM estimation and UCB-style bounds.
result Achieves cumulative regret of O ~ ( T ) \widetilde O(\sqrt T) O ( T ) over T T T periods. 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.
DOPL learns from preference feedback to solve RMAB problems.
problem Learning optimal decisions in RMAB with limited reward information.
method Direct online preference learning (DOPL) for Pref-RMAB.
result DOPL achieves sublinear regret for RMAB with preference feedback.