Online bandit convex optimisation with stochastic constraints via two-point feedback

Jichi Yu, Jueyou Li and Guo Chen

International Journal of Systems Science, 2023, vol. 54, issue 10, 2089-2105

Abstract: In this paper, an online convex optimisation problem with stochastic constraints in the bandit setup is investigated. We are particularly interested in the scenario where the gradient information of both loss and constraint functions is unavailable. Under this scenario, only the values of loss and constraint functions at a few random points near the decision are provided to the decision maker after the decision is submitted. We first propose an online bandit algorithm based on the virtual queue in which two-point feedback is used to approximate the gradient feedback. Then we adopt the static benchmark to analyse the optimisation performance and establish the sub-linear expected static regret and sub-linear expected constraint violations of the proposed algorithm in the two-point bandit feedback setup. Moreover, the expected static regret and constraint violations are further improved to $ \mathcal {O}(\ln {T}) $ O(ln⁡T) when loss functions satisfy the condition of strong convexity. Finally, an online job scheduling numerical simulation is shown to demonstrate the performance of the proposed method and to corroborate the theoretical guarantees.

Date: 2023
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1080/00207721.2023.2209566 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:taf:tsysxx:v:54:y:2023:i:10:p:2089-2105

Ordering information: This journal article can be ordered from
http://www.tandfonline.com/pricing/journal/TSYS20

DOI: 10.1080/00207721.2023.2209566

Access Statistics for this article

International Journal of Systems Science is currently edited by Visakan Kadirkamanathan

More articles in International Journal of Systems Science from Taylor & Francis Journals
Bibliographic data for series maintained by Chris Longhurst ().