Unifying temporal and structural credit assignment problems

By Adrian K. Agogino, Kagan Tumer. 2004

108 citations recorded by the source corpus.

Single-agent reinforcement learners in time-extended domains and multi-agent systems share a common difficulty known as the credit assignment problem. Multiagent systems have the structural credit assignment problem of determining the contributions of a particular agent to a common task. Instead, time-extended single-agent systems have the temporal credit assignment problem of determining the contribution of a particular action to the quality of the full sequence of actions. Traditionally these two problems are considered different and are handled in separate ways. In this article we show how these two forms of the credit assignment problem are equivalent. In this unified framework, a single-agent Markov decision process can be broken down into a single-time-step multiagent process. Furthermore we show that Monte Carlo estimation or Q-learning (depending on whether the values of resulting actions in the episode are known at the time of learning) are equivalent to different agent utility functions in a multi-agent system. This equivalence shows how an often neglected issue inmulti-agent systems is equivalent to a well-known deficiency in multi-time-step learning and lays the basis for solving time-extended multi-agent problems, where both credit assignment problems are present.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Reinforcement Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

In Reinforcement Learning

Citations in the corpus

A survey and critique of multiagent deep reinforcement learning (2018, background): “, the moving target problem (non-stationarity) [55,141,289], curse of dimensionality [55,289], multiagent credit assignment [2,355], global exploration [213], and relative overgeneralization [105,247,347].”
A review of cooperative multi-agent deep reinforcement learning (2019, background): “ibution. Following this idea, the rest of this section discusses the correspondingalgorithms. In the literature of tabular RL, there are two commonapproachesfor reward shaping: (i) difference rewards [3] which tries to isolate the reward of each agent from the joint reward, i.e. ˆri= r− r−i, where r”
Off-Policy Multi-Agent Decomposed Policy Gradients (2020, methodology): “However, they leave the issue of credit assignment (Tumer et al., 2002; Agogino & Tumer, 2004) largely untouched in fully cooperative settings, where agents learn policies from a single global reward signal.”
How the Experts Do It: Assessing and Explaining Agent Behaviors in Real-Time Strategy Games (2017, background): “dit assignment problem (determining the effect of an action taken at a particular time on the outcome) and a structural one (determining the effect of a particular system element on the outcome). See [1] for an accessible explanation of these problems. The casters found a potentially “satisﬁcing” ap”
Potential-based difference rewards for multiagent reinforcement learning (2014, background): “The difference reward (Di) is a shaped reward signal that helps an agent learn the consequences of its actions on the system objective by removing a large amount of the noise created by the actions of other agents active in the system [1, 2].”