Timezone: »

 
Poster
Instance-optimal PAC Algorithms for Contextual Bandits
Zhaoqi Li · Lillian Ratliff · houssam nassif · Kevin Jamieson · Lalit Jain

Wed Nov 30 02:00 PM -- 04:00 PM (PST) @ Hall J #839
in Poster Session 4 »
In the stochastic contextual bandit setting, regret-minimizing algorithms have been extensively researched, but their instance-minimizing best-arm identification counterparts remain seldom studied. In this work, we focus on the stochastic bandit problem in the $(\epsilon,\delta)$-PAC setting: given a policy class $\Pi$ the goal of the learner is to return a policy $\pi\in \Pi$ whose expected reward is within $\epsilon$ of the optimal policy with probability greater than $1-\delta$. We characterize the first instance-dependent PAC sample complexity of contextual bandits through a quantity $\rho_{\Pi}$, and provide matching upper and lower bounds in terms of $\rho_{\Pi}$ for the agnostic and linear contextual best-arm identification settings. We show that no algorithm can be simultaneously minimax-optimal for regret minimization and instance-dependent PAC for best-arm identification. Our main result is a new instance-optimal and computationally efficient algorithm that relies on a polynomial number of calls to a cost-sensitive classification oracle.
Keywords: Active Learning · Reinforcement Learning · contextual bandits
[ Paper]  [ Poster]  [ OpenReview] 

Author Information

Zhaoqi Li
Lillian Ratliff (University of Washington)
houssam nassif (Amazon)
Kevin Jamieson (U Washington)
Lalit Jain (University of Washington)

More from the Same Authors