Leveraging Offline Data in Linear Latent Bandits

• URL: http://arxiv.org/abs/2405.17324v1
• Date: Mon, 27 May 2024 16:23:34 GMT
• Title: Leveraging Offline Data in Linear Latent Bandits
• Authors: Chinmaya Kausik, Kevin Tan, Ambuj Tewari,
• Abstract summary: We show that $textitevery$ exchangeable and coherent stateless decision process is a latent bandit. We present a principled method to learn this subspace from short offline trajectories with guarantees. We provide two methods to leverage this subspace online: LOCAL-UCB and ProBALL-UCB.
• Score: 16.006405951752903
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Sequential decision-making domains such as recommender systems, healthcare and education often have unobserved heterogeneity in the population that can be modeled using latent bandits $-$ a framework where an unobserved latent state determines the model for a trajectory. While the latent bandit framework is compelling, the extent of its generality is unclear. We first address this by establishing a de Finetti theorem for decision processes, and show that $\textit{every}$ exchangeable and coherent stateless decision process is a latent bandit. The latent bandit framework lends itself particularly well to online learning with offline datasets, a problem of growing interest in sequential decision-making. One can leverage offline latent bandit data to learn a complex model for each latent state, so that an agent can simply learn the latent state online to act optimally. We focus on a linear model for a latent bandit with $d_A$-dimensional actions, where the latent states lie in an unknown $d_K$-dimensional subspace for $d_K \ll d_A$. We present SOLD, a novel principled method to learn this subspace from short offline trajectories with guarantees. We then provide two methods to leverage this subspace online: LOCAL-UCB and ProBALL-UCB. We demonstrate that LOCAL-UCB enjoys $\tilde O(\min(d_A\sqrt{T}, d_K\sqrt{T}(1+\sqrt{d_AT/d_KN})))$ regret guarantees, where the effective dimension is lower when the size $N$ of the offline dataset is larger. ProBALL-UCB enjoys a slightly weaker guarantee, but is more practical and computationally efficient. Finally, we establish the efficacy of our methods using experiments on both synthetic data and real-life movie recommendation data from MovieLens.

Related papers

• Anytime Model Selection in Linear Bandits [61.97047189786905]
  We develop ALEXP, which has an exponentially improved dependence on $M$ for its regret. Our approach utilizes a novel time-uniform analysis of the Lasso, establishing a new connection between online learning and high-dimensional statistics.
  arXiv  Detail & Related papers  (2023-07-24T15:44:30Z)
• Optimal Best-Arm Identification in Bandits with Access to Offline Data [27.365122983434887]
  We consider combining offline data with online learning, an area less studied but obvious practical importance. We develop algorithms that match the lower bound on sample complexity when $delta$ is small. Our algorithms are computationally efficient with an average per-sample acquisition cost of $tildeO(K)$, and rely on a careful characterization of the optimality conditions of the lower bound problem.
  arXiv  Detail & Related papers  (2023-06-15T11:12:35Z)
• Pessimism in the Face of Confounders: Provably Efficient Offline Reinforcement Learning in Partially Observable Markov Decision Processes [99.26864533035454]
  We study offline reinforcement learning (RL) in partially observable Markov decision processes. We propose the underlineProxy variable underlinePessimistic underlinePolicy underlineOptimization (textttP3O) algorithm. textttP3O is the first provably efficient offline RL algorithm for POMDPs with a confounded dataset.
  arXiv  Detail & Related papers  (2022-05-26T19:13:55Z)
• Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism [26.11003309805633]
  offline reinforcement learning (RL) algorithms seek to learn an optimal policy from a fixed dataset without active data collection. Based on the composition of the offline dataset, two main categories of methods are used: imitation learning and vanilla offline RL. We present a new offline RL framework that smoothly interpolates between the two extremes of data composition.
  arXiv  Detail & Related papers  (2021-03-22T17:27:08Z)
• Online Sparse Reinforcement Learning [60.44832065993122]
  We investigate the hardness of online reinforcement learning in fixed horizon, sparse linear decision process (MDP) We show that linear regret is generally unavoidable in this case, even if there exists a policy that collects well-conditioned data. This shows that in the large-action setting, the difficulty of learning can be attributed to the difficulty of finding a good exploratory policy.
  arXiv  Detail & Related papers  (2020-11-08T16:47:42Z)
• Restless-UCB, an Efficient and Low-complexity Algorithm for Online Restless Bandits [61.490254407420906]
  We study the online restless bandit problem, where the state of each arm evolves according to a Markov chain. We propose Restless-UCB, a learning policy that follows the explore-then-commit framework.
  arXiv  Detail & Related papers  (2020-11-05T05:16:04Z)
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection [71.9765117768556]
  We consider the contextual bandit problem under the high dimensional linear model. This setting finds essential applications such as personalized recommendation, online advertisement, and personalized medicine. We propose doubly growing epochs and estimating the parameter using the best subset selection method.
  arXiv  Detail & Related papers  (2020-09-04T04:10:39Z)
• Latent Bandits Revisited [55.88616813182679]
  A latent bandit problem is one in which the learning agent knows the arm reward distributions conditioned on an unknown discrete latent state. We propose general algorithms for this setting, based on both upper confidence bounds (UCBs) and Thompson sampling. We provide a unified theoretical analysis of our algorithms, which have lower regret than classic bandit policies when the number of latent states is smaller than actions.
  arXiv  Detail & Related papers  (2020-06-15T19:24:02Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.