Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Reports, Documentation, and Standards
  4. Minimizing Regret of Bandit Online Optimization in Unconstrained Action Spaces
 
report

Minimizing Regret of Bandit Online Optimization in Unconstrained Action Spaces

Tatarenko, Tatiana
•
Kamgarpour, Maryam  
May 2, 2020

We consider online convex optimization with a zero-order oracle feedback. In particular, the decision maker does not know the explicit representation of the time-varying cost functions, or their gradients. At each time step, she observes the value of the corresponding cost function evaluated at her chosen action (zero-order oracle). The objective is to minimize the regret, that is, the difference between the sum of the costs she accumulates and that of a static optimal action had she known the sequence of cost functions a priori. We present a novel algorithm to minimize regret in unconstrained action spaces. Our algorithm hinges on a classical idea of one-point estimation of the gradients of the cost functions based on their observed values. The algorithm is independent of problem parameters. Letting T denote the number of queries of the zero-order oracle and n the problem dimension, the regret rate achieved is O(n2/3T2/3). Moreover, we adapt the presented algorithm to the setting with two-point feedback and demonstrate that the adapted procedure achieves the theoretical lower bound on the regret of (n1/2T1/2).

  • Details
  • Metrics
Type
report
Author(s)
Tatarenko, Tatiana
Kamgarpour, Maryam  
Date Issued

2020-05-02

Subjects

Computer Science - Machine Learning

•

Mathematics - Optimization and Control

URL
http://arxiv.org/abs/1806.05069
Editorial or Peer reviewed

NON-REVIEWED

Written at

OTHER

EPFL units
SYCAMORE  
Available on Infoscience
December 1, 2021
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/183423
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés