Effective Off-Policy Evaluation and Learning in Contextual Combinatorial Bandits

• URL: http://arxiv.org/abs/2408.11202v1
• Date: Tue, 20 Aug 2024 21:25:04 GMT
• Title: Effective Off-Policy Evaluation and Learning in Contextual Combinatorial Bandits
• Authors: Tatsuhiro Shimizu, Koichi Tanaka, Ren Kishimoto, Haruka Kiyohara, Masahiro Nomura, Yuta Saito,
• Abstract summary: We explore off-policy evaluation and learning in contextual bandits. This setting is widespread in fields such as recommender systems and healthcare. We introduce a concept of factored action space, which allows us to decompose each subset into binary indicators.
• Score: 15.916834591090009
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We explore off-policy evaluation and learning (OPE/L) in contextual combinatorial bandits (CCB), where a policy selects a subset in the action space. For example, it might choose a set of furniture pieces (a bed and a drawer) from available items (bed, drawer, chair, etc.) for interior design sales. This setting is widespread in fields such as recommender systems and healthcare, yet OPE/L of CCB remains unexplored in the relevant literature. Typical OPE/L methods such as regression and importance sampling can be applied to the CCB problem, however, they face significant challenges due to high bias or variance, exacerbated by the exponential growth in the number of available subsets. To address these challenges, we introduce a concept of factored action space, which allows us to decompose each subset into binary indicators. This formulation allows us to distinguish between the ''main effect'' derived from the main actions, and the ''residual effect'', originating from the supplemental actions, facilitating more effective OPE. Specifically, our estimator, called OPCB, leverages an importance sampling-based approach to unbiasedly estimate the main effect, while employing regression-based approach to deal with the residual effect with low variance. OPCB achieves substantial variance reduction compared to conventional importance sampling methods and bias reduction relative to regression methods under certain conditions, as illustrated in our theoretical analysis. Experiments demonstrate OPCB's superior performance over typical methods in both OPE and OPL.

Related papers

• Causal Deepsets for Off-policy Evaluation under Spatial or Spatio-temporal Interferences [24.361550505778155]
  Offcommerce evaluation (OPE) is widely applied in sectors such as pharmaceuticals and e-policy-policy. This paper introduces a causal deepset framework that relaxes several key structural assumptions. We present novel algorithms that incorporate the PI assumption into OPE and thoroughly examine their theoretical foundations.
  arXiv  Detail & Related papers  (2024-07-25T10:02:11Z)
• Controllable Relation Disentanglement for Few-Shot Class-Incremental Learning [82.79371269942146]
  We propose to tackle FewShot Class-Incremental Learning (FSCIL) from a new perspective, i.e., relation disentanglement. The challenge of disentangling spurious correlations lies in the poor controllability of FSCIL. We propose a new simple-yeteffective method, called ConTrollable Relation-disentang FewShot Class-Incremental Learning (CTRL-FSCIL)
  arXiv  Detail & Related papers  (2024-03-17T03:16:59Z)
• Bayesian Off-Policy Evaluation and Learning for Large Action Spaces [14.203316003782604]
  In interactive systems, actions are often correlated, presenting an opportunity for more sample-efficient off-policy evaluation and learning. We introduce a unified Bayesian framework to capture these correlations through structured and informative priors. We propose sDM, a generic Bayesian approach for OPE and OPL, grounded in both algorithmic and theoretical foundations.
  arXiv  Detail & Related papers  (2024-02-22T16:09:45Z)
• Off-Policy Evaluation of Slate Bandit Policies via Optimizing Abstraction [22.215852332444907]
  We study the problem of slate contextual bandits where a policy selects multi-dimensional actions known as slates. The typical Inverse Propensity Scoring (IPS) estimator suffers from substantial variance due to large action spaces. We develop a novel estimator for OPE of slate bandits, called Latent IPS (LIPS), which defines importance weights in a low-dimensional slate abstraction space.
  arXiv  Detail & Related papers  (2024-02-03T14:38:09Z)
• Benchmarking Bayesian Causal Discovery Methods for Downstream Treatment Effect Estimation [137.3520153445413]
  A notable gap exists in the evaluation of causal discovery methods, where insufficient emphasis is placed on downstream inference. We evaluate seven established baseline causal discovery methods including a newly proposed method based on GFlowNets. The results of our study demonstrate that some of the algorithms studied are able to effectively capture a wide range of useful and diverse ATE modes.
  arXiv  Detail & Related papers  (2023-07-11T02:58:10Z)
• Off-Policy Evaluation for Large Action Spaces via Conjunct Effect Modeling [30.835774920236872]
  We study off-policy evaluation of contextual bandit policies for large discrete action spaces. We propose a new estimator, called OffCEM, that is based on the conjunct effect model (CEM), a novel decomposition of the causal effect into a cluster effect and a residual effect. Experiments demonstrate that OffCEM provides substantial improvements in OPE especially in the presence of many actions.
  arXiv  Detail & Related papers  (2023-05-14T04:16:40Z)
• Contextual Bandits for Advertising Campaigns: A Diffusion-Model Independent Approach (Extended Version) [73.59962178534361]
  We study an influence problem in which little is assumed to be known about the diffusion network or about the model that determines how information may propagate. In this setting, an explore-exploit approach could be used to learn the key underlying diffusion parameters, while running the campaign. We describe and compare two methods of contextual multi-armed bandits, with upper-confidence bounds on the remaining potential of influencers.
  arXiv  Detail & Related papers  (2022-01-13T22:06:10Z)
• Assessment of Treatment Effect Estimators for Heavy-Tailed Data [70.72363097550483]
  A central obstacle in the objective assessment of treatment effect (TE) estimators in randomized control trials (RCTs) is the lack of ground truth (or validation set) to test their performance. We provide a novel cross-validation-like methodology to address this challenge. We evaluate our methodology across 709 RCTs implemented in the Amazon supply chain.
  arXiv  Detail & Related papers  (2021-12-14T17:53:01Z)
• Performance Evaluation of Adversarial Attacks: Discrepancies and Solutions [51.8695223602729]
  adversarial attack methods have been developed to challenge the robustness of machine learning models. We propose a Piece-wise Sampling Curving (PSC) toolkit to effectively address the discrepancy. PSC toolkit offers options for balancing the computational cost and evaluation effectiveness.
  arXiv  Detail & Related papers  (2021-04-22T14:36:51Z)
• Deconfounding Scores: Feature Representations for Causal Effect Estimation with Weak Overlap [140.98628848491146]
  We introduce deconfounding scores, which induce better overlap without biasing the target of estimation. We show that deconfounding scores satisfy a zero-covariance condition that is identifiable in observed data. In particular, we show that this technique could be an attractive alternative to standard regularizations.
  arXiv  Detail & Related papers  (2021-04-12T18:50:11Z)
• Confounding Feature Acquisition for Causal Effect Estimation [6.174721516017138]
  We frame this challenge as a problem of feature acquisition of confounding features for causal inference. Our goal is to prioritize acquiring values for a fixed and known subset of missing confounders in samples that lead to efficient average treatment effect estimation.
  arXiv  Detail & Related papers  (2020-11-17T16:28:43Z)

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.