Exploration with Unreliable Intrinsic Reward in Multi-Agent Reinforcement Learning

This paper explores the use of intrisic reward (IR) to improve exploration in MARL. The authors focus on cooperative partially-observable environment, and apply their method to IQL+DQN+HER.

Observation

Most IR works converge at an estimate that is supposed to scale with $1/\sqrt{N_t(s_t,u_t)}$, but the estimation usually becomes rough for large input spaces.

They empirically observe that using IR accelerates learning, but because of the unreliability of these IR (due to rough approximation being made), the agents is prevented from finding the optimal solution.

They use a local uncertainty measure introduced by (O’Donoghue et al., 2018): $V_t[f](u|s)={\sigma }^2\varphi (s{)}^{\mathsf{T}}({\sum }_{i=1}^t{\delta }_{u_{iu}}\varphi (s_i)\varphi (s_i){)}^{-1}\varphi (s)$ with $\varphi (s)$ a representation of the state (e.g. the hidden state of the last layer of a network estimating Q-values). (O’Donoghue et al., 2018) propose $r_t^{+}:=\sqrt{V_t[q^a](u_t^a|{\tau }_t^a)}$ as the intrinsic reward.

In short, this is the variance of a linear regression mapping a fixed set of state-action pairs ($\varphi (s)$ used for cont. action spaces) to random labels $y_i$ following a Gaussian distribution. This is reminiscent of Random Network Distillation (cf. NovelD))

The architecture used is similar to COMA’s, with a centralized critic which learns to maximize a joint value function $q_{\psi }^a(u_t^a|s_t,{\mathbf{u}}_t^{-a},u_{t-1}^a)$. Instead of maximizing it w.r.t. ${\mathbf{u}}_t$, they propose to approximate a local maximum (denoted lmax) by choosing the $u_t^a$ which maximizes each individual agent’s $q_{\psi }^a$ and using it for the next iteration’s ${\mathbf{u}}^{-a}$. As in IQL, agents share $\psi$.

To accelerate the change of the sampling policy in response to newly discovered states, they use a version of $Q(\lambda )$ (Watkins, 1989) in which they do not cut the traces after exploratory steps, improving transport but introducing non-stationary targets.

Limits of intrinsic rewards (as defined above) for collaborative MARL

1. Counting for all $N_t(s_t,{\mathbf{u}}_t)$ is intractable. They propose to estimate it based on $N_t(s_{t+1})$, an heuristic that works with arbitrary large action spaces.
2. In collaborative MARL all agents should receive the same reward to avoid diverging incentives. However the uncertainty estimation for each agent depend on its observation, to which other agents could have contributed. They propose to use the largest uncertainty as an IR for all agents.
3. The agent’s value function continually change, making the representation ${\varphi }^a(x)$ differs at different times t (when using the example given above), and estimates thus become outdated after a while. To counter this they use an exponentially decaying average (see below).

The final collaborative intrinsic reward $r_t^{+}$ they use is: $r_t^{+}:=\sigma max\{0,ma{x}_a(\sqrt{{\varphi }_{(x_{t+1})}^{a\top }{\mathbf{C}}_t^{-1}{\varphi }_{(x_{t+1})}^a}-b_t)\}$ Here ${\varphi }^a(x)$ represents the hidden state of the IQL’s last layer, and ${\mathbf{C}}_t:=(1-\alpha ){\mathbf{C}}_{t-1}+{\sum }_{a=1}^n{\varphi }_{(x_t)}^a{\varphi }_{(x_t)}^{a\top }$ tackles the 3rd limit exposed above.

Finally, they train an intrinsically rewarded central agent, while the decentralized agents (here using IQL) are trained simultaneously on the shared replay buffer. This allows decentralized agents to benefit from the exploration induced by the (potentially unreliable) IR, while keeping their policies exclusively based on environmental rewards. Additionally, the central agent conditions on the true state, which contains information potentially unattainable by the decentralized agents.

Experiments §

They use a grid-world predator-prey environment, which contains mountain and valley preys. Mountain preys yield more reward, but it’s harder for our agents to catch them as actions going up the mountain have a chance of failing.

As baselines, they use versions of IQL using either no IR or IR with a magnitude of 1.

We can see below that while IR make learning faster for IQL with $\sigma =1$, the detrimental effects caused by their unreliability shows, and this version quickly stagnates both during training (left) and test (right). IQL with no IR is learns more slowly, but achieves better performances during test. Finally, ICQL seem to learn fast but stagnate quickly like IQL${}_{\sigma =1}$, but its performances during test are similar to IQL${}_{\sigma =0}$ while learning much faster. This is due to the fact that during the training with ICQL, they execute 50% of the environments with the intrinsically-rewarded central agent and 50% with the decentralized agents. This eventually makes the performances stagnate as the central agent is “holding the decentralized agents back”. During the decentralized test, all environments are done by the decentralized agents, and we can see how ICQL allows them to learn much faster than regular IQL agents.