Causally Abstracted Multi-armed Bandits

• URL: http://arxiv.org/abs/2404.17493v2
• Date: Wed, 17 Jul 2024 07:10:25 GMT
• Title: Causally Abstracted Multi-armed Bandits
• Abstract summary: Multi-armed bandits (MAB) and causal MABs (CMAB) are established frameworks for decision-making problems. We extend transfer learning to setups involving CMABs defined on potentially different variables. We propose algorithms to learn in a CAMAB, and study their regret.
• Score: 7.741729770041214
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-armed bandits (MAB) and causal MABs (CMAB) are established frameworks for decision-making problems. The majority of prior work typically studies and solves individual MAB and CMAB in isolation for a given problem and associated data. However, decision-makers are often faced with multiple related problems and multi-scale observations where joint formulations are needed in order to efficiently exploit the problem structures and data dependencies. Transfer learning for CMABs addresses the situation where models are defined on identical variables, although causal connections may differ. In this work, we extend transfer learning to setups involving CMABs defined on potentially different variables, with varying degrees of granularity, and related via an abstraction map. Formally, we introduce the problem of causally abstracted MABs (CAMABs) by relying on the theory of causal abstraction in order to express a rigorous abstraction map. We propose algorithms to learn in a CAMAB, and study their regret. We illustrate the limitations and the strengths of our algorithms on a real-world scenario related to online advertising.

Related papers

• Split the Differences, Pool the Rest: Provably Efficient Multi-Objective Imitation [49.86232017439639]
  We introduce Multi-Output Augmented Behavioral Cloning (MA-BC)<n>MA-BC partitions divergent expert data while pooling state-action pairs where no behavior conflict is observed.<n>We establish a novel lower bound for multi-objective imitation learning, demonstrating that MA-BC is minimax optimal.
  arXiv  Detail & Related papers  (2026-05-12T11:49:08Z)
• On the Paradoxical Interference between Instruction-Following and Task Solving [50.75960598434753]
  Instruction following aims to align Large Language Models (LLMs) with human intent by specifying explicit constraints on how tasks should be performed.<n>We reveal a counterintuitive phenomenon: instruction following can paradoxically interfere with LLMs' task-solving capability.<n>We propose a metric, SUSTAINSCORE, to quantify the interference of instruction following with task solving.
  arXiv  Detail & Related papers  (2026-01-29T17:48:56Z)
• Using causal abstractions to accelerate decision-making in complex bandit problems [4.09922517136932]
  We propose AT-UCB, an algorithm which efficiently exploits shared information between CMAB problem instances defined at different levels of abstraction.<n>We illustrate the advantages of AT-UCB theoretically, through a novel upper bound on the cumulative regret, and empirically, by applying AT-UCB to epidemiological simulators with varying resolution and computational cost.
  arXiv  Detail & Related papers  (2025-09-04T15:11:04Z)
• When Disagreements Elicit Robustness: Investigating Self-Repair Capabilities under LLM Multi-Agent Disagreements [56.29265568399648]
  We argue that disagreements prevent premature consensus and expand the explored solution space.<n>Disagreements on task-critical steps can derail collaboration depending on the topology of solution paths.
  arXiv  Detail & Related papers  (2025-02-21T02:24:43Z)
• Decision Mamba: A Multi-Grained State Space Model with Self-Evolution Regularization for Offline RL [57.202733701029594]
  Decision Mamba is a novel multi-grained state space model with a self-evolving policy learning strategy. To mitigate the overfitting issue on noisy trajectories, a self-evolving policy is proposed by using progressive regularization. The policy evolves by using its own past knowledge to refine the suboptimal actions, thus enhancing its robustness on noisy demonstrations.
  arXiv  Detail & Related papers  (2024-06-08T10:12:00Z)
• Combinatorial Multivariant Multi-Armed Bandits with Applications to Episodic Reinforcement Learning and Beyond [58.39457881271146]
  We introduce a novel framework of multi-armed bandits (CMAB) with multivariant and probabilistically triggering arms (CMAB-MT) Compared with existing CMAB works, CMAB-MT not only enhances the modeling power but also allows improved results by leveraging distinct statistical properties for multivariant random variables. Our framework can include many important problems as applications, such as episodic reinforcement learning (RL) and probabilistic maximum coverage for goods distribution.
  arXiv  Detail & Related papers  (2024-06-03T14:48:53Z)
• Causal Optimal Transport of Abstractions [8.642152250082368]
  Causal abstraction (CA) theory establishes formal criteria for relating multiple structural causal models (SCMs) at different levels of granularity. We propose COTA, the first method to learn abstraction maps from observational and interventional data without assuming complete knowledge of the underlying SCMs. We extensively evaluate COTA on synthetic and real world problems, and showcase its advantages over non-causal, independent and aggregated COTA formulations.
  arXiv  Detail & Related papers  (2023-12-13T12:54:34Z)
• DCID: Deep Canonical Information Decomposition [84.59396326810085]
  We consider the problem of identifying the signal shared between two one-dimensional target variables. We propose ICM, an evaluation metric which can be used in the presence of ground-truth labels. We also propose Deep Canonical Information Decomposition (DCID) - a simple, yet effective approach for learning the shared variables.
  arXiv  Detail & Related papers  (2023-06-27T16:59:06Z)
• Jointly Learning Consistent Causal Abstractions Over Multiple Interventional Distributions [8.767175335575386]
  An abstraction can be used to relate two structural causal models representing the same system at different levels of resolution. We introduce a first framework for causal abstraction learning between SCMs based on the formalization of abstraction recently proposed by Rischel.
  arXiv  Detail & Related papers  (2023-01-14T11:22:16Z)
• Causal Inference Through the Structural Causal Marginal Problem [17.91174054672512]
  We introduce an approach to counterfactual inference based on merging information from multiple datasets. We formalise this approach for categorical SCMs using the response function formulation and show that it reduces the space of allowed marginal and joint SCMs.
  arXiv  Detail & Related papers  (2022-02-02T21:45:10Z)
• Partial Counterfactual Identification from Observational and Experimental Data [83.798237968683]
  We develop effective Monte Carlo algorithms to approximate the optimal bounds from an arbitrary combination of observational and experimental data. Our algorithms are validated extensively on synthetic and real-world datasets.
  arXiv  Detail & Related papers  (2021-10-12T02:21:30Z)
• Stein Variational Model Predictive Control [130.60527864489168]
  Decision making under uncertainty is critical to real-world, autonomous systems. Model Predictive Control (MPC) methods have demonstrated favorable performance in practice, but remain limited when dealing with complex distributions. We show that this framework leads to successful planning in challenging, non optimal control problems.
  arXiv  Detail & Related papers  (2020-11-15T22:36:59Z)
• Multi-armed Bandits with Cost Subsidy [1.6631602844999724]
  We present two applications, intelligent SMS routing problem and ad audience optimization problem. We show that naive generalizations of existing MAB algorithms do not perform well for this problem. We also present a simple variant of explore-then-commit and establish near-optimal regret bounds for this algorithm.
  arXiv  Detail & Related papers  (2020-11-03T05:38:42Z)
• Invariant Causal Prediction for Block MDPs [106.63346115341862]
  Generalization across environments is critical to the successful application of reinforcement learning algorithms to real-world challenges. We propose a method of invariant prediction to learn model-irrelevance state abstractions (MISA) that generalize to novel observations in the multi-environment setting.
  arXiv  Detail & Related papers  (2020-03-12T21:03:01Z)

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.