Yonatan Nakar

Ram Rachum, Yonatan Nakar, Reuth Mirsky

Recent research in multi-agent reinforcement learning (MARL) has shown success in learning social behavior and cooperation. Social dilemmas between agents in mixed-sum settings have been studied extensively, but there is little research into social dilemmas in fullycooperative settings, where agents have no prospect of gaining reward at another agent's expense. While fully-aligned interests are conducive to cooperation between agents, they do not guarantee it. We propose a measure of "stubbornness" between agents that aims to capture the human social behavior from which it takes its name: a disagreement that is gradually escalating and potentially disastrous. We would like to promote research into the tendency of agents to be stubborn, the reactions of counterpart agents, and the resulting social dynamics. In this paper we present Stubborn, an environment for evaluating stubbornness between agents with fully-aligned incentives. In our preliminary results, the agents learn to use their partner's stubbornness as a signal for improving the choices that they make in the environment.

Ram Rachum, Yotam Amitai, Yonatan Nakar et al.

A major challenge of Reinforcement Learning is that agents often learn undesired behaviors that seem to defy the reward structure they were given. Explainable Reinforcement Learning (XRL) methods can answer queries such as "explain this specific action", "explain this specific trajectory", and "explain the entire policy". However, XRL lacks a formal definition for behavior as a pattern of actions across many episodes. We provide such a definition, and use it to enable a new query: "Explain this behavior". We present Behavior-Explainable Reinforcement Learning (BXRL), a new problem formulation that treats behaviors as first-class objects. BXRL defines a behavior measure as any function $m : Π\to \mathbb{R}$, allowing users to precisely express the pattern of actions that they find interesting and measure how strongly the policy exhibits it. We define contrastive behaviors that reduce the question "why does the agent prefer $a$ to $a'$?" to "why is $m(π)$ high?" which can be explored with differentiation. We do not implement an explainability method; we instead analyze three existing methods and propose how they could be adapted to explain behavior. We present a port of the HighwayEnv driving environment to JAX, which provides an interface for defining, measuring, and differentiating behaviors with respect to the model parameters.

Ram Rachum, Yonatan Nakar, Bill Tomlinson et al.

Modern Reinforcement Learning (RL) algorithms are able to outperform humans in a wide variety of tasks. Multi-agent reinforcement learning (MARL) settings present additional challenges, and successful cooperation in mixed-motive groups of agents depends on a delicate balancing act between individual and group objectives. Social conventions and norms, often inspired by human institutions, are used as tools for striking this balance. In this paper, we examine a fundamental, well-studied social convention that underlies cooperation in both animal and human societies: dominance hierarchies. We adapt the ethological theory of dominance hierarchies to artificial agents, borrowing the established terminology and definitions with as few amendments as possible. We demonstrate that populations of RL agents, operating without explicit programming or intrinsic rewards, can invent, learn, enforce, and transmit a dominance hierarchy to new populations. The dominance hierarchies that emerge have a similar structure to those studied in chickens, mice, fish, and other species.

Tzvika Geft, Dan Halperin, Yonatan Nakar

We study the Monotone Sliding Reconfiguration (MSR) problem, in which $\textit{labeled}$ pairwise interior-disjoint objects in a planar workspace need to be brought $\textit{one by one}$ from their initial positions to given target positions, without causing collisions. That is, at each step only one object moves to its respective target, where it stays thereafter. MSR is a natural special variant of Multi-Robot Motion Planning (MRMP) and related reconfiguration problems, many of which are known to be computationally hard. A key question is identifying the minimal mitigating assumptions that enable efficient algorithms for such problems. We first show that despite the monotonicity requirement, MSR remains a computationally hard MRMP problem. We then provide additional hardness results for MSR that rule out several natural assumptions. For example, we show that MSR remains hard without obstacles in the workspace. On the positive side, we introduce a family of MSR instances that always have a solution through a novel structural assumption pertaining to the graphs underlying the start and target configuration -- we require that these graphs are spannable by a forest of full binary trees (SFFBT). We use our assumption to obtain efficient MSR algorithms for unit discs and 2D grid settings. Notably, our assumption does not require separation between start/target positions, which is a standard requirement in efficient and complete MRMP algorithms. Instead, we (implicitly) require separation between $\textit{groups}$ of these positions, thereby pushing the boundary of efficiently solvable instances toward denser scenarios.