Learning Actionable Counterfactual Explanations in Large State Spaces

• URL: http://arxiv.org/abs/2404.17034v1
• Date: Thu, 25 Apr 2024 20:49:03 GMT
• Title: Learning Actionable Counterfactual Explanations in Large State Spaces
• Authors: Keziah Naggita, Matthew R. Walter, Avrim Blum,
• Abstract summary: We consider settings where optimal CFEs correspond to solutions of weighted set cover problems. In this work, we provide a deep-network learning procedure that we show experimentally is able to achieve strong performance. Our problem can also be viewed as one of learning an optimal policy in a family of large but deterministic Markov Decision Processes.
• Score: 16.30292272064278
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Counterfactual explanations (CFEs) are sets of actions that an agent with a negative classification could take to achieve a (desired) positive classification, for consequential decisions such as loan applications, hiring, admissions, etc. In this work, we consider settings where optimal CFEs correspond to solutions of weighted set cover problems. In particular, there is a collection of actions that agents can perform that each have their own cost and each provide the agent with different sets of capabilities. The agent wants to perform the cheapest subset of actions that together provide all the needed capabilities to achieve a positive classification. Since this is an NP-hard optimization problem, we are interested in the question: can we, from training data (instances of agents and their optimal CFEs) learn a CFE generator that will quickly provide optimal sets of actions for new agents? In this work, we provide a deep-network learning procedure that we show experimentally is able to achieve strong performance at this task. We consider several problem formulations, including formulations in which the underlying "capabilities" and effects of actions are not explicitly provided, and so there is an informational challenge in addition to the computational challenge. Our problem can also be viewed as one of learning an optimal policy in a family of large but deterministic Markov Decision Processes (MDPs).

Related papers

• Advancing Embodied Agent Security: From Safety Benchmarks to Input Moderation [52.83870601473094]
  Embodied agents exhibit immense potential across a multitude of domains. Existing research predominantly concentrates on the security of general large language models. This paper introduces a novel input moderation framework, meticulously designed to safeguard embodied agents.
  arXiv  Detail & Related papers  (2025-04-22T08:34:35Z)
• Efficient and Robust Regularized Federated Recommendation [52.24782464815489]
  The recommender system (RSRS) addresses both user preference and privacy concerns. We propose a novel method that incorporates non-uniform gradient descent to improve communication efficiency. RFRecF's superior robustness compared to diverse baselines.
  arXiv  Detail & Related papers  (2024-11-03T12:10:20Z)
• Proactive Agent: Shifting LLM Agents from Reactive Responses to Active Assistance [95.03771007780976]
  We tackle the challenge of developing proactive agents capable of anticipating and initiating tasks without explicit human instructions. First, we collect real-world human activities to generate proactive task predictions. These predictions are labeled by human annotators as either accepted or rejected. The labeled data is used to train a reward model that simulates human judgment.
  arXiv  Detail & Related papers  (2024-10-16T08:24:09Z)
• Satisficing Exploration for Deep Reinforcement Learning [26.73584163318647]
  In complex environments that approach the vastness and scale of the real world, attaining optimal performance may in fact be an entirely intractable endeavor. Recent work has leveraged tools from information theory to design agents that deliberately forgo optimal solutions in favor of sufficiently-satisfying or satisficing solutions. We extend an agent that directly represents uncertainty over the optimal value function allowing it to both bypass the need for model-based planning and to learn satisficing policies.
  arXiv  Detail & Related papers  (2024-07-16T21:28:03Z)
• GLANCE: Global Actions in a Nutshell for Counterfactual Explainability [10.25011737760687]
  We introduce GLANCE, a versatile and adaptive framework, comprising two algorithms. C-GLANCE employs a clustering approach that considers both the feature space and the space of counterfactual actions. T-GLANCE provides additional features to enhance flexibility.
  arXiv  Detail & Related papers  (2024-05-29T09:24:25Z)
• Universal Adversarial Perturbations for Vision-Language Pre-trained Models [30.04163729936878]
  We propose a novel black-box method to generate Universal Adversarial Perturbations (UAPs) The ETU takes into account the characteristics of UAPs and the intrinsic cross-modal interactions to generate effective UAPs. To further enhance the effectiveness and transferability of UAPs, we also design a novel data augmentation method named ScMix.
  arXiv  Detail & Related papers  (2024-05-09T03:27:28Z)
• Quantifying Agent Interaction in Multi-agent Reinforcement Learning for Cost-efficient Generalization [63.554226552130054]
  Generalization poses a significant challenge in Multi-agent Reinforcement Learning (MARL) The extent to which an agent is influenced by unseen co-players depends on the agent's policy and the specific scenario. We present the Level of Influence (LoI), a metric quantifying the interaction intensity among agents within a given scenario and environment.
  arXiv  Detail & Related papers  (2023-10-11T06:09:26Z)
• Flexible and Robust Counterfactual Explanations with Minimal Satisfiable Perturbations [56.941276017696076]
  We propose a conceptually simple yet effective solution named Counterfactual Explanations with Minimal Satisfiable Perturbations (CEMSP) CEMSP constrains changing values of abnormal features with the help of their semantically meaningful normal ranges. Compared to existing methods, we conduct comprehensive experiments on both synthetic and real-world datasets to demonstrate that our method provides more robust explanations while preserving flexibility.
  arXiv  Detail & Related papers  (2023-09-09T04:05:56Z)
