skip to main content
10.1145/1250790.1250870acmconferencesArticle/Chapter ViewAbstractPublication PagesstocConference Proceedingsconference-collections
Article

Playing games with approximation algorithms

Published: 11 June 2007 Publication History

Abstract

In an online linear optimization problem, on each period t, an online algorithm chooses st ∈ S from a fixed (possibly infinite) set S of feasible decisions. Nature (who may be adversarial) chooses a weight vector wt ∈ R, and the algorithm incurs cost c(st,wt), where c is a fixed cost function that is linear in the weight vector. In the full-information setting, the vector wt is then revealed to the algorithm, and in the bandit setting, only the cost experienced, c(st,wt), is revealed. The goal of the online algorithm is to perform nearly as well as the best fixed s ∈ S in hindsight. Many repeated decision-making problems with weights fit naturally into this framework, such as online shortest-path, online TSP, online clustering, and online weighted set cover.
Previously, it was shown how to convert any efficient exact offline optimization algorithm for such a problem into an efficient online bandit algorithm in both the full-information and the bandit settings, with average cost nearly as good as that of the best fixed s ∈ S in hindsight. However, in the case where the offline algorithm is an approximation algorithm with ratio α > 1, the previous approach only worked for special types of approximation algorithms. We show how to convert any offline approximation algorithm for a linear optimization problem into a corresponding online approximation algorithm, with a polynomial blowup in runtime. If the offline algorithm has an α-approximation guarantee, then the expected cost of the online algorithm on any sequence is not much larger than α times that of the best s ∈ S, where the best is chosen with the benefit of hindsight. Our main innovation is combining Zinkevich's algorithm for convex optimization with a geometric transformation that can be applied to any approximation algorithm. Standard techniques generalize the above result to the bandit setting, except that a "Barycentric Spanner" for the problem is also (provably) necessary as input.Our algorithm can also be viewed as a method for playing largerepeated games, where one can only compute approximate best-responses, rather than best-responses.

References

[1]
B. Awerbuch and R. Kleinberg. Adaptive routing with end-to-end feedback: Distributed learning and geometric approaches. In Proceedings of the 36th ACM Symposium on Theory of Computing (STOC), 2004.
[2]
M.-F. Balcan and A. Blum. Approximation algorithms and online mechanisms for item pricing. In Proceedings of the 7th ACM Conference on Electronic Commerce (EC), 2006.
[3]
R. Carr and S. Vempala. Randomized metarounding. Random Struct. Algorithms, 20(3):343--352, 2002.
[4]
D. Chakrabarty, A. Mehta, and V. Vazirani. Design is as easy as optimization. In 33rd International Colloquium on Automata, Languages and Programming (ICALP), 2006.
[5]
V. Dani and T.P. Hayes. Robbing the bandit: Less regret in online geometric optimization against an adaptive adversary. In Proceedings of the 17th ACM-SIAM Symposium on Discrete Algorithms (SODA), 2006.
[6]
M.X. Goemans and D.P. Williamson. Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM, 42(6):1115--1145, 1995.
[7]
J. Hannan. Approximation to Bayes risk in repeated play. In M. Dresher, A. Tucker, and P. Wolfe, editors, Contributions to the Theory of Games, volume III, pages 97--139. Princeton University Press, 1957.
[8]
A. Kalai and S. Vempala. Efficient algorithms for online decision problems. J. Comput. Syst. Sci., 71(3):291--307, 2005.
[9]
H. McMahan and A. Blum. Online geometric optimization in the bandit setting against an adaptive adversary. In Proceedings of the 17th Annual Conference on Learning Theory (COLT), 2004.
[10]
H. Robbins. Some aspects of the sequential design of experiments. In Bulletin of the American Mathematical Society, volume 55, 1952.
[11]
M. Zinkevich. Online convex programming and generalized infinitesimal gradient ascent. In Proceedings of the 20th International Conference on Machine Learning (ICML), 2003.

Cited By

View all
  • (2024)Online combinatorial optimization with group fairness constraintsProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/44(394-402)Online publication date: 3-Aug-2024
  • (2024)Online Combinatorial Optimization with Group Fairness ConstraintsSSRN Electronic Journal10.2139/ssrn.4824251Online publication date: 2024
  • (2023)Smoothed analysis of sequential probability assignmentProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669617(79808-79831)Online publication date: 10-Dec-2023
  • Show More Cited By

Index Terms

  1. Playing games with approximation algorithms

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    STOC '07: Proceedings of the thirty-ninth annual ACM symposium on Theory of computing
    June 2007
    734 pages
    ISBN:9781595936318
    DOI:10.1145/1250790
    Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

    Sponsors

    Publisher

    Association for Computing Machinery

    New York, NY, United States

    Publication History

    Published: 11 June 2007

    Permissions

    Request permissions for this article.

    Check for updates

    Author Tags

    1. approximation algorithms
    2. online linear optimization
    3. regret minimization

    Qualifiers

    • Article

    Conference

    STOC07
    Sponsor:
    STOC07: Symposium on Theory of Computing
    June 11 - 13, 2007
    California, San Diego, USA

    Acceptance Rates

    Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

    Upcoming Conference

    STOC '25
    57th Annual ACM Symposium on Theory of Computing (STOC 2025)
    June 23 - 27, 2025
    Prague , Czech Republic

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • Downloads (Last 12 months)31
    • Downloads (Last 6 weeks)4
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    Cited By

    View all
    • (2024)Online combinatorial optimization with group fairness constraintsProceedings of the Thirty-Third International Joint Conference on Artificial Intelligence10.24963/ijcai.2024/44(394-402)Online publication date: 3-Aug-2024
    • (2024)Online Combinatorial Optimization with Group Fairness ConstraintsSSRN Electronic Journal10.2139/ssrn.4824251Online publication date: 2024
    • (2023)Smoothed analysis of sequential probability assignmentProceedings of the 37th International Conference on Neural Information Processing Systems10.5555/3666122.3669617(79808-79831)Online publication date: 10-Dec-2023
    • (2023)Regularized online DR-submodular optimizationProceedings of the Thirty-Ninth Conference on Uncertainty in Artificial Intelligence10.5555/3625834.3626077(2608-2617)Online publication date: 31-Jul-2023
    • (2023)Inverse reinforcement learning without reinforcement learningProceedings of the 40th International Conference on Machine Learning10.5555/3618408.3619793(33299-33318)Online publication date: 23-Jul-2023
    • (2023)Misalignment, Learning, and Ranking: Harnessing Users Limited AttentionSSRN Electronic Journal10.2139/ssrn.4365381Online publication date: 2023
    • (2022)Oracle-efficient online learning for smoothed adversariesProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3600564(4072-4084)Online publication date: 28-Nov-2022
    • (2022)Regret Minimization of Extensive Games and Its Application on Game StrategiesHighlights in Science, Engineering and Technology10.54097/hset.v12i.145512(204-212)Online publication date: 26-Aug-2022
    • (2015)Efficient algorithms with performance guarantees for the stochastic multiple-choice Knapsack problemProceedings of the 24th International Conference on Artificial Intelligence10.5555/2832249.2832305(403-409)Online publication date: 25-Jul-2015
    • (2013)Playing Non-linear Games with Linear OraclesProceedings of the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science10.1109/FOCS.2013.52(420-428)Online publication date: 26-Oct-2013
    • Show More Cited By

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media