Efficient algorithms for online decision problems

DOI10.1016/J.JCSS.2004.10.016MaRDI QIDQ2568459zbMATH OpenOpenAlexFDO

Authors Santosh S. Vempala, Adam Tauman Kalai

Publication date 10 October 2005

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2004.10.016

zbMATH Keywords

decision theoryHannan's algorithmonline algorithmsoptimization

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Nonnumerical algorithms (68W05)

Recommendations

• Efficient algorithms for online decision problems.
• Algorithmic Learning Theory
• Logarithmic regret algorithms for online convex optimization
• Logarithmic Regret Algorithms for Online Convex Optimization
• Efficient algorithms for combinatorial online prediction

Cites work

• 10.1162/1532443041424328
• Adapting to a reliable network path
• Adaptive routing with end-to-end feedback: distributed learning and geometric approaches
• Approximation algorithms for metric facility location and k -Median problems using the primal-dual schema and Lagrangian relaxation
• Dynamic huffman coding
• Efficient algorithms for online decision problems.
• scientific article; zbMATH DE number 3128728 (Why is no real title available?)
• scientific article; zbMATH DE number 67625 (Why is no real title available?)
• scientific article; zbMATH DE number 1559549 (Why is no real title available?)
• scientific article; zbMATH DE number 1775392 (Why is no real title available?)
• scientific article; zbMATH DE number 1833416 (Why is no real title available?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Learning Theory
• Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems
• Predicting nearly as well as the best pruning of a planar decision graph.
• Self-adjusting binary search trees
• Static optimality and dynamic search-optimality in lists and trees
• The geometry of graphs and some of its algorithmic applications
• Universal Portfolios

Cited in

(83)

• Logarithmic regret algorithms for online convex optimization
• Regret to the best vs. regret to the average
• Perspectives on multiagent learning
• The Canadian Traveller Problem and its competitive analysis
• Online algorithms: a survey
• On minimaxity of follow the leader strategy in the stochastic setting
• Scale-free online learning
• Sampled fictitious play is Hannan consistent
• Online multiple kernel classification
• Extracting certainty from uncertainty: regret bounded by variation in costs
• Regret bounds for sleeping experts and bandits
• Machine learning advised algorithms for the ski rental problem with a discount
• Learning in auctions: regret is hard, envy is easy
• Online learning for min-max discrete problems
• Regret bounded by gradual variation for online convex optimization
• The covering Canadian traveller problem
• Online linear optimization and adaptive routing
• Regrets of proximal method of multipliers for online non-convex optimization with long term constraints
• Regret minimization in online Bayesian persuasion: handling adversarial receiver's types under full and partial feedback models
• Combinatorial optimization. Abstracts from the workshop held November 7--13, 2021 (hybrid meeting)
• Unified algorithms for online learning and competitive analysis
• On modification of population-based search algorithms for convergence in stochastic combinatorial optimization
• Learning hurdles for sleeping experts
• Online discrete optimization in social networks in the presence of Knightian uncertainty
• A combinatorial metrical task system problem under the uniform metric
• Online Linear Optimization for Job Scheduling Under Precedence Constraints
• Efficient algorithms for combinatorial online prediction
• Lower bounds on individual sequence regret
• Making online decisions with bounded memory
• scientific article; zbMATH DE number 437568 (Why is no real title available?)
• The on-line shortest path problem under partial monitoring
• The post-disaster debris clearance problem under incomplete information
• Oracle-based robust optimization via online learning
• Combining initial segments of lists
• Online variance minimization
• Combinatorial bandits
• Beyond the hazard rate: more perturbation algorithms for adversarial multi-armed bandits
• Nonstochastic Multi-Armed Bandits with Graph-Structured Feedback
• Online learning to rank with top-k feedback
• Online learning over a finite action set with limited switching
• Efficient online linear optimization with approximation algorithms
• Preference-based online learning with dueling bandits: a survey
• scientific article; zbMATH DE number 7626715 (Why is no real title available?)
• Structured Robust Submodular Maximization: Offline and Online Algorithms
• Multi-Finger Binary Search Trees
• Online learning based on online DCA and application to online classification
• Online first-order framework for robust convex optimization
• AN ONLINE PORTFOLIO SELECTION ALGORITHM WITH REGRET LOGARITHMIC IN PRICE VARIATION
• Efficient algorithms for online decision problems.
• An Online Policy Gradient Algorithm for Markov Decision Processes with Continuous States and Actions
• scientific article; zbMATH DE number 7064051 (Why is no real title available?)
• Algorithmic Learning Theory
• Equilibria of greedy combinatorial auctions
• Near-optimal algorithms for online matrix prediction
• A Linearly Convergent Variant of the Conditional Gradient Algorithm under Strong Convexity, with Applications to Online and Stochastic Optimization
• A simulated annealing algorithm for the restricted stochastic traveling salesman problem with exponentially distributed arc lengths
• Small-Loss Bounds for Online Learning with Partial Information
• No-regret algorithms in on-line learning, games and convex optimization
• No-regret dynamics in the Fenchel game: a unified framework for algorithmic convex optimization
• No-regret learning for repeated non-cooperative games with lossy bandits
• Synthetic control as online linear regression
• Regret analysis of an online majorized semi-proximal ADMM for online composite optimization
• Online dynamic submodular optimization
• Multiagent learning for competitive opinion optimization
• Efficient algorithms for implementing incremental proximal-point methods
• An \(\alpha \)-regret analysis of adversarial bilateral trade
• Comparing ad-hoc and MIP-based algorithms for the online facility location problem
• All-time safety and sample-efficient meta update for online safe meta reinforcement learning under Markov task transition
• On the complexity of computing sparse equilibria and lower bounds for no-regret learning in games
• Efficient projection-free online convex optimization using stochastic gradients
• Follow-the-perturbed-leader achieves best-of-both-worlds for bandit problems
• Online learning for traffic navigation in congested networks
• Thompson sampling for adversarial bit prediction
• An efficient algorithm for cooperative semi-bandits
• Online boosting with bandit feedback
• Online linear optimization with sparsity constraints
• Competitive ratio vs regret minimization: achieving the best of both worlds
• Online non-additive path learning under full and partial information
• Online alternating direction method of multipliers for online composite optimization
• Vladimir V'yugin: short biography and some research contributions
• Convergence to equilibrium of no-regret dynamics in congestion games
• Replicator dynamics: old and new
• Feature-aware regularization for sparse online learning

This page was built for publication: Efficient algorithms for online decision problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2568459)