• For Better or Worse: The Impact of Counterfactual Explanations' Directionality on User Behavior in xAI [6.883906273999368]
  Counterfactual explanations (CFEs) are a popular approach in explainable artificial intelligence (xAI) CFEs describe a scenario that is better than the factual state (upward CFE), or a scenario that is worse than the factual state (downward CFE) This study compares the impact of CFE directionality on behavior and experience of participants tasked to extract new knowledge from an automated system.
  arXiv  Detail & Related papers  (2023-06-13T09:16:38Z)
• On the Complexity of Multi-Agent Decision Making: From Learning in Games to Partial Monitoring [105.13668993076801]
  A central problem in the theory of multi-agent reinforcement learning (MARL) is to understand what structural conditions and algorithmic principles lead to sample-efficient learning guarantees. We study this question in a general framework for interactive decision making with multiple agents. We show that characterizing the statistical complexity for multi-agent decision making is equivalent to characterizing the statistical complexity of single-agent decision making.
  arXiv  Detail & Related papers  (2023-05-01T06:46:22Z)
• Sample-Efficient Multi-Objective Learning via Generalized Policy Improvement Prioritization [8.836422771217084]
  Multi-objective reinforcement learning (MORL) algorithms tackle sequential decision problems where agents may have different preferences. We introduce a novel algorithm that uses Generalized Policy Improvement (GPI) to define principled, formally-derived prioritization schemes. We empirically show that our method outperforms state-of-the-art MORL algorithms in challenging multi-objective tasks.
  arXiv  Detail & Related papers  (2023-01-18T20:54:40Z)
• Cluster-level pseudo-labelling for source-free cross-domain facial expression recognition [94.56304526014875]
  We propose the first Source-Free Unsupervised Domain Adaptation (SFUDA) method for Facial Expression Recognition (FER) Our method exploits self-supervised pretraining to learn good feature representations from the target data. We validate the effectiveness of our method in four adaptation setups, proving that it consistently outperforms existing SFUDA methods when applied to FER.
  arXiv  Detail & Related papers  (2022-10-11T08:24:50Z)
• Formalizing the Problem of Side Effect Regularization [81.97441214404247]
  We propose a formal criterion for side effect regularization via the assistance game framework. In these games, the agent solves a partially observable Markov decision process. We show that this POMDP is solved by trading off the proxy reward with the agent's ability to achieve a range of future tasks.
  arXiv  Detail & Related papers  (2022-06-23T16:36:13Z)
• PAC: Assisted Value Factorisation with Counterfactual Predictions in Multi-Agent Reinforcement Learning [43.862956745961654]
  Multi-agent reinforcement learning (MARL) has witnessed significant progress with the development of value function factorization methods. In this paper, we show that in partially observable MARL problems, an agent's ordering over its own actions could impose concurrent constraints. We propose PAC, a new framework leveraging information generated from Counterfactual Predictions of optimal joint action selection.
  arXiv  Detail & Related papers  (2022-06-22T23:34:30Z)
• Local Learning Matters: Rethinking Data Heterogeneity in Federated Learning [61.488646649045215]
  Federated learning (FL) is a promising strategy for performing privacy-preserving, distributed learning with a network of clients (i.e., edge devices)
  arXiv  Detail & Related papers  (2021-11-28T19:03:39Z)
• Amortized Generation of Sequential Counterfactual Explanations for Black-box Models [26.91950709495675]
  Counterfactual explanations (CFEs) provide what if'' feedback of a form. Current CFE approaches are single shot -- that is, they assume $x$ can change to $x'$ in a single time period. We propose a novel approach that generates sequential CFEs that allow $x$ to move across intermediate states to a final state $x'$.
  arXiv  Detail & Related papers  (2021-06-07T20:54:48Z)
• Attention Actor-Critic algorithm for Multi-Agent Constrained Co-operative Reinforcement Learning [3.296127938396392]
  We consider the problem of computing optimal actions for Reinforcement Learning (RL) agents in a co-operative setting. We extend this algorithm to the constrained multi-agent RL setting.
  arXiv  Detail & Related papers  (2021-01-07T03:21:15Z)
• Reinforcement Learning with Efficient Active Feature Acquisition [59.91808801541007]
  In real-life, information acquisition might correspond to performing a medical test on a patient. We propose a model-based reinforcement learning framework that learns an active feature acquisition policy. Key to the success is a novel sequential variational auto-encoder that learns high-quality representations from partially observed states.
  arXiv  Detail & Related papers  (2020-11-02T08:46:27Z)
• Selective Classification via One-Sided Prediction [54.05407231648068]
  One-sided prediction (OSP) based relaxation yields an SC scheme that attains near-optimal coverage in the practically relevant high target accuracy regime. We theoretically derive bounds generalization for SC and OSP, and empirically we show that our scheme strongly outperforms state of the art methods in coverage at small error levels.
  arXiv  Detail & Related papers  (2020-10-15T16:14:27Z)
• Scaling Guarantees for Nearest Counterfactual Explanations [17.590082025924747]
  Counterfactual explanations are being widely used to explain algorithmic decisions. We provide a framework based on Mixed-Integer Programming (MIP) to compute nearest counterfactual explanations. Our approach allows for efficiently computing diverse CFEs with both distance guarantees and perfect coverage.
  arXiv  Detail & Related papers  (2020-10-10T10:05:50Z)
• Randomized Entity-wise Factorization for Multi-Agent Reinforcement Learning [59.62721526353915]
  Multi-agent settings in the real world often involve tasks with varying types and quantities of agents and non-agent entities. Our method aims to leverage these commonalities by asking the question: What is the expected utility of each agent when only considering a randomly selected sub-group of its observed entities?''
  arXiv  Detail & Related papers  (2020-06-07T18:28:41Z)

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.