Towards Computationally Efficient Responsibility Attribution in
Decentralized Partially Observable MDPs
- URL: http://arxiv.org/abs/2302.12676v1
- Date: Fri, 24 Feb 2023 14:56:25 GMT
- Title: Towards Computationally Efficient Responsibility Attribution in
Decentralized Partially Observable MDPs
- Authors: Stelios Triantafyllou, Goran Radanovic
- Abstract summary: Responsibility attribution is a key concept of accountable multi-agent decision making.
We introduce a Monte Carlo Tree Search (MCTS) type of method which efficiently approximates the agents' degrees of responsibility.
We experimentally evaluate the efficacy of our algorithm through a simulation-based test-bed.
- Score: 5.825190876052148
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Responsibility attribution is a key concept of accountable multi-agent
decision making. Given a sequence of actions, responsibility attribution
mechanisms quantify the impact of each participating agent to the final
outcome. One such popular mechanism is based on actual causality, and it
assigns (causal) responsibility based on the actions that were found to be
pivotal for the considered outcome. However, the inherent problem of
pinpointing actual causes and consequently determining the exact responsibility
assignment has shown to be computationally intractable. In this paper, we aim
to provide a practical algorithmic solution to the problem of responsibility
attribution under a computational budget. We first formalize the problem in the
framework of Decentralized Partially Observable Markov Decision Processes
(Dec-POMDPs) augmented by a specific class of Structural Causal Models (SCMs).
Under this framework, we introduce a Monte Carlo Tree Search (MCTS) type of
method which efficiently approximates the agents' degrees of responsibility.
This method utilizes the structure of a novel search tree and a pruning
technique, both tailored to the problem of responsibility attribution. Other
novel components of our method are (a) a child selection policy based on linear
scalarization and (b) a backpropagation procedure that accounts for a
minimality condition that is typically used to define actual causality. We
experimentally evaluate the efficacy of our algorithm through a
simulation-based test-bed, which includes three team-based card games.
Related papers
- Provably Efficient UCB-type Algorithms For Learning Predictive State
Representations [55.00359893021461]
The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs)
This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models.
In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
arXiv Detail & Related papers (2023-07-01T18:35:21Z) - Decomposing Counterfactual Explanations for Consequential Decision
Making [11.17545155325116]
We develop a novel and practical recourse framework that bridges the gap between the IMF and the strong causal assumptions.
texttt generates recourses by disentangling the latent representation of co-varying features.
Our experiments on real-world data corroborate our theoretically motivated recourse model and highlight our framework's ability to provide reliable, low-cost recourse.
arXiv Detail & Related papers (2022-11-03T21:26:55Z) - Neural Causal Models for Counterfactual Identification and Estimation [62.30444687707919]
We study the evaluation of counterfactual statements through neural models.
First, we show that neural causal models (NCMs) are expressive enough.
Second, we develop an algorithm for simultaneously identifying and estimating counterfactual distributions.
arXiv Detail & Related papers (2022-09-30T18:29:09Z) - Actual Causality and Responsibility Attribution in Decentralized
Partially Observable Markov Decision Processes [22.408657774650358]
We study these concepts under a widely used framework for multi-agent sequential decision making under uncertainty.
Actual causality focuses on specific outcomes and aims to identify decisions (actions) that were critical in realizing an outcome of interest.
Responsibility attribution is complementary and aims to identify the extent to which decision makers (agents) are responsible for this outcome.
arXiv Detail & Related papers (2022-04-01T09:22:58Z) - On Blame Attribution for Accountable Multi-Agent Sequential Decision
Making [29.431349181232203]
We study blame attribution in the context of cooperative multi-agent sequential decision making.
We show that some of the well known blame attribution methods, such as Shapley value, are not performance-incentivizing.
We introduce a novel blame attribution method, unique in the set of properties it satisfies.
arXiv Detail & Related papers (2021-07-26T02:22:23Z) - The Causal Neural Connection: Expressiveness, Learnability, and
Inference [125.57815987218756]
An object called structural causal model (SCM) represents a collection of mechanisms and sources of random variation of the system under investigation.
In this paper, we show that the causal hierarchy theorem (Thm. 1, Bareinboim et al., 2020) still holds for neural models.
We introduce a special type of SCM called a neural causal model (NCM), and formalize a new type of inductive bias to encode structural constraints necessary for performing causal inferences.
arXiv Detail & Related papers (2021-07-02T01:55:18Z) - Modularity in Reinforcement Learning via Algorithmic Independence in
Credit Assignment [79.5678820246642]
We show that certain action-value methods are more sample efficient than policy-gradient methods on transfer problems that require only sparse changes to a sequence of previously optimal decisions.
We generalize the recently proposed societal decision-making framework as a more granular formalism than the Markov decision process.
arXiv Detail & Related papers (2021-06-28T21:29:13Z) - Identification of Unexpected Decisions in Partially Observable
Monte-Carlo Planning: a Rule-Based Approach [78.05638156687343]
We propose a methodology for analyzing POMCP policies by inspecting their traces.
The proposed method explores local properties of policy behavior to identify unexpected decisions.
We evaluate our approach on Tiger, a standard benchmark for POMDPs, and a real-world problem related to mobile robot navigation.
arXiv Detail & Related papers (2020-12-23T15:09:28Z) - Weakly Supervised Disentangled Generative Causal Representation Learning [21.392372783459013]
We show that previous methods with independent priors fail to disentangle causally related factors even under supervision.
We propose a new disentangled learning method that enables causal controllable generation and causal representation learning.
arXiv Detail & Related papers (2020-10-06T11:38:41Z) - A Critical View of the Structural Causal Model [89.43277111586258]
We show that one can identify the cause and the effect without considering their interaction at all.
We propose a new adversarial training method that mimics the disentangled structure of the causal model.
Our multidimensional method outperforms the literature methods on both synthetic and real world datasets.
arXiv Detail & Related papers (2020-02-23T22:52:28Z)
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.