Open Problem: First-Order Regret Bounds for Contextual Bandits

Alekh Agarwal; Akshay Krishnamurthy; John Langford; Haipeng Luo; Robert E. Schapire

Open Problem: First-Order Regret Bounds for Contextual Bandits

Alekh Agarwal
, Akshay Krishnamurthy
, John Langford
, Haipeng Luo
, Robert E. Schapire

Research output: Contribution to journal › Conference article › peer-review

Abstract

We describe two open problems related to first order regret bounds for contextual bandits. The first asks for an algorithm with a regret bound of O^e(√L_*K ln N) where there are K actions, N policies, and L_* is the cumulative loss of the best policy. The second asks for an optimization-oracle-efficient algorithm with regret O^e(L^2/3_*poly(K, ln(N/δ))). We describe some positive results, such as an inefficient algorithm for the second problem, and some partial negative results.

Original language	English (US)
Pages (from-to)	4-7
Number of pages	4
Journal	Proceedings of Machine Learning Research
Volume	65
State	Published - 2017
Externally published	Yes
Event	30th Conference on Learning Theory, COLT 2017 - Amsterdam, Netherlands Duration: Jul 7 2017 → Jul 10 2017

All Science Journal Classification (ASJC) codes

Software
Control and Systems Engineering
Statistics and Probability
Artificial Intelligence

Keywords

contextual bandits
first-order regret bounds
oracle-efficient algorithms

Cite this

@article{c1779971d26b411d981267123aca3287,

title = "Open Problem: First-Order Regret Bounds for Contextual Bandits",

abstract = "We describe two open problems related to first order regret bounds for contextual bandits. The first asks for an algorithm with a regret bound of Oe(√L*K ln N) where there are K actions, N policies, and L* is the cumulative loss of the best policy. The second asks for an optimization-oracle-efficient algorithm with regret Oe(L2/3*poly(K, ln(N/δ))). We describe some positive results, such as an inefficient algorithm for the second problem, and some partial negative results.",

keywords = "contextual bandits, first-order regret bounds, oracle-efficient algorithms",

author = "Alekh Agarwal and Akshay Krishnamurthy and John Langford and Haipeng Luo and Schapire, \{Robert E.\}",

note = "Publisher Copyright: {\textcopyright} 2017 A. Agarwal, A. Krishnamurthy, J. Langford, H. Luo \& R.E. Schapire.; 30th Conference on Learning Theory, COLT 2017 ; Conference date: 07-07-2017 Through 10-07-2017",

year = "2017",

language = "English (US)",

volume = "65",

pages = "4--7",

journal = "Proceedings of Machine Learning Research",

issn = "2640-3498",

publisher = "ML Research Press",

}

TY - JOUR

T1 - Open Problem

T2 - 30th Conference on Learning Theory, COLT 2017

AU - Agarwal, Alekh

AU - Krishnamurthy, Akshay

AU - Langford, John

AU - Luo, Haipeng

AU - Schapire, Robert E.

PY - 2017

Y1 - 2017

N2 - We describe two open problems related to first order regret bounds for contextual bandits. The first asks for an algorithm with a regret bound of Oe(√L*K ln N) where there are K actions, N policies, and L* is the cumulative loss of the best policy. The second asks for an optimization-oracle-efficient algorithm with regret Oe(L2/3*poly(K, ln(N/δ))). We describe some positive results, such as an inefficient algorithm for the second problem, and some partial negative results.

AB - We describe two open problems related to first order regret bounds for contextual bandits. The first asks for an algorithm with a regret bound of Oe(√L*K ln N) where there are K actions, N policies, and L* is the cumulative loss of the best policy. The second asks for an optimization-oracle-efficient algorithm with regret Oe(L2/3*poly(K, ln(N/δ))). We describe some positive results, such as an inefficient algorithm for the second problem, and some partial negative results.

KW - contextual bandits

KW - first-order regret bounds

KW - oracle-efficient algorithms

UR - https://www.scopus.com/pages/publications/105031498846

UR - https://www.scopus.com/pages/publications/105031498846#tab=citedBy

M3 - Conference article

AN - SCOPUS:105031498846

SN - 2640-3498

VL - 65

SP - 4

EP - 7

JO - Proceedings of Machine Learning Research

JF - Proceedings of Machine Learning Research

Y2 - 7 July 2017 through 10 July 2017

ER -

Open Problem: First-Order Regret Bounds for Contextual Bandits

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Other files and links

Fingerprint

Cite this