Improved Regret Bounds of Bilinear Bandits using Action Space Analysis

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 25
  • Download : 0
We consider the bilinear bandit problem where the learner chooses a pair of arms, each from two different action spaces of dimension d1 and d2, respectively. The learner then receives a reward whose expectation is a bilinear function of the two chosen arms with an unknown matrix param- eter Θ∗ ∈ Rd1×d2 with rank r. Despite abundant applications such as drug discovery, the optimal regret rate is unknown for this problem, though it was conjectured to be O ̃(􏰕d1d2(d1 + d2)rT ) by Jun et al. (2019) where O ̃ ignores polylogarith- mic factors in T . In this paper, we make progress towards closing the gap between the upper and lower bound on the optimal regret. First, we reject the conjecture above by proposing algorithms that􏰕 achieve the regret O( d1d2(d1 + d2)T ) using the fact that the action space dimension O(d1+d2) is significantly lower than the matrix parameter di- mension O(d1d2). Second, we additionally devise an algorithm with better empirical performance than previous algorithms.
Publisher
ICML
Issue Date
2021-07-22
Language
English
Citation

International Conference on Machine Learning, pp.4744 - 4754

URI
http://hdl.handle.net/10203/287125
Appears in Collection
MA-Conference Papers(학술회의논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0