<figure><img src="image_1.png" /></figure>

HAL
open science

# Probabilistic Decision-Making Models for Multi-Agent Systems and Human-Robot Collaboration

Yang You

<figure><img src="image_2.png" /></figure>

## To cite this version:

Yang You. Probabilistic Decision-Making Models for Multi-Agent Systems and Human-Robot Collaboration. Computer Science [cs]. Université de Lorraine, 2023. English. NNT: 2023LORR0014. tel-04073320

HAL Id: tel-04073320

https://hal.univ-lorraine.fr/tel-04073320

Submitted on 18 Apr 2023

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_3.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
AVERTISSEMENT

Ce document est le fruit d'un long travail approuvé par le jury de soutenance et mis à disposition de l'ensemble de la communauté universitaire élargie.

Il est soumis à la propriété intellectuelle de l'auteur. Ceci implique une obligation de citation et de référencement lors de l'utilisation de ce document.

D'autre part, toute contrefaçon, plagiat, reproduction illicite
encourt une poursuite pénale.

Contact bibliothèque : ddoc-theses-contact@univ-lorraine.fr

*(Cette adresse ne permet pas de contacter les auteurs)*

LIENS

Code de la Propriété Intellectuelle. articles L 122. 4

Code de la Propriété Intellectuelle. articles L 335.2- L 335.10

http://www.cfcopies.com/V2/leg/leg_droi.php

http://www.culture.gouv.fr/culture/infos-pratiques/droits/protection.htm
# Probabilistic Decision-Making Models for Multi-Agent Systems and Human-Robot Collaboration

## THÈSE

présentée et soutenue publiquement le February 22, 2023

pour l'obtention du

Doctorat de l'Université de Lorraine

(mention informatique)

par

YOU YANG

## Composition du jury

<table><tr><td>Président :</td><td>Armelle Brun</td><td>Professeur, Université de Lorraine</td></tr><tr><td>Rapporteurs :</td><td>Abdel-Illah Mouaddib<br>Adriana Tapus</td><td>Professeur, Université de Caen Normandie<br>Professeur, ENSTA Paris</td></tr><tr><td>Examineurs :</td><td>Olivier Buffet<br>Caroline Chanel<br>Vincent Thomas</td><td>Chargé de recherche, INRIA (directeur)<br>Maître de conférences, ISAE-Supaéro<br>Maître de conférences, Université de Lorraine (co-directeur)</td></tr><tr><td>Invité :</td><td>Rachid Alami</td><td>Directeur de recherche, LAAS-CNRS</td></tr></table>
Mis en page avec la classe thesul.
# Résumé

Dans cette thèse, nous nous intéressons à la prise de décision haut niveau (planification de tâches) pour la robotique à l'aide de modèles de prise de décision markoviens et sous deux aspects : la collaboration robot-robot et la collaboration homme-robot.

Dans le cadre de la collaboration robot-robot (RRC), nous étudions les problèmes de décision de plusieurs robots devant atteindre un objectif commun de manière collaborative, et nous utilisons le cadre des processus de décision markoviens partiellement observables et décentralisés (Dec-POMDP) pour modéliser de tels problèmes. Nous proposons deux nouveaux algorithmes pour résoudre les Dec-POMDP. Le premier algorithme (Inf-JESP) trouve des équilibres de Nash en construisant itérativement pour chaque agent la politique meilleure réponse aux autres agents jusqu'à ce qu'aucune amélioration ne soit possible. Pour traiter les Dec-POMDP à horizon infini, nous représentons la politique de chaque agent à l'aide d'un contrôleur à états finis. Le deuxième algorithme (MC-JESP) étend Inf-JESP avec des modèles génératifs, ce qui nous permet de passer à l'échelle pour des grands problèmes. Nous démontrons expérimentalement que nos méthodes sont compétitives par rapport aux solveurs Dec-POMDP existants.

Dans le cadre de la collaboration homme-robot (HRC), nous ne pouvons contrôler que le comportement du robot, lequel doit faire face à des objectifs humains et à des comportements induits incertains. Nous cherchons ainsi à dériver des politiques de robot qui sont robustes aux incertitudes sur les comportements humains. Pour cela, nous discutons des modèles mentaux qui peuvent être utilisés pour modéliser le comportement humain dans une telle tâche collaborative. Nous décrivons ensuite une approche générale pour dériver, automatiquement et sans connaissance préalable, un modèle de comportements humains basé sur l'hypothèse que l'humain contrôle aussi le robot. À partir de là, nous proposons deux algorithmes pour calculer des politiques robustes pour le robot en se basant sur la résolution d'un POMDP dont l'état contient l'état interne de l'humain. Le premier algorithme fonctionne hors ligne et fournit une politique complète qui peut être utilisée par le robot pendant son exécution. Le deuxième algorithme est une méthode en ligne, c'est-à-dire qu'il décide de l'action du robot à chaque pas de temps au cours de l'exécution. Par rapport à l'approche hors ligne, la méthode en ligne ne nécessite qu'un modèle génératif et peut donc s'adapter à de grands problèmes. Des expériences avec des humains synthétiques et réels sont menées dans un environnement simulé pour évaluer ces algorithmes. Nous observons que nos méthodes peuvent fournir des décisions robustes pour des robots collaboratifs malgré les incertitudes sur les objectifs et les comportements humains.

Dans cette thèse, notre recherche sur la collaboration robot-robot fournit une base pour construire des politiques meilleure réponse dans un cadre partiellement observable et multi-agent, base qui sert d'étape intermédiaire importante pour aborder les problèmes de collaboration homme-robot. De plus, pour chaque contribution, nous fournissons des algorithmes plus flexibles utilisant des modèles génératifs dont nous pensons qu'ils faciliteront la mise en œuvre de nos contributions à des applications du monde réel.
Abstract

In this thesis, using Markov decision models, we investigate high-level decision-making (task-level planning) for robotics in two aspects: robot-robot collaboration and human-robot collaboration.

In robot-robot collaboration (RRC), we study the decision problems of multiple robots in-
volved to achieve a shared goal collaboratively, and we use the decentralized partially observable
Markov decision process (Dec-POMDP) framework to model such RRC problems. Then, we pro-
pose two novel algorithms for solving Dec-POMDPs. The first algorithm (Inf-JESP) finds Nash
equilibrium solutions by iteratively building the best-response policy for each agent until no
improvement can be made. To handle infinite-horizon Dec-POMDPs, we represent each agent's
policy using a finite-state controller. The second algorithm (MC-JESP) extends Inf-JESP with
generative models, which enables us to scale up to large problems. Through experiments, we
demonstrate our methods are competitive with existing Dec-POMDP solvers.

In human-robot collaboration (HRC), we can only control the robot, and the robot faces un-
certain human objectives and induced behaviors. Therefore, we attempt to address the challenge
of deriving robot policies in HRC, which are robust to the uncertainties about human behaviors.
In this direction, we discuss possible mental models that can be used to model humans in an HRC
task. We propose a general approach to derive, automatically and without prior knowledge, a
model of human behaviors based on the assumption that the human could also control the robot.
From here, we then design two algorithms for computing robust robot policies relying on solving
a robot POMDP, whose state contains the human's internal state. The first algorithm operates
offline and gives a complete robot policy that can be used during the robot's execution. The
second algorithm is an online method, i.e., it plans the robot's action at each time step during
execution. Compared with the offline approach, the online method only requires a generative
model and thus can scale up to large problems. Experiments with synthetic and real humans
are conducted in a simulated environment to evaluate these algorithms. We observe that our
methods can provide robust robot decisions despite the uncertainties over human objectives and
behaviors.

In this thesis, our research for RRC provides a foundation for building best-response policies
in a partially observable and multi-agent setting, which serves as an important intermediate step
for addressing HRC problems. Moreover, we provide more flexible algorithms using generative
models in each contribution, and we believe this will facilitate applying our contributions to
real-world applications.
Acknowledgements

I would like first to thank my supervisors, Olivier Buffet, Vincent Thomas, and Francis Colas.
We have worked together since my master's internship and then my Ph.D. at INRIA Nancy.
Without their help and guidance, this thesis would not have existed.

I want to thank all my committee members for coming to my defense and sharing insightful
perspectives. In particular, I want to thank Rachid Alami for providing the necessary ideas for
human-robot collaboration experiments at the beginning of my Ph.D.

I want also to thank all my friends who supported me during my thesis, especially Danlei
Zhang, Abir Bouaouda, Aya Yaacoub and Nima Mehdi.

Finally, I want to sincerely thank my parents, especially my mother, who cares about me
every day when I live and study abroad.
# Contents

## Résumé

## Abstract

## Acknowledgements

### Chapter 1

#### Introduction

1

<table><tr><td>1.1</td><td>Motivation and Research Questions</td><td>1</td></tr><tr><td>1.2</td><td>Overview of Robot-Robot Collaboration</td><td>2</td></tr><tr><td>1.2.1</td><td>Planning for Single-Agent Settings</td><td>3</td></tr><tr><td>1.2.2</td><td>Planning for Multi-Agent Settings</td><td>4</td></tr><tr><td>1.3</td><td>Overview of Human-Robot Collaboration</td><td>4</td></tr><tr><td>1.3.1</td><td>Robot Decision-Making in HRC</td><td>6</td></tr><tr><td>1.4</td><td>Contribution</td><td>7</td></tr><tr><td>1.5</td><td>Outline</td><td>8</td></tr></table>

### Chapter 2

#### Background

9

<table><tr><td>2.1</td><td>frameworks for Sequential Decision Making</td><td>9</td></tr><tr><td>2.2</td><td>Markov Decision Process (MDP)</td><td>9</td></tr><tr><td>2.2.1</td><td>Performance Measurement</td><td>10</td></tr><tr><td>2.2.2</td><td>Optimization Algorithms</td><td>11</td></tr><tr><td></td><td>Dynamic Programming Methods</td><td>11</td></tr><tr><td></td><td>Value Iteration:</td><td>12</td></tr><tr><td></td><td>Policy Iteration:</td><td>12</td></tr><tr><td></td><td>Sampling-Based Methods</td><td>12</td></tr><tr><td>2.2.3</td><td>Categorization of the Offline and Online Planning</td><td>14</td></tr><tr><td>2.3</td><td>Partially Observable Markov Decision Process (POMDP)</td><td>15</td></tr></table>
<table><tr><td>2.3.1 History-Based Policy</td><td>17</td></tr><tr><td>Policy Trees</td><td>17</td></tr><tr><td>Finite State Controllers</td><td>17</td></tr><tr><td>2.3.2 Belief-Based Policy</td><td>18</td></tr><tr><td>α-vectors</td><td>18</td></tr><tr><td>2.3.3 Optimization Algorithms</td><td>19</td></tr><tr><td>Point-Based Method</td><td>19</td></tr><tr><td>Sampling-Based Method</td><td>20</td></tr><tr><td>2.3.4 Multi-Agent POMDP</td><td>22</td></tr><tr><td>2.4 Decentralized Partially Observable Markov Decision Process (Dec-POMDP)</td><td>22</td></tr><tr><td>2.5 Solving Dec-POMDPs by finding Nash Equilibria</td><td>23</td></tr><tr><td>2.6 Conclusion</td><td>24</td></tr></table>

## Chapter 3

### Related Work on Multi-Agent Decision Making 25

<table><tr><td>3.1 Dec-POMDPs' overview</td><td>25</td></tr><tr><td>3.2 Policy Search in Dec-POMDPs</td><td>26</td></tr><tr><td>3.2.1 Multi-Agent A*</td><td>26</td></tr><tr><td>3.2.2 Expectation-Maximization (EM) for Dec-POMDPs</td><td>27</td></tr><tr><td>3.2.3 Conclusion</td><td>28</td></tr><tr><td>3.3 Transforming Dec-POMDPs into (PO)MDPs</td><td>28</td></tr><tr><td>3.3.1 Feature Based HSVI</td><td>29</td></tr><tr><td>3.3.2 PBVI-BB</td><td>30</td></tr><tr><td>Conclusion</td><td>30</td></tr><tr><td>3.4 Finding Nash Equilibria in Dec-POMDPs</td><td>30</td></tr><tr><td>3.4.1 JESP</td><td>31</td></tr><tr><td>3.4.2 Bounded Policy Iteration for Dec-POMDPs (Dec-BPI)</td><td>31</td></tr><tr><td>Conclusion</td><td>31</td></tr><tr><td>3.5 Solving Dec-POMDPs with a generative model</td><td>32</td></tr><tr><td>3.5.1 Monte-Carlo Expectation Maximization (MCEM) based algorithms for solving Dec-POMDPs</td><td>32</td></tr><tr><td>3.5.2 Occupancy-State SARSA (oSARSA):</td><td>32</td></tr><tr><td>3.6 Conclusion</td><td>32</td></tr></table>

## Chapter 4

### Searching for an Equilibrium in an Infinite-Horizon Multi-agent Problem 35

<table><tr><td>4.1 Infinite-Horizon JESP</td><td>36</td></tr></table>
<table>
  <tbody>
    <tr>
      <td>4.1.1</td>
      <td>Inf-JESP Main Algorithm</td>
      <td>36</td>
    </tr>
    <tr>
      <td></td>
      <td>Properties</td>
      <td>37</td>
    </tr>
    <tr>
      <td>4.1.2</td>
      <td>Building Best-Response POMDP for Agent <i>i</i></td>
      <td>38</td>
    </tr>
    <tr>
      <td>4.1.3</td>
      <td>Building Agent <i>i</i>'s FSC with bounded size</td>
      <td>39</td>
    </tr>
    <tr>
      <td>4.1.4</td>
      <td>Heuristic Initialization</td>
      <td>42</td>
    </tr>
    <tr>
      <td></td>
      <td>MPOMDP-based Stochastic Initial FSC (M-S)</td>
      <td>42</td>
    </tr>
    <tr>
      <td></td>
      <td>MPOMDP-based Deterministic Initial FSC (M-D)</td>
      <td>42</td>
    </tr>
    <tr>
      <td></td>
      <td>MPOMDP-based Average-Belief Initial FSC (M-A)</td>
      <td>43</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>Monte-Carlo JESP</td>
      <td>44</td>
    </tr>
    <tr>
      <td>4.2.1</td>
      <td>Building Best Response Generative Model for Agent <i>i</i></td>
      <td>45</td>
    </tr>
    <tr>
      <td></td>
      <td>Algorithm Description:</td>
      <td>45</td>
    </tr>
    <tr>
      <td>4.2.2</td>
      <td>Computing Agent <i>i</i>'s FSC using Monte Carlo Methods</td>
      <td>45</td>
    </tr>
    <tr>
      <td></td>
      <td>Algorithm Description:</td>
      <td>46</td>
    </tr>
    <tr>
      <td>4.2.3</td>
      <td>Main Algorithm and Initialization</td>
      <td>47</td>
    </tr>
    <tr>
      <td></td>
      <td>Main Algorithm:</td>
      <td>47</td>
    </tr>
    <tr>
      <td></td>
      <td>Heuristic Initialization:</td>
      <td>47</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>Experiments</td>
      <td>47</td>
    </tr>
    <tr>
      <td>4.3.1</td>
      <td>Evaluation of Inf-JESP</td>
      <td>49</td>
    </tr>
    <tr>
      <td></td>
      <td>Algorithm settings</td>
      <td>49</td>
    </tr>
    <tr>
      <td></td>
      <td>Comparison with state-of-the-art algorithms</td>
      <td>50</td>
    </tr>
    <tr>
      <td></td>
      <td>A Closer Look at Inf-JESP's behavior</td>
      <td>52</td>
    </tr>
    <tr>
      <td></td>
      <td>Complementary results</td>
      <td>52</td>
    </tr>
    <tr>
      <td></td>
      <td>Summary</td>
      <td>55</td>
    </tr>
    <tr>
      <td>4.3.2</td>
      <td>Evaluation of MC-JESP</td>
      <td>56</td>
    </tr>
    <tr>
      <td></td>
      <td>Algorithm settings</td>
      <td>56</td>
    </tr>
    <tr>
      <td></td>
      <td>Comparison with state-of-the-art algorithms</td>
      <td>56</td>
    </tr>
    <tr>
      <td></td>
      <td>A Closer Look at MC-JESP's behavior</td>
      <td>58</td>
    </tr>
    <tr>
      <td>4.4</td>
      <td>Conclusion and Perspectives</td>
      <td>58</td>
    </tr>
    <tr>
      <td>4.4.1</td>
      <td>Conclusion</td>
      <td>58</td>
    </tr>
    <tr>
      <td></td>
      <td>Inf-JESP</td>
      <td>58</td>
    </tr>
    <tr>
      <td></td>
      <td>MC-JESP</td>
      <td>61</td>
    </tr>
    <tr>
      <td>4.4.2</td>
      <td>Perspectives</td>
      <td>62</td>
    </tr>
    <tr>
      <td></td>
      <td>Influence of different parameters and possible optimizations</td>
      <td>62</td>
    </tr>
    <tr>
      <td></td>
      <td>Extending MC-JESP to continuous domains</td>
      <td>62</td>
    </tr>
    <tr>
      <td></td>
      <td>Evaluating the difficulty of a collaboration problem</td>
      <td>62</td>
    </tr>
    <tr>
      <td></td>
      <td>Solving Some Partially Observable Stochastic Games (POSGs)</td>
      <td>63</td>
    </tr>
  </tbody>
</table>
Chapter 5

Related Work on Task Planning for Human-Robot Collaboration

65

<table><tr><td>5.1 Overview of Task Planning in HRC</td><td>65</td></tr><tr><td>5.2 HRC with first-order mental model</td><td>66</td></tr><tr><td>Planned human policy inside a robot POMDP</td><td>67</td></tr><tr><td>Other related works</td><td>68</td></tr><tr><td>Limitations of 1oMMs for HRC</td><td>68</td></tr><tr><td>How to Derive a 1oMM of the human</td><td>68</td></tr><tr><td>5.3 HRC with Second-order Mental Model</td><td>69</td></tr><tr><td>Reasoning about Others</td><td>69</td></tr><tr><td>Comparison with 1oMMs</td><td>70</td></tr><tr><td>5.4 HRC with Shared Mental Model</td><td>70</td></tr><tr><td>Human-Robot Cross-Training</td><td>70</td></tr><tr><td>Cooperative Inverse Reinforcement Learning</td><td>70</td></tr><tr><td>Pros and Cons</td><td>71</td></tr><tr><td>5.5 Conclusion</td><td>71</td></tr></table>

Chapter 6

Robust Decision Making for Human-Robot Collaboration

73

<table><tr><td>6.1 Offline Robust Planning for HRC</td><td>74</td></tr><tr><td>6.1.1 Generating Human Stochastic FSCs with a Bounded Size</td><td>75</td></tr><tr><td>Sampling a Stochastic Human FSC</td><td>76</td></tr><tr><td>Sampling a Deterministic Human FSC</td><td>78</td></tr><tr><td>6.1.2 Building a robot best response policy</td><td>78</td></tr><tr><td>6.2 Online Robust Planning for HRC</td><td>80</td></tr><tr><td>6.2.1 Robot Extended Generative Model</td><td>81</td></tr><tr><td>6.2.2 Online Main Algorithm</td><td>83</td></tr><tr><td>6.3 Experiments</td><td>84</td></tr><tr><td>6.3.1 Experiments with Synthetic Humans – Offline Algorithm</td><td>86</td></tr><tr><td>Qualitative results</td><td>86</td></tr><tr><td>Robustness Analysis</td><td>88</td></tr><tr><td>6.3.2 Experiments with Synthetic Humans – Online Algorithm</td><td>89</td></tr><tr><td>6.3.3 Real Human Experiments</td><td>90</td></tr><tr><td>Qualitative results</td><td>91</td></tr><tr><td>Quantitative results</td><td>93</td></tr><tr><td>6.4 Conclusion</td><td>94</td></tr><tr><td>6.5 Perspectives</td><td>95</td></tr></table>
List of Figures

<table>
  <tbody>
    <tr>
      <td>1.1</td>
      <td>An illustration of the Flying Co-Worker project scenario: a flying drone equipped with an end effector delivers tools for the workers in a working space.</td>
      <td>2</td>
    </tr>
    <tr>
      <td>1.2</td>
      <td>An illustration of the coordination issue for the robot in HRC. The human and robot need to repair all the broken devices (top left and top right ones). They can repair one device if and only if they are in the same cell and performing repairing actions simultaneously.</td>
      <td>6</td>
    </tr>
    <tr>
      <td>2.1</td>
      <td>Markov decision process illustration: the agent chooses an action <i>a</i> at state <i>s</i>, will have a reward <i>r</i> and reach next state <i>s'</i>.</td>
      <td>10</td>
    </tr>
    <tr>
      <td>2.2</td>
      <td>Diagram about Monte-Carlo Tree Search.</td>
      <td>14</td>
    </tr>
    <tr>
      <td>2.3</td>
      <td>An illustration of the offline and online approaches [Ross et al., 2008].</td>
      <td>15</td>
    </tr>
    <tr>
      <td>2.4</td>
      <td>Partially observable Markov decision process.</td>
      <td>16</td>
    </tr>
    <tr>
      <td>2.5</td>
      <td>Two example representations of POMDP policies: (a) policy tree; (b) finite state controller [Amato, 2010].</td>
      <td>18</td>
    </tr>
    <tr>
      <td>3.1</td>
      <td>An illustration of the Expectation-Maximization (EM) algorithm [Do and Bat-zoglou, 2008].</td>
      <td>29</td>
    </tr>
    <tr>
      <td>3.2</td>
      <td>An overview of representative algorithms for Dec-POMDPs: The area colored with light green gives the methods based on transforming Dec-POMDPs to (PO)MDPs with sufficient statistics; The light pink area contains algorithms that directly search in the joint policy space; Algorithms that find Nash equilibrium solutions are presented inside the light blue area. All those methods are also categorized with the temporal horizons (finite or infinite) and model types (explicit model or generative model).</td>
      <td>34</td>
    </tr>
    <tr>
      <td>4.1</td>
      <td>JESP's iterative optimization process for a 2-agent problem, starting with policies <i>&pi;</i><sub>1</sub> and <i>&pi;</i><sub>a</sub></td>
      <td>36</td>
    </tr>
    <tr>
      <td>4.2</td>
      <td>An illustration of the best-response POMDP for agent <i>i</i> based on the Dec-POMDP model and other agents' fixed FSCs.</td>
      <td>40</td>
    </tr>
    <tr>
      <td>4.3</td>
      <td>Structure of the best-response generative model <i>G</i><sub>BR</sub>: The black arrows are the inputs and outputs of the POMDP generative model; The blue arrows show the inputs and outputs of a Dec-POMDP simulator <i>G</i>; The green arrows show the evolution of agents ≠ <i>i</i>' FSCs.</td>
      <td>46</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>4.4</td>
      <td>Values of the joint policy for the Dec-Tiger, Grid and Recycling problems (from top to bottom). The left part of each figure presents the evolution (during a run) of the value of the joint policy at each iteration of: IJ(R-1) (avg + 10th and 90th percentiles in blue), and the deterministic IJ(M-D) (in red) and IJ(M-S) (in green). The dashed line represents FB-HSVI's final value. The right part presents the value distribution after convergence of IJ(R-1).</td>
      <td>53</td>
    </tr>
    <tr>
      <td>4.5</td>
      <td>Effect of the state elimination for the Dec-Tiger, Grid and Recycling problems (from left to right). Each figure plots, for each Best-Response POMDP obtained while executing Inf-JESP(R-1<sub>1</sub>), the number of states of that POMDP after state elimination as a function of that number before state elimination.</td>
      <td>54</td>
    </tr>
    <tr>
      <td>4.6</td>
      <td>Sizes of the final FSCs obtained with Inf-JESP(R-1<sub>1</sub>) after convergence for the Dec-Tiger, Grid and Recycling problems (from left to right). Each dot corresponds to a pair containing the sizes of both agents' FSCs.</td>
      <td>54</td>
    </tr>
    <tr>
      <td>4.7</td>
      <td>Sum of the sizes of the final FSCs obtained with Inf-JESP(R-1<sub>1</sub>) after convergence as a function of the required number of iterations for the Dec-Tiger, Grid and Recycling problems (from left to right).</td>
      <td>55</td>
    </tr>
    <tr>
      <td>4.8</td>
      <td>Value of the final FSCs obtained with Inf-JESP(R-1<sub>1</sub>) after convergence as a function of the required number of iterations for the Dec-Tiger, Grid and Recycling problems (from left to right).</td>
      <td>55</td>
    </tr>
    <tr>
      <td>4.9</td>
      <td>Value of the final FSCs obtained with Inf-JESP(R-1<sub>1</sub>) after convergence as a function of the sum of the sizes of final FSCs for the Dec-Tiger, Grid and Recycling problems (from left to right).</td>
      <td>55</td>
    </tr>
    <tr>
      <td>4.10</td>
      <td>Values of the joint policy for the Dec-Tiger, Grid and Recycling problems (from top to bottom). The left part of each figure presents the evolution (during a run) of the value of the joint policy at each iteration of MC-JESP(1<sub>20</sub>) (avg + 10th and 90th percentiles) with different bounded FSC sizes (10, 30, and 50, respectively). The dashed line represents FB-HSVI's final value. The right part presents the value distribution after convergence of MC-JESP(1<sub>20</sub>).</td>
      <td>59</td>
    </tr>
    <tr>
      <td>4.11</td>
      <td>Values of the joint policy for the Box-Pushing and Mars Rovers problems (from top to bottom). The left part of each figure presents the evolution (during a run) of the value of the joint policy at each iteration of MC-JESP(1<sub>20</sub>) (avg + 10th and 90th percentiles) with different bounded FSC sizes (10, 30, and 50, respectively). The dashed line represents FB-HSVI's final value. The right part presents the value distribution after convergence of MC-JESP(1<sub>20</sub>).</td>
      <td>60</td>
    </tr>
    <tr>
      <td>4.12</td>
      <td>Values of the joint policy for the Dec-Tiger problem. The x-axis indicates the different POMDP timeout used when building the FSC node in the MC-JESP algorithm. The y-axis represents the final value obtained through the MC-JESP method.</td>
      <td>61</td>
    </tr>
    <tr>
      <td>4.13</td>
      <td>An illustration of Markov decision models and POSGs: MDP is a subset of POMDP, which is again a subset of Dec-POMDP. Dec-POMDP is a special case of POSG, in which all agents share a same reward function.</td>
      <td>63</td>
    </tr>
    <tr>
      <td>5.1</td>
      <td>An illustration of the three types of mental models: first-order mental model (1oMM), second-order mental model (2oMM), and shared mental model (SMM).</td>
      <td>66</td>
    </tr>
    <tr>
      <td>5.2</td>
      <td>A collaborative collecting task [Karami et al., 2009]: In the grid-world environment, there are three objects I<sub>1</sub>, I<sub>2</sub>, and I<sub>3</sub>. The human and the robot need to collect them to the box at the top right corner.</td>
      <td>67</td>
    </tr>
    <tr>
      <td>5.3</td>
      <td>The high-level process of the robot decision system [Karami, 2011]</td>
      <td>68</td>
    </tr>
  </tbody>
</table>
<table>
  <tbody>
    <tr>
      <td>6.1</td>
      <td>A comparison of two 2oMMs: (a) the first 2oMM has a chicken-and-egg issue with an infinite loop of considerations; (b) the robot in the second one assumes that the considered human behaves according to an SMM.</td>
      <td>74</td>
    </tr>
    <tr>
      <td>6.2</td>
      <td>The structure of the offline robust robot planning algorithm</td>
      <td>75</td>
    </tr>
    <tr>
      <td>6.3</td>
      <td>Structure of the extended generative model G<sub>e</sub> for the robot: The black arrows are the inputs and outputs of the robot's extended generative model; The blue arrows show the inputs and outputs of a Dec-POMDP simulator G; The green arrows show the evolution of the human model.</td>
      <td>82</td>
    </tr>
    <tr>
      <td>6.4</td>
      <td>A collaboration task: A robot and a human evolve in a 4 × 3 grid world. The top-left cell (0,0) and the top-right cell (3,0) both contain a broken device. A device to be maintained is also located in cell (1,0). A toolbox is located in cell (2,2) where the human can pick components.</td>
      <td>86</td>
    </tr>
    <tr>
      <td>6.5</td>
      <td>An illustration of the uncertainties about the human behavior in this HRC task: 1. Uncertainty on the human objective (presented with blue and orange colors); 2. Uncertainty on human behaviors (different trajectories)</td>
      <td>87</td>
    </tr>
    <tr>
      <td>6.6</td>
      <td>A screenshot of the human-robot collaboration game: The top part illustrates the current environment state for the human player; The middle part provides information on available human actions; The bottom part is a legend explaining how to read the map. In each time step, the top part will refresh according to the executed human and robot actions.</td>
      <td>91</td>
    </tr>
    <tr>
      <td>6.7</td>
      <td>All subjects' evaluations regarding both players' adaptation during the collaboration task for each robot policy.</td>
      <td>92</td>
    </tr>
    <tr>
      <td>6.8</td>
      <td>All subjects' choices when asked to pick the robot policy they preferred at the end of the experiments.</td>
      <td>93</td>
    </tr>
    <tr>
      <td>6.9</td>
      <td>Each subject's number of successes when he or she collaborates with different robot policies.</td>
      <td>94</td>
    </tr>
    <tr>
      <td>A.1</td>
      <td>(top left) Standard POMDP dependencies, including intermediate variables used to compute the transition function (only); and candidate Best-Response POMDP formalizations with: (top right) e<sub>i</sub><sup>t</sup> def = &lt;s<sup>t</sup>, n<sub>&ne;i</sub><sup>t</sup>&gt;, (bottom left) e<sub>i</sub><sup>t</sup> def = &lt;s<sup>t</sup>, n<sub>&ne;i</sub><sup>t</sup>, o<sub>i</sub><sup>t</sup>&gt;, and (bottom right) e<sub>i</sub><sup>t</sup> def = &lt;s<sup>t</sup>, n<sub>&ne;i</sub><sup>t-1</sup>, o<sub>&ne;i</sub><sup>t</sup>&gt;.</td>
      <td>104</td>
    </tr>
  </tbody>
</table>
# Introduction

## 1.1 Motivation and Research Questions

Collaborative robots are widely used in modern society in various domains. For example, in agriculture, a robot can work as a sprayer to help farmers get rid of harmful insects [Berenstein and Edan, 2012]; in daily life, robots provide services in hospitals for therapeutic programs and guide passengers in airports [Tapus et al., 2007, Triebel et al., 2016]; in industry, robots are used to lift heavy objects, perform high-precision manipulations, or collaborate with human workers [Vysocky and Novak, 2016]. We can mainly categorize these robot collaboration applications into:

* Robot-Robot Collaboration (RRC): multiple robots are involved together to collaboratively achieve a task or a specified goal;

* Human-Robot Collaboration (HRC): Humans and robots work together cooperatively; usually, a goal is specified by human users or linked to humans' objectives.

This thesis is funded by the ANR project *Flying Co-Worker*, an aerial manipulator robot that acts as a teammate of a human worker to realize complex tasks. As shown in Figure 1.1, one possible scenario is that two workers are in a working space, and a flying drone is designed to deliver tools between workers. In this thesis, we are interested in the robot's decision-making system in a broader view in both RRC and HRC. In other words, we investigate how the robot should decide on its actions in order to achieve a task, no matter whether the partners are humans or other robots. We focus on sequential decision-making as the collaboration tasks take multiple time steps to accomplish, so we search for policies to maximize the team's global performance. Those policies indicate what actions the agents should perform for each condition they encounter. Moreover, one can decompose the decision-making process hierarchically into low-level and high-level decisions [Cacace et al., 2015], here (in robotics) with low-level decisions corresponding to low-level control, i.e., motor commands, and high-level decision <fnref n="1" /> corresponding to task-planning, i.e., deciding to “pick an object”, “repair a device”. Our thesis focuses on the high-level decision (hence task-planning) for robotics in both RRC and HRC.

However, the research questions raised by task planning in RRC and HRC are different due to their different features. In RRC, we assume that we can assign policies for all robots, and then they behave independently in the environment. Thus, we investigate how to design algorithms that compute optimal policies for each agent to maximize the overall performance. On the other

<footnote n="1">¹In robotics, a high-level decision will eventually compile to low-level controls. Thus, the high-level decision making is (in a sense) about decomposing the original problem into sub-problems.</footnote>
<figure><img src="image_4.png" /><figcaption>Figure 1.1: An illustration of the Flying Co-Worker project scenario: a flying drone equipped with an end effector delivers tools for the workers in a working space.</figcaption></figure>

hand, in HRC, only the robot can be controlled but not the human (in this thesis, we assume there is one human and one robot in an HRC team). Therefore, the challenge is to design a decision-making system only for the robot, and it should adapt to the human behaviors regarding his objectives in order to achieve the collaboration task.

## 1.2 Overview of Robot-Robot Collaboration

A multi-agent system (MAS) defines a set of individual agents that work collaboratively to solve problems such as electric grids, sensor networks, or intelligent transportation. In this sense, the robots in a robot-robot collaboration (RRC) task make up a MAS since they work together to achieve a shared goal. One can use Markov decision models to formalize sequential decision-making problems in the MAS setting. The key feature of Markov decision models is the Markov property, i.e., the system's next state only depends on the current state and the executed action [Bellman, 1957]. Among all the Markov decision models, the Markov decision process (MDP) is the most basic one for single-agent problems. It addresses a sequential decision-making problem by formalizing a controllable agent in its environment with discrete time, stochastic dynamics, and fully observable states. The *partially observable Markov decision process* (POMDP) is a generalization of the MDP. It models one agent's decision process in the same way as an MDP. However, the agent in a POMDP cannot directly observe the true world state but only partial or noisy information. The *decentralized partially observable Markov decision process* (Dec-POMDP) [Bernstein et al., 2002] extends POMDPs to the multi-agent setting. The objective of solving a Dec-POMDP is to derive strategies for all agents to achieve a common task. Overall, the Dec-POMDP is the most general framework among all Markov decision models, and it fits the multi-agent and collaboration setting for RRC problems in this thesis.

In terms of solving techniques, there are mainly two approaches: reinforcement learning (RL) and planning. RL is about learning the optimal behavior to maximize a numerical reward signal by trial and error through interactions with the environment [Sutton and Barto, 2018]. One can distinguish “offline” RL (with 2 phases: training and execution) and “online” RL (with a single phase where one learns directly in the real world). In both cases, RL methods do not need a complete problem model but only a black-box simulator (typically offline RL) or even just the
real environment (typically online RL). On the other hand, planning methods usually rely on a
complete problem model. Unlike RL approaches, where the agent interacts with the environment
to gather information, planning methods can often directly use the model information to compute
optimal policies. In this thesis, we would like to have a generic method taking advantage of the
model of the task, we thus investigate the planning approaches to design the robot decision-
making system.

To reduce ambiguities, we need to emphasize that we focus on the high-level, sequential
decision-making problems, and the planning methods in our context are related to the Markov
models.

1.2.1 Planning for Single-Agent Settings

Before introducing planning methods for multi-agent decision-making, we first look at planning
in a single-agent case. Generally, single-agent problems are often modeled using MDPs if the
environment state is fully observable or POMDPs if the underlying state cannot be directly
observed. In our thesis, we won't directly use MDPs or POMDPs for modeling the RRC problems
since they are designed for single-agent decisions. However, in HRC, the robot's decision could
be modeled using POMDPs because of its limited observations, and because we cannot control
the human but only the robot.

The planning methods for solving such single-agent problems can be classified into two types: model-based or simulator-based. Model-based planning methods require an explicit model of the problem, which means that the dynamics of the environment should be known, including how the environment state evolves, and how the environment is perceived if it is not fully observable. Classic model-based planning methods such as *value iteration* and *policy iteration* for MDPs are also the foundations of RL algorithms [Bellman, 1957, Howard, 1960], and state-of-the-art model-based planning algorithms such as HSVI [Smith and Simmons, 2004] and SARSOP [Kurniawati et al., 2008] can give ε-optimal solutions for POMDPs. However, for some large-scale problems, such as planning in an urban environment [Delamer et al., 2019], building explicit models is difficult since it will cost a lot of memory to represent the full dynamics. Moreover, exact computations may be too costly (at least regarding CPU time), so sampling-based methods can be a good solution in large-scale problems. Sampling-based planning approaches [Metropolis and Ulam, 1949, Silver and Veness, 2010] only require a black-box simulator which takes inputs of the current state and executed action, then gives the next state, agent's observation and instant reward as outputs.

One can also distinguish single-agent planning algorithms into two types: offline and online planning. Offline planning contains two steps: policy construction and policy execution. In the policy construction phase, an optimal policy is computed which contains the best actions for all possible situations. This optimal policy will then be executed in the execution phase. Unlike offline planning, online planning methods [Ross et al., 2008, Metropolis and Ulam, 1949, Silver and Veness, 2010] interleave the planning and execution processes. In the planning phase, online algorithms try to find the best action given the current situation within a bounded memory or time budget. Then, when the planning phase terminates, the agent performs this action in the execution phase and updates its information state in order to launch the next plan. Compared with offline planning, online planning can better fit applications with fixed time constraints and non-stationary environments [Chatzis and Kosmopoulos, 2014, Lecarpentier and Rachelson, 2019]. In those cases, using offline methods to enumerate all possible situations is computationally infeasible. However, if enough resources and time are given, offline methods [Smith and Simmons, 2004, Kurniawati et al., 2008] will converge to near-optimal solutions.
1.2.2 Planning for Multi-Agent Settings

For multi-agent planning, the purpose is to compute optimal policies for each agent in order to
achieve the common goal. As in the single-agent setting, we divide current multi-agent planning
algorithms into mainly two categories:

* Explicit model-based algorithms: This approach requires an explicit model of the multi-agent problem, including the environment dynamics and reward function. Then, using the model knowledge, optimal or suboptimal policies for each agent are computed by using heuristic search [Szer et al., 2005, Dibangoye et al., 2016], parameters optimizations [Bernstein et al., 2009] or finding Nash-equilibrium solutions [Nair et al., 2003, You et al., 2021a];

* Simulator-based (sampling-based) algorithms: in this case, algorithms [Wu et al., 2013, Liu et al., 2015, Dibangoye and Buffet, 2018] do not need an explicit model, but a black-box simulator, with which agents can interact and receive observations and rewards.

Compared with the single-agent setting, multi-agent decision-making brings more challenges in
several aspects. First, agents usually have limited access to the environment and cannot observe
the exact status of other agents. Thus it is difficult for the agents to coordinate their behaviors
only based on local observations. Second, the complexity of computation grows exponentially
with the number of agents. Therefore, scalability is also an issue for multi-agent decision-making.
In this thesis, we will give more details regarding the models and theories in Chapter 2 and
related algorithms in Chapter 3. Our contributions in both explicit model-based and simulator-
based planners for solving multi-agent problems modeled with Dec-POMDPs are presented in
Chapter 4.

1.3 Overview of Human-Robot Collaboration

In the previous section, we briefly introduced Robot-Robot Collaboration (RRC) and related
decision-making methods. In this section, we introduce *Human-Robot Collaboration* (HRC),
which has emerging applications in recent years, such as in manufacturing [Zanchettin et al.,
2016, Guerin et al., 2015, Wang et al., 2017, Zanchettin and Rocco, 2013] and healthcare [Tapus
et al., 2009, Jacob et al., 2013]. In HRC, a collaborative team of humans and robots work to-
gether to achieve a shared goal. HRC is also part of the broader field of human-robot interaction
(HRI), where the various partners do not necessarily benefit from the interaction [Bauer et al.,
2008]. Here, let us summarize some dimensions and challenges in HRC:

* Robot design: To enable a successful collaboration between the human and robot, the first step is to study how to design the robot, which involves the following aspects:

- Robot appearance: The human's acceptability to the robot partner varies because of the robot appearance [Walters et al., 2008, Mori, 2012], which will affect the human's attention, effectiveness during a collaboration task Goetz et al. [2003], Walters et al. [2009], Kwak [2014]. Thus, one important topic is how to design the robot's appearance.

- Hardware and software: HRC tasks require the robot to provide different kinds of service or assistance to the human partner. In response to those requirements, the robot should be equipped with appropriate hardware [Wang et al., 2019, Khalid et al., 2016] such as smart sensors [Schmidt and Wang, 2014, Wang, 2015] to detect human
behaviors, and software such as tools to facilitate programming of collaborative robots
[Mokaram et al., 2017].

- Interface and communication: In HRC, the human user should feel easy to interact and communicate with the robot [Villani et al., 2018]. This requires properly designed user interfaces such as providing augmented reality [Tian and Paulos, 2021] or virtual reality [Wang et al., 2019] to illustrate the robot status, and enabling remote operation with dedicated tools [Lv et al., 2020, Wang et al., 2019].

Safety: In HRC, human safety is a fundamental prerequisite, especially for industrial applications. To ensure safe interactions between humans and robots in a shared workspace, one particular research question is collision avoidance. To do so, it is important to detect human movements and identify potential risks, such as a human approaching within a danger range. There are multiple ways to detect human movements, such as using depth cameras [Nascimento et al., 2020, Mohammed et al., 2017] and laser scanners [Safeea and Neto, 2019]. Moreover, to increase the detection precision, methods such as data fusion have been applied in order to efficiently use multiple sensors' data [Lin et al., 2020]. After potential risks have been detected, the robot should take appropriate reactions such as emergency stops or changing its moving direction [Nascimento et al., 2020] to prevent collisions.

The outcome of such research on safety may lead to new industrial standards. Up to now, standards have been established to ensure the safety of collaborative robots mainly in the industry, such as ISO 13850, 13851, 10218-1/2 [Villani et al., 2018]. Those safety standards define the requirements and design guidelines for developing robot systems in HRC. For example, ISO 10218-1/2 [ISO 10218-1:2011, ISO 10218-2:2011] identify four collaborative modes including *safety-rate monitored stop, hand guiding, speed and separation monitoring, power, and force limiting*, and list required robot functionalities to ensure safety. In the future, more standards will be created with the increased usage of collaborative robots in domains like home service [Taipalus and Kosuge, 2005] and healthcare [Tapus et al., 2009, Jacob et al., 2013].

* Robot autonomy: In HRC, the robot autonomy can be roughly divided into two parts, *perception system* and *decision system*, as follows:

- Perception system: In HRC, robot sensors receive signals from the environment and the human partner. Thus, one issue is how to let the robot understand those signals and make use of them. To answer this question, multiple techniques have been applied in HRC, such as using histogram of oriented gradients (HOG), support vector machines (SVM), or convolutional neural networks (CNN) for image recognition [Feng and Yuan, 2013, Zhao et al., 2019]; processing IMU's data through hidden Markov model (HMM) [Roitberg et al., 2014, Wang et al., 2018]; and using data fusion techniques to analyze multi-sensor data [Lin et al., 2020]. Recently, deep learning has made great progress, especially in the machine vision domain, with deep learning methods outperforming human experts' accuracy for classification tasks. Therefore, state-of-the-art deep learning methods such as YOLOv5 [Jocher, 2020] have been introduced to HRC applications [Liau and Ryu, 2021] as powerful tools for motion and gesture detection.

- Decision system: The core of the robot's autonomy is its decision system. It reflects how the robot adapts to different situations and assists the human partner with appro-
<figure><img src="image_5.png" /><figcaption>Figure 1.2: An illustration of the coordination issue for the robot in HRC. The human and robot need to repair all the broken devices (top left and top right ones). They can repair one device if and only if they are in the same cell and performing repairing actions simultaneously.</figcaption></figure>

priate decisions. In classical planning, the robot plans its actions considering temporal and domain constraints and controls executions in real time [Alami et al., 1998]. To handle tasks with uncertain environments, many works [Zheng et al., 2018, Görür et al., 2018, Unhelkar et al., 2020, Nikolaidis et al., 2017, Chen et al., 2018] also use Markov decision models to represent the robot decision framework in HRC. For example, Nikolaidis et al. proposed a robot decision framework for a collaborative grasping task based on a POMDP [Nikolaidis et al., 2017]. Since human has different statuses during the task and evolves over time, Nikolaidis et al. define the human’s status as a part of the state and integrate human status dynamics inside the POMDP’s transition function. Therefore, the robot could update its belief on the human status from observed human actions. Then, solving this POMDP would result in a robot decision solution (robot policy) considering human behaviors. Moreover, other methods such as imitation learning [Lee et al., 2011] and reinforcement learning [Liu et al., 2021] can be also used in HRC.

Among those research directions, in this thesis, we focus on robot decision-making for HRC.

### 1.3.1 Robot Decision-Making in HRC

HRC brings more challenges for the robot’s decision-making compared with RRC. Unlike RRC, which specifies all agents’ behaviors, the human partner in HRC cannot be controlled, and his intention and future behaviors are often hidden from the robot. Thus, a real challenge for the robot is how to make decisions on its behavior to coordinate with the human. Here we use a simple example to explain this challenge, as shown in Figure 1.2, where two broken devices are located on the top left and top right corners of the map. The goal is to repair all the broken devices. In RRC, this is an easy problem since we can directly control two agents and move them to the broken devices’ locations together and do the repair simultaneously. However, in HRC, the robot does not know which device the human wants to repair first. Thus the robot needs to observe the human behavior to infer his intention. Moreover, humans are not fully rational, and their behaviors can be uncertain due to multiple factors such as emotions and fatigue. Therefore, in this simple example, humans could have different paths to broken devices, some of which may be erratic. For example, a human may go left first, wait for a while, return to his original position, and then head to the top-left broken device. From the robot’s point of view, to make correct decisions, all those uncertainties must be considered.

As we previously mentioned, many researchers [Zheng et al., 2018, Görür et al., 2018, Unhelkar
et al., 2020, Nikolaidis et al., 2017, Chen et al., 2018] rely on Markov decision models, especially using the POMDP framework to represent the robot decision-making for HRC, and a human model [Nikolaidis et al., 2017] is usually integrated as parts of the environment dynamics. By doing so, the robot could reason about its actions considering possible human behaviors and following consequences. However, to have such human models, expert knowledge or collected data in specific domains are usually required [Nikolaidis et al., 2017, Chen et al., 2018].

In this thesis, we also rely on Markov decision models to design the robot decision for HRC.
We investigate and make contributions to the following challenges:

* How should the robot model the human partner in order to estimate his intention and behavior, this modeling process is automatically done by the robot, and it should be generic enough so that no expert knowledge and data are needed;

* How should the robot decide its own actions to coordinate with the human partner, the robot's decisions should be robust enough regarding the uncertainties of human intention and behavior.

We will give more details regarding the related works of robot decisions for HRC in Chapter 5 and our contributions for HRC are written in Chapter 6.

1.4 Contribution

We summarized the relations of main contributions in this thesis as in Table 1. The contribution in this thesis can be divided into two main parts (RRC and HRC).

For RRC, this thesis provides novel techniques for solving multi-agent decision problems modeled with Dec-POMDPs in which agents only have partial observations of the environment. More specifically, inspired by JESP [Nair et al., 2003], we would like to solve Dec-POMDPs by finding Nash equilibrum solutions. Thus, we iteratively optimize each agent's policy until no improvements can be made. Moreover, we address JESP's drawback that it can only solve finite-horizon problems because it uses policy trees. In our thesis, we use finite-state controllers to represent each policy, and we propose two novel algorithms (Inf-JESP and MC-JESP) for solving infinite-horizon Dec-POMDPs. These two contributions differ in that one uses an explicit model while the other uses a generative model. Through experiments on benchmark problems, we demonstrate the validity of our methods, which perform quite well compared to other existing Dec-POMDP solvers.

On the other hand, for human-robot collaboration, we focus on the robot's decision-making and aim to compute robot policies that are robust to uncertain human objectives and behaviors. Relying on Markov decision models, we provide a robust robot planning algorithm that relies on solving a POMDP where one hidden state variable corresponds to human behavior. However, human behaviors are usually uncertain and unknown to the robot. Unlike other approaches [Nikolaidis et al., 2017, Chen et al., 2018], which need expert knowledge or collected data to provide such a human model, we provide an approach to automatically generate an uncertain human behavior (a policy) for each human objective. Moreover, in our approach, the generated human model is not myopic, which can account for possible robot behaviors and consider long-term consequences. We distinguish two variants of this robust robot planning method. The first algorithm is based on knowing the explicit model of the collaboration task and computing a robust robot policy by estimating possible human behaviors. This method operates offline, so we first compute a robust robot policy and assign it to the robot before the actual execution. The second algorithm works online, and only a black box simulator is sufficient. To evaluate our
<table><caption>Table 1.1: Table of the relations about contributions</caption><thead><tr><th>Task Type</th><th>RRC</th><th>HRC</th></tr></thead><tbody><tr><td>Explicit Model</td><td>Inf-JESP</td><td>Robust Robot Planning - Offline</td></tr><tr><td>Generative Model</td><td>MC-JESP</td><td>Robust Robot Planning - Online</td></tr><tr><td>Research Interest</td><td>Optimality</td><td>Robustness</td></tr></tbody></table>

methods, a co-working scenario is designed, which allows conducting experiments and presenting qualitative and quantitative results to evaluate our approach.

## 1.5 Outline

The structure of this thesis is organized as follows:

* Chapter 1 gives an overview of this thesis, the motivation, research questions, contributions and outlines;

* Chapter 2 is the background part, where we introduce different Markov decision models related to our research and discuss their relations and variations;

* Chapter 3 discusses the related works of multi-agent decision making applicable to robot-robot collaboration;

* Chapter 4 presents our contributions on how to solve multi-agent decision problems with partial observations;

* Chapter 5 describes the related works of human-robot collaboration, which are categorized based on how the robot models its human partner;

* Chapter 6 presents our contributions to solving human-robot collaboration problems by computing robust robot policies;

* Chapter 7 concludes the thesis and discusses future directions.
# Background

## 2.1 Frameworks for Sequential Decision Making

Decision making is an important part of daily life. We, humans, make decisions and follow plans to achieve our goals. It is the same for automated software, robotics, and all kinds of machines to decide what to do or how to react in different conditions.

One big branch in this context is classical planning, where the aim is to find a sequence of actions to end up in a goal state. Classical planning has a wide range of real-world applications, such as in logistics [Helmert, 2009, García et al., 2013], robotics [Alami et al., 1998, González et al., 2017] and web services [Yang and Qin, 2010]. However, in classical planning, the environment and actions are usually deterministic, and a practical approach is to “re-plan” whenever the state encountered is not the one anticipated, but this can lead to catastrophes. To that end, *contingent planning* and *conformant planning* [Cimatti and Roveri, 2000, Hoffmann and Brafman, 2005, 2006, Albore et al., 2009] are meant to handle planning problems with uncertainty about the initial state and action outcomes under partial or no observability. A key issue with these approaches is that they ignore probabilities. Thus, they can only rely on criteria such as the “worst-case outcome” of the (conditional) plan, which can be overly pessimistic

Another classic framework for sequential decision making is the Markov decision process, which is the main tool we used in this thesis. In Markov Decision models, the agent(s) will take actions and receive observations come from the environment state. The environment dynamic is modeled by the probabilities of state transition and observation. The reward defines the agents’ goal, where the agents need to maximize the expected accumulated reward during the task. The key feature in Markov decision models, which is called *Markov property*, is that the next state only depends on the current state and the action performed, not the history. In this chapter, we introduce Markov decision processes in detail, including MDPs, POMDPs for single-agent settings and Dec-POMDPs for multi-agent settings.

## 2.2 Markov Decision Process (MDP)

In this section, we present the Markov decision process (MDP) model, which is one of the most basic decision-making formalisms for single-agent settings. Despite its simplicity, it can be used to formalize tasks where an agent is in a stochastic environment with full observability of the environment state.

As illustrated on Figure 2.1, an MDP is formally defined by a tuple $(S, A, T, r)$ where

* $S$ is the state space;
<figure><img src="image_6.png" /><figcaption>Figure 2.1: Markov decision process illustration: the agent chooses an action a at state s, will have a reward r and reach next state s'.</figcaption></figure>

* A is the action space;

* $T(s, a, s') = Pr(s'|s, a)$ is the transition function, which encodes the dynamic of the environment (the probability of reaching the next state s' given the current state s and an executed action a);

* $r(s, a)$ is the reward function, which gives the instant reward when performing action a at state s. Note that one can also specify $r(s, a, s')$, but then define $r(s, a) = \sum_{s'} T(s, a, s') \cdot r(s, a, s')$.

### 2.2.1 Performance Measurement

As mentioned above, after choosing an action a at state s, a reward r will be given. However, the instant reward cannot evaluate a policy since one can easily be misled by a high reward in the current state and lose the opportunity to gain more in the future.

In MDPs, a policy $\pi$ is a mapping from states to actions $\pi: S \to A$, and the goal is to find the optimal policy $\pi^*$ which brings the highest accumulated rewards. We call $V^\pi(s)$ the *value function*, and it evaluates policy $\pi$ when executed from state s:

$$V^\pi(s) = E_\pi \left[ \sum_{i=0}^{\infty} \gamma^i r_i | s_0 = s \right]. \qquad (2.1)$$

The discounted factor $\gamma$ indicates the importance of future rewards compared with the current reward. Especially if $\gamma = 0$, it means the agent will behave greedily and only considers the current reward; if $\gamma = 1$, the future reward and current reward are equally important, but this will cause a problem in the infinite-horizon setting since the agent sees no difference from picking any action in terms of expected value at infinite steps. Thus, in infinite-horizon settings, $\gamma$ is in range [0, 1) but in finite-horizon settings, $\gamma$ could be set to 1. Given a policy $\pi$, the agent's action selection is denoted as $a = \pi(s)$, then Equation (2.1) can be rewritten as

$$V^\pi(s) = r(s, \pi(s)) + \gamma \sum_{s' \in S} T(s, \pi(s), s') V^\pi(s'). \qquad (2.2)$$
This value function $V^\pi$ is also called state-value function. On the other hand, if we also consider the action $a$, one can define the action-value function as follows:

$$Q^\pi(s, a) = E \left[ \sum_{i=0}^{\infty} \gamma^i r_i | s_0 = s, a_0 = a \right] \qquad (2.3)$$

$$= \sum_{s' \in S} T(s, a, s') [r(s, a) + \gamma V^\pi(s')] \qquad (2.4)$$

$$= r(s, a) + \gamma \sum_{s' \in S} T(s, a, s') V^\pi(s'). \qquad (2.5)$$

According to the definition of state-value function and action-value function, the state value is the expected value when performing action $\pi(s)$; Similarly, the action-value function is defined by an instant reward plus the discounted future expected state value.

In MDPs, the goal is to find an optimal policy, i.e., one that maximizes the expected value as defined in Equation (2.1). This optimal policy is denoted $\pi^*$, and it should maximize the value function for any state $s$ as shown in Equation (2.6).

$$\pi^* = \arg \max_{\pi} V^{\pi}(s). \qquad (2.6)$$

Note that there may be multiple optimal policies in an MDP, but all of them share the same value function. Here we define the optimal state-value function $V^*$ as in Equation (2.7). This mathematical expression is also called Bellman optimality equation.

$$V^*(s) = \max_a[r(s, a) + \gamma \sum_{s' \in S} T(s', a, s)V^*(s')]. \qquad (2.7)$$

Similarly, the optimal action-value function $Q^*$ is defined in Equation (2.8). It is the sum of the current instant reward plus the discounted expectation of optimal future values.

$$Q^*(s, a) = r(s, a) + \gamma \sum_{s' \in S} T(s, a, s')V^*(s'). \qquad (2.8)$$

From those two definitions, we know that the optimal value in a given state equals the expected return of its best action, knowing that an optimal policy is followed afterward.

### 2.2.2 Optimization Algorithms

In the previous section, we have defined the MDP model and value functions. In this section, we introduce algorithms for solving MDPs that give optimal policies.

#### Dynamic Programming Methods

Dynamic programming (DP) is a classic approach that breaks down a complex problem into simpler sub-problems in a recursive manner [Howard, 1960]. For MDPs, there are two main DP algorithms, *value iteration* and *policy iteration* respectively. Before introducing those two detailed algorithms, we first present the *Contraction Mapping Theorem* (also called *Banach fixed-point theorem*).

**Definition 1** An operator $\mathcal{F}$ on a vector space $\mathcal{X}$ is a $\gamma$-contraction for all $x, y \in \mathcal{X}$ if $0 < \gamma < 1$:

$$\|F(x) - F(y)\| \le \gamma \|x - y\| \qquad (2.9)$$
**Theorem 1** For a given $\gamma$-contraction $\mathcal{F}$ in $\mathcal{X}$, it has two properties (proofs can be found in [Denardo, 1967]):

* the iteration of $\mathcal{F}$ will converge to a fixed point in $\mathcal{X}$ in any start point;

* the convergence rate is determined linearly by $\gamma$.

**Value Iteration:** We first introduce the *value iteration* algorithm as shown in Algorithm 1. In

<caption>**Algorithm 1:** Value Iteration</caption>

1 [Initilization:] $V(s) = 0$, for all $s \in \mathcal{S}$
2 repeat
3 &nbsp;&nbsp;&nbsp;&nbsp;$\Delta \leftarrow 0$
4 &nbsp;&nbsp;&nbsp;&nbsp;**for** $s \in \mathcal{S}$ **do**
5 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$v \leftarrow V(s)$
6 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$V(s) \leftarrow \max_a[r(s, a) + \gamma \sum_{s' \in \mathcal{S}} T(s, a, s')V(s')]$
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\Delta \leftarrow \max(\Delta, |v - V(s)|)$
8 **until** $\Delta < \epsilon$ (a small positive number)
9 $\pi(s) = \arg \max_a[r(s, a) + \gamma \sum_{s' \in \mathcal{S}} T(s, a, s')V(s')]$
10 **return** $\pi$

the value iteration algorithm, all states' values are initialized to 0 (line 1). Then, it recursively updates values based on the best next state (line 6). In line 8, this process is stopped when the change is smaller than $\epsilon$. Therefore, we obtain the optimal value function $V^*$, which stores the optimal value for each state. An optimal policy $\pi^*$ is easily computed by finding the best action at each state (line 9). The key to this method is to recursively refine the estimator $V^*$:

$$V_{i+1}^*(s) \leftarrow \max_a \sum_{s' \in S} [r(s, a) + \gamma T(s, a, s') V_i^*(s')], \quad (2.10)$$

which is a contraction mapping between vector spaces $V_{i+1} = H_{\max}V_i$ (see Definition 1), and $H_{\max}$ is a $\gamma$-contraction operator. Therefore, applying this operator repeatedly is guaranteed to converge to a fixed optimal value function $V^*$

**Policy Iteration:** On the other hand, *Policy iteration* starts with a given policy $\pi$ and improves it iteratively until an optimal policy is obtained. As shown in Algorithm 2, it contains two steps, policy evaluation and policy improvement. In policy evaluation, the aim is to evaluate $V^\pi(s)$ for the current policy $\pi$. This is a linear system since $V^\pi$ contains $|S|$ linear equations with $|S|$ unknowns. This linear system $V = H^\pi V$ relies on a contraction mapping operator $H^\pi$ (line 6), so repeatedly applying this operator leads to the only solution $V^\pi$. In the policy improvement step, with the evaluated values, the aim is to find the best action for each state $s$ (line 14) in order to improve the current policy. Given $\pi_k$ and $\pi_{k+1}$ the two policies before and after improvement, policy iteration iterates this process until $\pi_{k+1} = \pi_k$, meaning that an optimal policy has been reached.

## Sampling-Based Methods

In the previous section, we briefly introduced two DP methods: *value iteration* and *policy iteration*. Both used knowledge of the explicit model, including the state transition probabilities
<table><caption>**Algorithm 2: Policy Iteration**</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>[Initialization:] initialize V(s) and π(s) arbitrarily, for all s ∈ S</td></tr><tr><td>2</td><td><b>Fct Policy Evaluation</b></td></tr><tr><td>3</td><td><b>repeat</b></td></tr><tr><td>4</td><td>Δ ← 0</td></tr><tr><td>5</td><td><b>for</b> s ∈ S <b>do</b></td></tr><tr><td>6</td><td><b>v</b> ← V(s)</td></tr><tr><td>7</td><td><b>V</b>(s) ← <b>r</b>(s, π(s)) + γ ∑<sub>s'∈S</sub> <b>T</b>(s, π(s), s')<b>V</b>(s')</td></tr><tr><td>8</td><td>Δ ← max(Δ, |<b>v</b> − <b>V</b>(s)|)</td></tr><tr><td>9</td><td><b>until</b> Δ &lt; ε (a small positive number)</td></tr><tr><td>10</td><td><b>Fct Policy Improvement</b></td></tr><tr><td>11</td><td><b>policy</b> − <b>stable</b> ← <b>true</b></td></tr><tr><td>12</td><td><b>for</b> s ∈ S <b>do</b></td></tr><tr><td>13</td><td><b>old − action</b> ← π(s)</td></tr><tr><td>14</td><td>π(s) ← arg max<sub>a</sub>[<b>r</b>(s, a) + γ ∑<sub>s'∈S</sub> <b>T</b>(s, a, s')<b>V</b>(s')]</td></tr><tr><td>15</td><td><b>if</b> <b>old − action</b> ≠ π(s) <b>then</b></td></tr><tr><td>16</td><td><b>policy</b> − <b>stable</b> ← <b>false</b></td></tr><tr><td>17</td><td><b>if</b> <b>policy</b> − <b>stable</b> <b>then</b></td></tr><tr><td>18</td><td><b>return</b> π</td></tr><tr><td>19</td><td><b>else</b></td></tr><tr><td>20</td><td><b>go to</b> <b>Policy Evaluation</b></td></tr></tbody></table>

and expected rewards, to compute an optimal policy $\pi^*$. However, for large problems, there is a “curse of dimensionality” since the cost of computing the expectation over all possible future states grows exponentially with the number of states [Rust, 1997]. Moreover, for such large problems, representing explicitly the full model could even be unfeasible. Unlike the DP methods we mentioned in the last section, sampling-based planning methods only require a generative model (also called a simulator). Such an MDP generative model $G$ takes a state-action pair of state and action $\langle s, a \rangle$ as input, then returns a next state $s'$ and an instant reward $r$.

In this section, we mainly introduced the *Monte-carlo tree search* algorithm (MCTS) [Browne et al., 2012], which is one of the most popular sampling-based planning methods. In MCTS, the curse of dimensionality is avoided by only sampling states from a generative model instead of calculating all possible state transitions using an explicit MDP model. Globally, MCTS searches a tree policy as shown in figure 2.2, going through 4 main steps at each iteration:

1. *Selection*: Starting from the root node, recursively select child nodes until reaching a leaf node $L$;

2. *Expansion*: Randomly create an unvisited child node $C$ of node $L$ if $L$ is not a terminal node;

3. *Simulation*: Starting from node $C$, perform simulations using rollout-policy $\pi_{Rollout}$ (also called default policy which is usually a random policy) till a terminal state;

4. *Back-propagation*: Use the result obtained from the simulation step to update the values of all parent nodes in the selected path.
<figure><img src="image_7.png" /><figcaption>Figure 2.2: The four steps of an iteration of Monte-Carlo Tree Search [Browne et al., 2012]: Selection, Expansion, Simulation, and Back-propagation.</figcaption></figure>

For MCTS, an important question is how to balance exploration and exploitation in the search process. To that end, a practical method is picking actions optimistically by adding a bonus to action-value estimates that are less reliable (because they are less visited). For example, the UCT algorithm [Kocsis and Szepesvári, 2006] uses the upper confidence bound (UCB) for the tree search/exploration, where the action value is modified by adding an exploration bonus:

$$Q^{+}(s, a) = Q(s, a) + c\sqrt{\frac{\log N(s)}{N(s, a)}}. \qquad (2.11)$$

The visit number for each state action pair $\langle s, a \rangle$ is denoted as $N(s, a)$, and $N(s)$ is the overall visit number in state $s$, so that $N(s) = \sum_a N(s, a)$. The term $c\sqrt{\frac{\log N(s)}{N(s, a)}}$ allows adding a larger bonus to the rarely selected actions rather than frequently visited ones. The parameter $c$ controls the ratio of exploration and exploitation, the algorithm tries more exploration actions when $c$ increases and acts as a greedy policy that only exploits estimates if $c = 0$. Note that one can remove the exploration bonus to pick actions at execution time. Another common approach is to pick the most often selected action (the one maximizing $N(s, a)$), which can be more reliable.

### 2.2.3 Categorization of the Offline and Online Planning

For single-agent planning approaches, an important categorization is to distinguish offline and online algorithms. As shown in Figure 2.3, the offline planning method first computes a complete policy for the agent (a mapping from states to actions in MDPs), and the agent executes the computed policy afterward. On the other hand, the online planning method interleaves the planning and execution phases. In the planning phase, the online approach tries to find the best immediate action given the current situation within a given time and memory budget. Then, when the planning phase terminates, the agent executes an estimated best action in the execution phase and updates its estimate of the environment state to launch the next online planning phase.

We take a simple example of a path planning problem for a robot to illustrate the difference between the offline and online methods. In offline planning, the robot has complete knowledge of the environment, including the positions of obstacles and the goal on a map, then a complete path is computed using this complete environment information before the robot behaves. In the online planning case, the planning is carried out continuously when the robot receives observations
<figure><img src="image_8.png" /><figcaption>Figure 2.3: An illustration of the offline and online approaches [Ross et al., 2008].</figcaption></figure>

(complete or partial) from the environment; it may also find the changes in the environment, such as the goal position or the obstacles being moved. This being said, the offline planning method is generally used for the static environment but is usually able to find optimal solutions; the online algorithms, on the other hand, are more suitable for unknown or dynamic changing environments [Ross et al., 2008, Chatzis and Kosmopoulos, 2014, Lecarpentier and Rachelson, 2019]. The dynamic programming algorithms we describe in Section 2.2.2 are meant to be used offline and guarantee to converge to optimal policies no matter the start state; and the sampling-based method, such as MCTS, belongs to online planning, which may not need the explicit model and tolerate the changes in the environment but gives approximate solutions in terms of realistic computation resources.

## 2.3 Partially Observable Markov Decision Process (POMDP)

In some cases, the complete environment's information is not directly accessible, the agent only has partial information about the current state [Åström, 1965]. The Partially Observable Markov Decision Process (POMDP) model is designed for such decision problems. A POMDP is defined by a tuple $\langle S, A, \Omega, T, O, r, b_0 \rangle$ where $\langle S, A, T, r \rangle$ is an underlying MDP, and:

* $\Omega$ is the observation space;

* $O(o, a, s') = Pr(o|s', a)$ is the observation function; it indicates the probability of receiving an observation $o$ given the next state $s'$ reached while performing action $a$;

* $b_0$ is an initial distribution over states.

As illustrated in Figure 2.4, at each time step $t$, performing an action $a$ when in state $s$ induces a reward $r(s, a)$ and leads to state $s'$ with probability $T(s, a, s')$. However, the agent can only receive an observation $o$, which contains partial or noisy information on the next state.

In MDPs, the state is a sufficient statistics to reason about the current situation and make optimal decisions since the agent does not need any additional information. However, in POMDPs, since the real state is not accessible by the agent anymore, all the information the agent has
<figure><img src="image_9.png" /><figcaption>Figure 2.4: Partially observable Markov decision process</figcaption></figure>

at execution time is the action-observation history (AOH), so its decisions will depend on that. In POMDPs, we call AOH a *information state*. However, in long-horizon problems, storing such histories is costly. Therefore, another popular method is using a probability distribution over possible states to represent the current information state, and this distribution is called a belief state (or belief) *b*. Moreover, the agent needs to update its belief after an action *a* is executed and an observation *o* is received. This belief update process is detailed as follows, where $b^{a,o}$ is a new belief and $b^{a,o}(s')$ is the probability of being in the state $s'$ in that belief state:

$$b^{a,o}(s') = \mathrm{Pr}(s'|o, a, b) = \frac{\mathrm{Pr}(s', o, a, b)}{\mathrm{Pr}(o, a, b)}, \qquad (2.12)$$

$$= \frac{\mathrm{Pr}(o|s', a, b) \mathrm{Pr}(s'|a, b) \mathrm{Pr}(a, b)}{\sum_{s'} \sum_s \mathrm{Pr}(o, s, s', a, b)}, \qquad (2.13)$$

$$= \frac{\mathrm{Pr}(o|s', a) \sum_s \mathrm{Pr}(s'|a, b, s) \mathrm{Pr}(s|a, b)}{\sum_{s'} \mathrm{Pr}(o|s', a) \sum_s \mathrm{Pr}(s'|a, b, s) \mathrm{Pr}(s|a, b)}, \qquad (2.14)$$

$$= \frac{O(s', a, o) \sum_s T(s, a, s') b(s)}{\sum_{s'} O(s', a, o) \sum_s T(s, a, s') b(s)}. \qquad (2.15)$$

As for MDPs, the objective of POMDPs is to generate a policy whose execution maximizes the agent's expected accumulated rewards. The optimal value function of POMDPs is defined in Equation (5),

$$V^*(b) = \max_{a \in \mathcal{A}} \left[ r(b, a) + \gamma \sum_{o \in \Omega} \mathrm{Pr}(o|b, a)V^*(b') \right] \qquad (2.16)$$

and its optimal policy is defined as follows:

$$\pi^*(b) = \arg \max_{a \in \mathcal{A}} \left[ r(b, a) + \gamma \sum_{o \in \Omega} \mathrm{Pr}(o|b, a)V^*(b') \right]. \qquad (2.17)$$

Here the function $r(b, a)$ specifies the expected immediate reward of executed action *a* under the belief *b*:

$$r(b, a) = \sum_{s \in \mathcal{S}} b(s)r(s, a),$$
and the function $Pr(o|b, a)$ is the probability of recieving an observation $o$ in belief $b$ with performed action $a$:

$$Pr(o|b, a) = \sum_{s' \in S} O(s', a, o) \sum_{s \in S} T(s, a, s') b(s).$$

### 2.3.1 History-Based Policy

#### Policy Trees

For the finite-horizon setting, a POMDP policy can be represented in a tree structure as shown in Figure 2.5 (a). Each tree node contains an action $a$ to be executed by the agent, then steps to a lower branch depending on which observation $o$ the agent received. For a finite horizon $H$, a policy tree contains $\sum_{t=0}^{t=H-1} |\Omega|^t = \frac{|\Omega|^{H-1}}{|\Omega|-1}$ nodes. In our example Figure 2.5 (a), the horizon $H=3$ and the size of observation space $|\Omega|=2$, thus we have $2^0+2^1+2^2=7$ nodes. Since each node has $|A|$ choices of actions, the number of all policy trees in horizon $H$ is $|A|^{\frac{|\Omega|^{H}-1}{|\Omega|-1}}$.

Moreover, using policy trees, one can approximate the value of a discounted infinite-horizon POMDP as follows:

$$V^*(b_0) - V_H^*(b_0) \le \frac{\gamma^H}{1-\gamma} [R_{max} - R_{min}], \qquad (2.18)$$

where $V^*(b_0)$ is the optimal value of the true POMDP and $V_H^*(b_0)$ is the optimal value given a truncated horizon $H$.

#### Finite State Controllers

An issue of the policy tree structure is its complexity in the long horizon problem and its impossibility of storing all the decisions in the infinite horizon problems. Therefore, finite state controllers (FSCs) are usually used to represent POMDP policies for the infinite-horizon setting. Compared with the policy tree, an FSC is defined by a directed graph that contains cycles to handle infinite horizons. Here we first introduce the most generic form, the stochastic FSC. For some POMDP sets $\mathcal{A}$ and $\Omega$, a stochastic FSC is defined by a tuple $fsc = \langle N, \beta, \eta, \psi \rangle$, where:

* $N$ is a finite set of (internal) nodes;

* $\beta$ is a probability distribution from which to sample the initial node;

* $\eta: N \times \mathcal{A} \times \Omega \times N \rightarrow \mathbb{R}$, the transition function, gives the probability $\eta(n, \langle a, o \rangle, n')$ of transiting from node $n$ to $n'$ if $a$ is performed and $o$ is observed; a deterministic transition can be noted $n' = \eta(n, \langle a, o \rangle)$;

* $\psi: N \times \mathcal{A} \rightarrow \mathbb{R}$, the action selection function, gives the probability $\psi(n, a)$ of choosing $a \in \mathcal{A}$ when in $n$.

But in most cases, deterministic FSCs are used to present POMDP policies in policy search algorithms [Hansen, 1997, 1998] where the action selection function $\psi$ gives a deterministic action $a$ at each node $n$. An illustration of such a deterministic FSC is presented in Figure 2.5 (b).
<figure><img src="image_10.png" /><figcaption>Figure 2.5: Two example representations of POMDP policies: (a) policy tree; (b) finite state controller [Amato, 2010].</figcaption></figure>

### 2.3.2 Belief-Based Policy

#### α-vectors

Another type of policy representation is using α-vectors, which is a belief-based policy. For a given POMDP, although its belief space $B$ is infinite, it is proved that one can approximate the POMDP’s value function as an upper envelope of a finite set of linear functions $\Gamma = \{\alpha_1, \dots, \alpha_n\}$ [Sondik, 1978], which are also known as α-vectors. Each α-vector is attached to an action $a$ and contains $|S|$ values for each corresponding state, and in this case, for a specific belief $b$, the representation of the value function is defined as:

$$V(b) = \max_{\alpha \in \Gamma} b \cdot \alpha, \qquad (2.19)$$

$$\text{where} \quad b \cdot \alpha = \sum_{s \in S} b(s)\alpha(s). \qquad (2.20)$$

This representation provides a lower-bound to approximate $V^*$, and to derive a policy from α-vectors, one can find out which α-vectors is attached to the current belief (see Equation (2.19)), and the action attached to the α-vector is the one to perform. This approach guarantees an expected return above the value of this lower bound. Modern POMDP solvers such as SARSOP [Kurniawati et al., 2008] and HSVI [Smith and Simmons, 2004] usually give solutions in the form of α-vectors.

Moreover, one can transform a set of α-vectors to a corresponding FSC. Grześ et al. propose such a method called Alpha2FSC as presented in Algorithm 3 [Grześ et al., 2015]. In this method, it is assumed that a set of α-vectors in $\Gamma$ is given, and each $\alpha_i \in \Gamma$ is attached with a belief $b_i$ and action $a_i$ (line 1). Then, an FSC node $n_i$ is created for each $\alpha_i$ and labeled by action $a_i$ (lines 4-6). In lines 9-13, the transitions between nodes are determined by finding which α-vector has the highest value of $b_i^{a_i, o}$ (which is the updated belief for each node $n_i$ with attached action $a_i$ and received observation $o$), and a self-loop is created for any impossible observation given the current node $n_i$. Moreover, if a set of α-vectors in $\Gamma$ is the optimal value function, one can transform $\Gamma$ to an optimal corresponding FSC [Grześ et al., 2015]. However, this transformation guarantees that an optimal corresponding FSC is derived only if the set of α-vectors in $\Gamma$ is the optimal value function. Otherwise, if the set of α-vectors is suboptimal (which is the case for
<table><caption>**Algorithm 3: Alpha2FSC**</caption><thead><tr><th></th><th></th></tr></thead><tbody><tr><td>1</td><td>[inputs:] Γ: a set of &lt;α<sub>i</sub>, b<sub>i</sub>, a<sub>i</sub>&gt;-tuples</td></tr><tr><td>2</td><td>[outputs:] an FSC &lt;N, ψ, η&gt;</td></tr><tr><td>3</td><td>N &larr; ∅</td></tr><tr><td>4</td><td>for i = 1 to |Γ| do</td></tr><tr><td>5</td><td>N &larr; N &cup; n<sub>i</sub></td></tr><tr><td>6</td><td>ψ(n<sub>i</sub>) &larr; a<sub>i</sub></td></tr><tr><td>7</td><td>for i = 1 to |Γ| do</td></tr><tr><td>8</td><td>for o &isin; Ω do</td></tr><tr><td>9</td><td>if Pr(o|b<sub>i</sub>, a<sub>i</sub>) &gt; 0 then</td></tr><tr><td>10</td><td>best &larr; arg max<sub>j</sub> b<sub>i</sub><sup>a<sub>i</sub>,o</sup> &middot; α<sub>j</sub></td></tr><tr><td>11</td><td>η(n<sub>i</sub>, o) &larr; n<sub>best</sub></td></tr><tr><td>12</td><td>else</td></tr><tr><td>13</td><td>η(n<sub>i</sub>, o) &larr; n<sub>i</sub></td></tr><tr><td>14</td><td>return &lt;N, φ, ψ&gt;</td></tr></tbody></table>

modern POMDP solvers), the transformation is an approximation, and its quality may be better or worse. In this thesis, we also provide other approximate transformation methods in Chapter 4.

Last but not least, a deterministic FSC's value function (i.e., η and ψ being both deterministic) is the solution of the following system of linear equations, with one α-vector per node n [Hansen, 1997]:

$$ \alpha_s^n = R(s, a_n) + \gamma \sum_{s',o} T(s, a_n, s')O(a_n, s', o)\alpha_{s'}^{\eta(n,o)}, \quad (2.21) $$

where $a_n \stackrel{\text{def}}{=} \psi(n)$. Using the fixed point theorem, a solution can be found using an iterative process typically stopped when the Bellman residual (the largest change in value) is less than a threshold $\epsilon$, so that the estimation error is less than $\frac{\epsilon}{1-\gamma}$.

### 2.3.3 Optimization Algorithms

Many algorithms have been proposed to solve POMDPs. For example, in the finite-horizon case, a POMDP can be turned into a finite-horizon belief-space MDP, thus with finitely many belief states [Åström, 1965]. Therefore, exact value iteration and policy iteration methods for MDPs can be applied. But the real breakthroughs in the past decades are the point-based algorithms, including PBVI [Pineau et al., 2003], HSVI [Smith and Simmons, 2004] and SARSOP [Kurniawati et al., 2008]; and sampling-based methods such as POMCP [Silver and Veness, 2010] and DESPOT [Somani et al., 2013]. Both types of methods can solve complex POMDP problems with many thousands of states.

#### Point-Based Method

The Point-Based Value Iteration algorithm (PBVI) [Pineau et al., 2003] is the foundation of modern point-based solvers [Shani et al., 2012]. As we know in POMDPs, belief space is continuous, meaning there are infinitely many belief points. However, in practice:

* some belief points are unreachable with any given action-observation history;
• we want to focus on points that are reachable under an optimal policy;

Therefore, the problem is quickly figuring out which set of belief points to use (and at which to perform Bellman updates). To that end, PBVI focuses on solving POMDPs within a set of reachable belief points, and the value function is approximated as an upper envelope of α-vectors (which acts as a lower bound) denoted as $\Gamma$.

<caption>**Algorithm 4: Point-Based Value Iteration Algorithm**</caption>

1. **[inputs:]** $B_0$: initial belief set | $\Gamma_0$: initial value | $N$: expansion number | $H$: iteration number
2. $B = B_0$
3. $\Gamma = \Gamma_0$
4. **for** $N$ **expansions** **do**
5. &nbsp;&nbsp;&nbsp;&nbsp;**for** $H$ **iterations** **do**
6. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**[** $\Gamma = \text{BACKUP}(\Gamma, B)$
7. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**B' = \text{EXPAND}(\Gamma, B)$
8. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**]**
9. **return** $\Gamma$

As shown in Algorithm 4, a belief set $B$ is first initialized with starting belief $b_0$. Then in lines 5–6, in each iteration, PBVI updates the value function $V$ by performing a Bellman backup at each belief point $b$ stored in $B$, in which:

$$ \Gamma_B^{i+1} = \text{backup}(\Gamma_B^i, b), b \in B; \qquad (2.22) $$

$$ \text{backup}(\Gamma, b) = \underset{a \in A, \alpha \in \Gamma}{\arg\max} b \cdot \alpha_a^b; \qquad (2.23) $$

$$ \alpha_a^b = r_a + \gamma \sum_{o \in \Omega} \underset{\alpha \in \Gamma}{\arg\max} b \cdot \alpha^{a,o}. \qquad (2.24) $$

This process is repeated $H$ times, and usually, the $H$ is selected so that $\gamma^H[R_{max} - R_{min}] < \epsilon$ where $\epsilon$ is the error bound. After $H$ backups are finished, PBVI expands its belief set $B$ by selecting for belief $b \in B$ a reachable successor belief $b'$ (lines 7–8), which has the longest distance from the current belief set $B$. In the end, PBVI returns the value function $\Gamma$, a set of $\alpha$ vectors, and each $\alpha \in \Gamma$ comes with an action to perform.

Based on PBVI, researchers made improvements to further increase the scalability of the point-based methods. For example, in HSVI [Smith and Simmons, 2004] and SARSOP [Kurniawati et al., 2008], heuristics are introduced to focus on the points which are most relevant to the value function, and an upper and lower bound are maintained over the value function to guide local updates and bound the error.

## Sampling-Based Method

As in an MDP, sampling-based methods for a POMDP do not need an explicit model but only a generative model $G$ (a black-box simulator). Such a model takes a state-action pair and returns a tuple of successor state, observation, and instant reward as follows:

$$ \langle s', o', r \rangle \sim G(s, a). \qquad (2.25) $$
In Section 2.2.2 (page 12), we have introduced the Monte-Carlo tree search (MCTS) algorithm for solving MDPs. Partially Observable Monte-Carlo Planning (POMCP) [Silver and Veness, 2010], one of the most successful sampling-based methods, extends MCTS to POMDPs. The main algorithm is present in Algorithm 5. Compared with MCTS, POMCP has two improvements to

<caption>**Algorithm 5: POMCP**</caption>

1 Fct Search(h)
2 repeat
3 if h = empty then
4 s ~ b₀
5 else
6 s ~ B(h) // B(h): set of state particles for the history h
7 Simulate(s, h, 0)
8 until Timout()
9 return arg maxₐ Q(h, a)
10 Fct Simulate(s, h, depth)
11 if γdepth < ϵ then
12 return 0
13 if h ∉ T then
14 for a ∈ A do
15 T(h, a) ← (Nₘit(h, a), Qₘit(h, a), ∅)
16 return Rollout(s, h, depth)
17 a ← arg maxₐ [Q(h, a) + c√(log N(h)/N(h, a))]
18 (s', o, r) ~ G(s, a)
19 R ← r + γSimulate(s', hao, depth + 1) // hao: new action-observation history
20 B(h) ← B(h) ∪ {s}
21 N(h) ← N(h) + 1
22 N(h, a) ← N(h, a) + 1
23 Q(h, a) ← Q(h, a) + (R-Q(b,a)/N(h,a))
24 return R
25 Fct Rollout(s, h, depth)
26 if γdepth < ϵ then
27 return 0
28 a ← πₚollout(h) // πₚollout: default policy (random policy)
29 (s', o, r) ~ G(s, a)
30 return r + γRollout(s', hao, depth + 1)

solve the POMDP problem. First, POMCP extends the UCT algorithm to a partially observable setting called PO-UCT. In PO-UCT, a search tree is built using histories instead of states. Each tree node is labeled with an action-observation history *h*, and in the search process, actions are selected using the same UCB method:

$$Q^{+}(h, a) = Q(h, a) + c\sqrt{\frac{\log N(h)}{N(h, a)}}. \qquad (2.26)$$
Second, POMCP approximates the agent’s belief with particles and uses a particle filter to update
the current belief state after each actual transition. In the beginning, the approximate belief $\tilde{b}$
is represented with $K$ particles of states sampled from the initial belief. Then, after an action $a$
is executed in the real environment with an observation $o$ received, we randomly select a state
$s$ from the current $\tilde{b}$ and pass $s$ with executed action $a$ to the generative model $G$ which will
return a tuple $\langle s', o', r \rangle$. If the sample observation is the same as the real observation $o' = o$, we
keep the successor state $s'$ and add it to a new approximate belief $\tilde{b}'$. This process repeats until
we have $k$ particles in $\tilde{b}'$.

There exists also other powerful sampling-based methods such as DESPOT (Determinized Sparse Partially Observable Tree) [Somani et al., 2013]. However, in this thesis, POMCP is used in our contributions because of its simplicity of implementation and efficiency in solving POMDPs.

### 2.3.4 Multi-Agent POMDP

For the multi-agent setting, if there is a centralized controller that controls all agents’ actions and receives all agents’ observations in at each time step, then we can use multi-agent POMDP (MPOMDP) [Pynadath and Tambe, 2002] to formulate such a problem. An MPOMDP is essentially a POMDP since its action space is the joint action space of all agents and the same for the observation space. All the properties and algorithms built for POMDPs can be directly applied to MPOMDPs.

## 2.4 Decentralized Partially Observable Markov Decision Process
(Dec-POMDP)

The Dec-POMDP formalism is an extension of the POMDP formalism where several agents interact in the same environment and share the same reward function. Compared with a POMDP, a Dec-POMDP factors:

* the (joint) action into one action per agent,

* the (joint) observation into one observation per agent, and

* the (joint) policy into one individual policy per agent.

Formally, a Dec-POMDP with $|\mathcal{I}|$ agents is represented as a tuple $M = \langle \mathcal{I}, \mathcal{S}, \mathcal{A}, \Omega, T, O, R, b_0, H, \gamma \rangle$
[Bernstein et al., 2002], where:

* $\mathcal{I} = \{1, \dots, |\mathcal{I}|\}$ is a finite set of agents;

* $\mathcal{S}$ is a finite set of states;

* $\mathcal{A}^i$ is the finite set of agent $i$'s actions; $\mathcal{A} = \times_i \mathcal{A}^i$ is the finite set of joint actions;

* $\Omega^i$ is the finite set of agent $i$'s observations; $\Omega = \times_i \Omega^i$ is the finite set of joint observations;

* $T: \mathcal{S} \times \mathcal{A} \times \mathcal{S} \rightarrow \mathbb{R}$ denotes the transition function; $T(s, a, s')$ is the probability of transiting to the next state $s'$ from state $s$ if joint action $a$ is performed;

* $O: \mathcal{A} \times \mathcal{S} \times \Omega \rightarrow \mathbb{R}$ is the observation function; $O(a, s', o)$ is the probability of observing $o$ if joint action $a$ is performed and the resulting state is $s'$;
* $R: S \times A \to \mathbb{R}$ is the reward function; $R(s, a)$ gives the immediate reward for executing joint action $a$ in state $s$;

* $b_0$ is the initial probability distribution over states;

* $H \in \mathbb{N} \cup \{\infty\}$ is the (possibly infinite) time horizon;

* $\gamma \in [0, 1)$ is the discount factor, which defines the discount applied to future rewards.

Each agent $i$ can be equipped with a policy $\pi^i$ that maps its possible action-observation histories to actions. The objective is then to find a joint policy $\pi = \langle \pi^1, \dots, \pi^{|S|} \rangle$ that maximizes a performance criterion, here the expected discounted return from $b_0$:

$$V_H^\pi(b_0) \stackrel{\text{def}}{=} \mathbb{E} \left[ \sum_{t=0}^{H-1} \gamma^t r(S_t, A_t) \mid S_0 \sim b_0, \pi \right].$$

Dec-POMDPs are difficult to solve and are proved to be NEXP-complete [Bernstein et al., 2002, Oliehoek and Amato, 2016]. In the finite-horizon setting, the number of possible deterministic joint policies (set of all agents' individual policies) is:

$$O(|\mathcal{A}^\dagger|^{\frac{|\mathcal{A}|(|\Omega^\dagger|^{H-1})}{|\Omega^\dagger|-1}}),$$

where $|\mathcal{A}^\dagger|$ and $|\Omega^\dagger|$ are the largest individual action and observation sets.

## 2.5 Solving Dec-POMDPs by finding Nash Equilibria

In this thesis, one of our main contributions is solving Dec-POMDPs (see Chapter 4). Specifically, we search Nash equilibrium solutions based on the JESP scheme (Joint Equilibrium based search for policies) [Nair et al., 2003]. Therefore, in this section, we detail the JESP method for solving Dec-POMDPs, and we present other Dec-POMDP algorithms in Chapter 3.

In a Nash equilibrium solution, each agent's policy is the best response to the other's policies in that equilibrium, and one has nothing to gain by only modifying its own policy [Kreps, 1989]. For a Dec-POMDP, the optimal solutions are a subset of these Nash equilibrium solutions (the ones with the highest values).

The JESP algorithm is designed for finite-horizon Dec-POMDPs, and aims to find Nash equilibrium solutions. In JESP, each agent's policy is represented using a policy tree. JESP iterates over each agent and tries to improve agent $i$'s policy, considering that other agents' policies are fixed. More specifically, when knowing other agents' fixed policies $\pi_{\neq i}$, an extended state POMDP is built for agent $i$. In this POMDP, the extended state is $e^t = \langle s^t, \vec{w}_{\neq i}^t \rangle$, where $s^t$ is the Dec-POMDP state and $\vec{w}_{\neq i}^t$ is the observation histories of other agents $\neq i$. Here, from agent $i$'s point of view, it is sufficient to consider observation histories rather than action-observation histories because the other agents' policies $\pi_{\neq i}$ are deterministic policy trees. Therefore, other agents' actions are directly derived with the observation histories as $a_{\neq i}^t \leftarrow \pi_{\neq i}(\vec{w}_{\neq i}^t)$ at each time step $t$. The dynamics of this extended POMDP for agent $i$ can be defined with Dec-POMDP's transition function $T$, observation function $O$, and reward function $R$ as:

$$ 
\begin{aligned}
T_e(e^t, a_i^t, e^{t+1}) &= \mathrm{Pr}(e^{t+1} | e^t, a_i^t) \\
&= [\prod_{j \neq i} O_{\mathrm{dec},j}(s^{t+1}, \langle a_i^t, \pi_{\neq i}(\vec{w}_{\neq i}^t) \rangle, \omega_j^{t+1})][T_{\mathrm{dec}}(s^t, \langle a_i^t, \pi_{\neq i}(\vec{w}_{\neq i}^t) \rangle, s^{t+1})], \\
O_e(a_i^t, e_i^{t+1}, o_i^{t+1}) &= \mathrm{Pr}(o_i^{t+1} | a_i^t, e_i^{t+1})
\end{aligned}
$$
$$ = O_{dec,i}(s^{t+1}, \langle a_i^t, \pi_{\neq i}(\vec{w}_{\neq i}^t) \rangle, \omega_i^{t+1}); \\ R_c(e_i^t, a_i^t) = R(s^t, \langle a_i^t, \pi_{\neq i}(\vec{w}_{\neq i}^t) \rangle). $$

Then agent $i$ maintains an extended belief $\beta_i^t = Pr(e_i^t|\vec{w}_i^t, \vec{a}_i^{t-1}, b_0)$ and its value function is defined as:

$$ V_i^t(\beta_i^t) = R(\beta_i^t, a_i^t) + \sum_{o^{t+1} \in \Omega_i} Pr(o^{t+1}|\beta_i^t, a_i^t)V_i^{t+1}(\beta_i^{t+1}). \quad (2.27) $$

The improvement process for agent $i$ consists in finding the optimal policy to optimize its value function. Nair et al. propose two choices to achieve this operation, either by an exhaustive search (Exhaustive-JESP) or dynamic programming (DP-JESP) to compute a new policy tree for agent $i$. But, of course, any other exact finite-horizon POMDP solver could also be used for the same purpose. JESP stops when no more improvements can be made for any agent. In each iteration, the value monotonically increases and guarantees to converge to Nash equilibrium solutions, thus, local optima.

For JESP, the main drawback is that it cannot guarantee to find the global optimal solution, and the Nash equilibrium solution computed by JESP may be a very poor local optimum. Therefore, JESP often runs using multiple restarts with different random initial policies in order to find one good local optimum solution. Another disadvantage is that JESP works only for finite-horizon Dec-POMDPs since policies are represented using policy trees.

## 2.6 Conclusion

In this chapter, we mainly introduced three general types of Markov models, MDPs, POMDPs, and Dec-POMDPs, respectively. To sum up, we have:

* MDP: the most basic Markov decision-making formalism for single-agent settings. In an MDP, the agent faces an uncertain environment but can directly observe the environment state;

* POMDP: the POMDP extends MDP in which the agent only observes partial or noisy information about the environment;

* Dec-POMDP: an extension of the POMDP to multi-agent settings where each agent has its own actions and observations;

Moreover, in the multi-agent setting, if we can control all agents' actions and access their observations, then we can model this problem as an MPOMDP, which is essentially a POMDP with joint action and joint observation spaces.

Regarding the solving algorithms, one can solve MDPs optimally with dynamic programming methods, including value iteration and policy iteration algorithms. Then, using generative models (simulators), a sampling-based method such as MCTS can be applied to find approximate solutions. On the other hand, for solving POMDPs, the first type of modern solvers are based on point-based value iteration, including SARSOP and HSVI; the second type is the sampling-based method such as POMCP, which is an extension of MCTS for POMDPs. We also introduced the JESP algorithm for solving Dec-POMDPs by finding Nash equilibrium solutions, which guarantees to converge to a local optimum.

In this thesis, the POMDP and Dec-POMDP formalisms will be used in our contributions to RRC and HRC (see Chapters 4 and 6).
# Related Work on
Multi-Agent Decision Making

## 3.1 Dec-POMDPs' overview

One primary interest in this thesis is multi-agent decision making, and Dec-POMDP is the most general framework among all Markov decision models, where multiple agents optimize a shared performance criterion under uncertainties due to the environment's dynamics and the agents' partial and noisy observations. However, as explained in Section 2.4, solving a Dec-POMDP is very difficult. Even for a finite-horizon Dec-POMDP, the solving process has been proven to be NEXP in the worst case [Bernstein et al., 2002] and solving an infinite-horizon Dec-POMDP is undecidable [Oliehoek and Amato, 2016, Madani et al., 2003]. A key difference compared with POMDPs is that the utility of one agent's policy is not just linked to the dynamics of the environment but also depends on the interactions with other agents and their policies.

There are various techniques for solving Dec-POMDPs, and one can classify algorithms according to several dimensions:

* finite vs infinite temporal horizon;

* explicit vs generative model (simulator);

* reasoning about all agents simultaneously vs one agent at a time;

* types of approach such as value-based, policy search, Bayesian inference, and finding Nash equilibria.

In this chapter, we present a selection of representative techniques for solving Dec-POMDPs organized as follows:

* policy search algorithms that directly search in the joint policy space are presented in Section 3.2;

* methods based on transforming the Dec-POMDP into a (PO)MDP are presented in Section 3.3;

* Section 3.4 gives the methods for searching Nash equilibrium solutions in Dec-POMDPs;

* Section 3.5 presents the sampling-based methods for Dec-POMDPs when explicit models are unavailable.
Then, we conclude in Section 3.6 by positioning our contributions in this domain. But of course, this chapter does not contain all related algorithms, a larger overview can be found in [Oliehoek and Amato, 2016].

## 3.2 Policy Search in Dec-POMDPs

In this section, we introduce approaches that explore the joint policy space by using heuristic search (MAA* [Szer et al., 2005]) or by optimizing the parameterized policies of all the agents (EM methods [Kumar and Zilberstein, 2010, Kumar et al., 2011, Pajarinen and Peltonen, 2011]). More precisely, MAA* solves finite-horizon Dec-POMDPs by transforming the Dec-POMDP into a deterministic shortest-path problem, and EM methods focus on the optimization conducted on fixed-size finite-state controllers (FSCs) for each agent for infinite-horizon setting.

### 3.2.1 Multi-Agent A*

Multi-Agent A* (MAA*) is an optimal heuristic search algorithm for solving finite-horizon Dec-POMDPs. It turns the finite-horizon Dec-POMDP planning into a deterministic shortest-path problem before solving it using an A* search. In MAA*, a joint policy $\delta$ is presented as a vector of individual policy trees. Given a horizon $t$, a joint policy is defined as $\delta^t = (q_1^t, \dots, q_n^t)$ and $q_i^t$ is the policy tree with depth $t$ for agent $i$. Assuming the goal is to solve a Dec-POMDP with horizon $T$, then a completion $\Delta^{T-t}$ is defined as a set of possible policy trees with depth $T-t$ that can be attached to the leaf node of an executed policy tree $\delta^t$. As A*, MAA* defines a *value estimator* $F$ as:

$$F^T(s_0, \delta^t) \stackrel{\text{def}}{=} V(s_0, \delta^t) + H^{T-t}(s_0, \delta^t), \quad (3.1)$$

where $V(s_0, \delta^t)$ is the value from start state $s_0$ with a given joint policy $\delta^t$, and $H$ is the heuristic function which gives an overestimation of the actual value of $\delta^t$'s completion $\Delta^{T-t}$.

To fit MAA* in a standard A* scheme, each joint policy $\delta^t$ is treated as a node. Then, in each iteration, MAA* computes $F^T$ and selects the node with the highest estimated value to expand. The expansion process consists in adding all possible child nodes $\delta^{t+1}$ (which correspond to all possible combinations of all possible expansions of each individual policy tree) to an open list $D$ and removing the visited parent node $\delta^t$ from that open list. The search is finished when its most promising element has a $F$-value smaller (in the maximizing case) than the best complete solution found up to now:

$$\exists \delta^T \in D, \forall \delta \in D, \quad F^T(s_0, \delta) \le F^T(s_0, \delta^T) = V(s_0, \delta^T). \quad (3.2)$$

Thus, an optimal joint policy has been found.

In MAA*, the heuristic function $H$, which overestimates the future expected return (or underestimates the cost-to-go, as for any A* search) is a key ingredient. Three methods are provided for computing $H$ in MAA*:

* $H_{MDP}$: the easiest way is to overestimate the actual value function by relaxing a Dec-POMDP to an MDP. In this case, it assumes that there is only one agent that controls the joint action and has access to the full state of the system.

* $H_{POMDP}$: a tighter estimation consists in relaxing a Dec-POMDP to a POMDP. In this case, all agents are seen as a single one who observes the joint observation and decides the joint action.
* $H_{MAA*}$: this is a heuristic method where another MAA* is used to estimate the $\delta^t$'s completion $\Delta^{T-t}$, thus, leading to a recursive computation. Compared with $H_{MDP}$ and $H_{POMDP}$, no relaxation of Dec-POMDPs has been made by using $H_{MAA*}$. Therefore, it is assumed that this heuristic method can give the tightest estimation, close to the actual value, with enough resources.

Experiments confirm that the $H_{MAA*}$ gives the tightest estimation, and a recursive MAA* search performs better than other heuristics, however, it suffers from heavy computations. A critical issue of MAA* lies in its expansion process, which induces a combinatorial explosion with the increase of $T$. Thus, MAA* is only able to solve small and finite-horizon Dec-POMDPs.

### 3.2.2 Expectation-Maximization (EM) for Dec-POMDPs

Before introducing the Expectation-Maximization (EM) algorithm, we need to know that a single-agent planning problem can be transformed into a probabilistic inference problem.

Attias first proposes such a transformation for some “special” MDPs and POMDPs [Attias, 2003]. Here, we use an MDP case to illustrate how it works. In an MDP, a transition function is denoted as $Pr(s^{t+1}|s^t, a^t)$, and the agent needs to select an action sequence $a_{1:N} = (a_1, ..., a_T)$ that ensures being in the goal state $s^{N+1} = g$ after $N$ time steps. Now, let's define a probability distribution over all sequences of states and actions as follows:

$$ Pr(s_{2:N+1}, a_{1:N}) = \prod_{n=2}^{N} Pr(s_n | s_{n-1}, a_{n-1}) Pr(a_n | a_{n-1}) \cdot Pr(a_1) Pr(s_{N+1} | s_N, a_N), $$

where we have:

$$ Pr(s_n = s' | s_{n-1} = s, a_{n-1} = a) = \lambda_{s'sa}; $$

$$ Pr(a_n = a' | a_{n-1} = a) = \eta_{a'a}; $$

for $n = 2:N+1$, and $Pr(a_1 = a) = \eta_a$ for $n = 1$. Therefore, such an inference model has a parameter set $\theta = \{\lambda_{s'sa}, \eta_{a'a}, \eta_a\}$. Then, a posterior distribution over an action sequence is defined as:

$$ Pr(a_{1:N} | s_1 = s_{init}, s_{N+1} = g), \qquad (3.3) $$

where $s_{init}$ is the initial state. The planning problem is thus turned into maximizing the posterior over actions:

$$ \hat{a}_{1:N} = \arg\max_{a_{1:N}} p(a_{1:N} | s_1 = i, s_{N+1} = g). \qquad (3.4) $$

However, one should note that Attias's formulation is not built for standard MDPs or POMDPs, because it assumes:

1. the solution is constrained to be a fixed sequence of actions; and

2. the objective is to maximize the probability of reaching a goal state (no reward function) after a fixed number of time steps.

A more generic approach for transforming standard MDPs and POMDPs into probabilistic inference can be found in Toussaint et al.'s work [Toussaint et al., 2006].

The Expectation-Maximization (EM) algorithm is a well-known method in machine learning, especially for data mining applications [Jung et al., 2014]. EM is usually used to estimate parameters in statistical models, i.e., a probability distribution, where the model depends on unobserved
variables. Given the model's parameters $\theta$, observed data $y$, and latent data $z$ (unobserved data), the expectation step (E-step) is defined as

$$Q(\theta, \theta^i) = \int_z \log(\Pr(\theta|z, y))\Pr(z|\theta^i, y)dz.$$

This is the expectation of the log-likelihood function of $\theta$ with respect to the conditional distribution of $z$ given the observed data $y$ and current estimates of the parameter $\theta^i$. Then, in the maximization step (M-step), one maximizes the $Q$ function concerning $\theta$ to update $\theta^i$:

$$\theta^{i+1} = \arg\max_{\theta} Q(\theta, \theta^i).$$

A diagram of EM is given in Figure 3.1. First, EM initializes parameter values and assumes the current observed data comes from a specific model (a probability distribution). Then, EM seeks to find the maximum likelihood estimate (MLE) by iteratively applying the E and M steps. EM checks if the assumed model's parameters $\theta^i$ have converged (by testing if the change of parameter value is smaller than a threshold); the algorithm stops if there is a convergence, otherwise the process repeats. The convergence in the EM approach is guaranteed since the data likelihood function is monotonically increased in each iteration. However, EM only guarantees that the converging point has zero gradients with respect to the parameters. Therefore, it may stuck into local optima or saddle points.

With those two necessary steps described above, a new class of Dec-POMDPs algorithms has been proposed [Kumar and Zilberstein, 2010, Kumar et al., 2011, Pajarinen and Peltonen, 2011] that relies on transforming the Dec-POMDP problem into an equivalent mixture of dynamic Bayes networks (DBNs) [Toussaint et al., 2006], where each agent's policy is a fixed-size FSC. Its parameters are optimized iteratively through the EM approach, which gives local optimal solutions.

### 3.2.3 Conclusion

This section introduced various policy searching methods, including MAA* and a series of EM algorithms for solving Dec-POMDPs. For MAA*, the main advantage is its standard A* scheme, where an optimal solution is guaranteed. However, the main issue is its scalability. Since each node in MAA*'s decision tree is a joint policy up to the current depth $t$, the complexity grows exponentially with horizons. Therefore, MAA* is only suitable for small finite-horizon Dec-POMDPs.

On the other hand, by recasting the planning problem into a probabilistic inference problem, the EM approach provides a new class of Dec-POMDP solvers where inference tools could be applied. In general, both finite-horizon and infinite-horizon Dec-POMDPs can be solved within the EM approach. One drawback is that the EM approach is only guaranteed to converge to local optima.

## 3.3 Transforming Dec-POMDPs into (PO)MDPs

In this section, we introduce a type of approach for solving Dec-POMDPs consisting of transforming the Dec-POMDP problem into a Markov decision process whose state is a sufficient statistics of the process, as in FB-HSVI [Dibangoye et al., 2016] and PBVI-BB [MacDermed and Isbell, 2013].
<figure><img src="image_11.png" /><figcaption>Figure 3.1: An illustration of the Expectation-Maximization (EM) algorithm [Do and Batzoglou, 2008].</figcaption></figure>

### 3.3.1 Feature Based HSVI

Dibangoye et al. propose a method called Feature based HSVI (FB-HSVI) for solving finite-horizon Dec-POMDPs. A starting point of FB-HSVI is to transform the Dec-POMDP problem into a continuous MDP using sufficient statistics for planning as a state. This occupancy state $\eta^t$ is a probability distribution over all Dec-POMDP states and joint action-observation histories of all agents. The action space of this MDP is a set of joint decision rules, each joint decision rule is denoted as $d^t$, which is an N-tuple of individual decision rules ($d_1^t, \dots, d_N^t$), one individual decision rule for each agent. Each individual decision rule $d_i^t$ is a mapping from t-step individual histories to individual actions of agent i. Since the occupancy-state is a distribution over states and histories, the next occupancy-state $\eta^{t+1}$ is deterministically controlled by the current occupancy-state $\eta^t$ and joint decision rule $d^t$ where $\eta^{t+1} = F(\eta^t, d^t)$. This being said, this MDP has deterministic dynamics. Thus, solving the Dec-POMDP at hand is equivalent to solving this occupancy-state MDP, where the optimality equation is defined as follows:

$$V_t^*(\eta^t) = \max_{d^t} [R(\eta^t, d^t) + \gamma V_{t+1}^* F(\eta^t, d^t)]. \quad (3.5)$$

Note that this transformation also amounts to deriving a non-observable MDP (NOMDP) [Boutilier et al., 1999], which is a special case of POMDP where the observation space is empty. This NOMDP has the following features:

1. the state comprises the Dec-POMDP state plus each agent's action-observation history (AOH);

2. the horizon is finite, and the state space depends on the time step;

3. the dynamics are deterministic;
4. actions are selected by solving a constraint satisfaction problem (CSP);

5. compression techniques are used that merge equivalent AOHs.

Therefore, a POMDP solver (HSVI) can be applied to solve this continuous MDP, which uses heuristic initializations to initialize a lower and upper bound to direct the search. The lower and upper bounds will converge in the limit, but in practice, the algorithm stops when a precision (a gap) $\epsilon$ is reached.

### 3.3.2 PBVI-BB

*Point Based Value Iteration with Optimal Belief Compression for Dec-POMDPs (PBVI-BB)* [MacDermed and Isbell, 2013] can be seen as a variant of FB-HSVI in the infinite-horizon setting. Like FB-HSVI, one crucial process is transforming the Dec-POMDP into an (PO)MDP with appropriate state and action spaces. To do so, PBVI-BB assumes that each agent has a fixed maximum number of beliefs at each time step. With this assumption, PBVI-BB transforms a Dec-POMDP to a NOMDP where:

1. an agent's individual belief is akin to an internal state;

2. an agent's individual policy thus amounts to an FSC (with bounded size), as the agent alternatively picks an action and the next internal state;

3. the NOMDP's belief is over the current system state and the agents' internal states;

4. in this POMDP, $V^*$ is still PWLC, which allows applying modern POMDP solvers.

In their case, this NOMDP (they call it *Belief-POMDP*) is solved using a POMDP solver Perseus [Spaan and Vlassis, 2005] (a variant of PBVI, see Algorithm 4 on page 20).

#### Conclusion

To summarize, both FB-HSVI and PBVI-BB transform a Dec-POMDP problem into a (PO)MDP problem. This transformation preserves optimal solutions and allows adapting point-based POMDP solvers (HSVI and Persus). In practice, both methods can be used for infinite-horizon Dec-POMDPs. To that end, FB-HSVI approximate infinite-horizon using finite horizons within an error bound [Dibangoye et al., 2014], and $\epsilon$-optimal solutions. Compared with FB-HSVI, PBVI-BB has weaker properties due to (1) the choice of FSCs, and (2) using Perseus instead of HSVI (a variant of HSVI-BB would be $\epsilon$-optimal for a choice of FSC size). But one potential issue is their scalability when facing large problems because of the combinatorial explosion. In the next section, we present algorithms to avoid this issue by iteratively only optimizing one agent's policy considering other agents' policies are fixed.

## 3.4 Finding Nash Equilibria in Dec-POMDPs

This section reviews related works for solving Dec-POMDPs by finding Nash equilibrium solutions where each agent's policy is the best response to others, and no one could improve the global performance by modifying only its own policy.
### 3.4.1 JESP

As we described in Section 2.5, the Joint Equilibrium-based search for policies (JESP) algorithm was first proposed to search Nash equilibria for finite-horizon Dec-POMDPs. In JESP, all agents' policies are randomly initialized using policy trees. Then, JESP iterates over each agent $i$ to improve its policy $\pi_i$ while fixing other agents' policies $\pi_{\ne i}$. This improvement is made by solving an extended state POMDP built for agent $i$, where an extended state $e^t = \langle s^t, \vec{w}_{\ne i}^t \rangle$ consists of the Dec-POMDP state and other agents' observation histories. By solving this POMDP, the agent $i$'s policy $\pi_i'$ is now a best-response to $\pi_{\ne i}$, and the value of the joint policy is at least as good as the previous one (if no improvement, $\pi_i' = \pi_i$). Therefore, in each iteration of JESP, its value monotonically increases and converges to a Nash equilibrium.

However, JESP uses policy trees and thus is limited to the finite-horizon setting. Another drawback is that the JESP scheme has no guarantees of globally optimal solutions, and some random initial policies may converge to very poor local optimum. Therefore, JESP usually needs multiple restarts to find good local optima.

### 3.4.2 Bounded Policy Iteration for Dec-POMDPs (Dec-BPI)

For the infinite-horizon setting, Dec-BPI [Bernstein et al., 2005] is a Dec-POMDP extension of bounded policy iteration (BPI) for POMDPs [Poupart and Boutilier, 2003] and provides a locally optimal solution. In Dec-BPI, agent policies are represented as FSCs. Dec-BPI iterates over the nodes of each agent's FSC and tries to improve one agent's FSC assuming the other agents' policies are fixed. In each node of local policies, linear programming is used to search a new probability distribution over actions and transitions if the value will increase for any initial state and any initial node of other agents' FSCs. Each agent improves its FSC in turn and ends when no improvement can be made on any agent. An improvement of Dec-BPI is optimizing each agent FSC using a non-linear program in each iteration [Amato et al., 2012].

In Dec-BPI, with each iteration's improvement, the value of the joint policy is at least as high as the last iteration. This monotonic improvement ensures that Dec-BPI converges, but with no optimality guarantee. The reason is that, in each iteration of Dec-BPI, only improving one agent's FSC may lead to a sub-optimal Nash equilibrium solution in which each agent's policy is the best response to others' fixed policies (which is similar to JESP [Nair et al., 2003] approach described in Section 3.4.1). However, one should also note that this best-response policy during the improvement can only be obtained in the best case, which is not true in practice. Because in each iteration of Dec-BPI, the optimization of an FSC does not find the optimal parameters. Thus, even the Nash equilibrium solution is not guaranteed by Dec-BPI.

## Conclusion

In this section, we introduce two algorithms, JESP and Dec-BPI, for solving Dec-POMDPs, and both methods try to find Nash equilibrium solutions. JESP guarantees to converge to Nash equilibria but can only be applied to finite-horizon Dec-POMDPs since it uses policy trees. On the other hand, Dec-BPI uses FSCs to represent agents' policies and solves infinite-horizon Dec-POMDPs, but without a guarantee of finding Nash-equilibrium solutions. Last but not least, in Dec-BPI, the improvement in each iteration is made for all initial state distributions. This being said, Dec-BPI finds a local optima solution for any starting belief $b_0$.
## 3.5 Solving Dec-POMDPs with a generative model

Previous sections introduced various methods for solving Dec-POMDPs when explicit models are available. In other words, this requires the exact dynamics of the Dec-POMDP problem we are addressing. However, we often do not have such an explicit model for large problems or real applications where we do not know the transition and observation probabilities. Usually, in this case, only a black-box simulator (also called a generative model) G is available:

$$s', \vec{o}, r \leftarrow G(s, \vec{a}). \qquad (3.6)$$

The inputs of G are the current state s and joint action $\vec{a}$ of all agents. Then, it outputs the next state $s'$, the observations $\vec{o}$ for all agents, and the instant reward r. This section introduces several sampling-based methods for Dec-POMDPs requiring only a generative model G.

### 3.5.1 Monte-Carlo Expectation Maximization (MCEM) based algorithms for solving Dec-POMDPs

MCEM for Dec-POMDPs [Wu et al., 2013] is a model-free version of the EM approach we introduced in Section 3.2.2. Like the EM methods for solving Dec-POMDPs, MCEM based approach optimizes $\theta$, which is the parameter of each agent’s FSC with a fixed size. For the EM algorithm, one relies on the explicit model to compute Equation (3.3). In the MCEM approach, this computation is approximated by a Monte-Carlo integration as follows:

$$Q_{i+1}(\theta, \theta^{i+1}) = \frac{1}{m} \sum_{j=1}^{m} \log(\mathrm{Pr}(\theta|z^j, y)). \qquad (3.7)$$

The samples $\{z^1, \dots, z^m\}$ are generated from the current approximation to the conditional distribution $\mathrm{Pr}(z|\theta^i, y)$. Then, the M-step consists in maximizing Equation (3.7), and the conditional distribution is updated with the new maximizer. The algorithm iterates until convergence to a local optimal or a saddle point.

One improvement is constructing agents’ FSCs with variable sizes as in Dec-SBPR (Stick-Breaking Policy learning for Dec-POMDPs) [Liu et al., 2015] to eliminate two side effects of fixed-size FSCs: an overly small number won’t be able to represent good policies, and an overly large number will cause an over-fitting problem and slow convergence.

### 3.5.2 Occupancy-State SARSA (oSARSA):

Similar to FB-HSVI introduced in Section 3.3.1, oSARSA [Dibangoye and Buffet, 2018] is also interested in recasting Dec-POMDPs into occupancy-state MDPs. Instead of using policies, oSARSA computes plans which are linear functions over occupancy states and joint decision rules since it is simple to store and update while having an optimal performance for Dec-POMDPs. Compared with FB-HSVI, greedy or soft maximization is replaced by mixed-integer linear programming to save resources and scale up better. Given enough resources and an accurate estimation of the occupancy states, oSARSA can converge to a near-optimal plan for finite-horizon Dec-POMDPs.

## 3.6 Conclusion

To sum up, in this chapter, we introduced various algorithms for solving Dec-POMDPs, which can be categorized as:
* algorithms that optimize the policies of all the agents simultaneously, including MAA*, FB-HSVI, and PBVI-BB. For MAA*, it finds an optimal solution in a standard A* scheme for finite-horizon Dec-POMDPs. On the other hand, FB-HSVI and PBVI-BB transform a Dec-POMDP to a (PO)MDP and solve it with POMDPs techniques. Both FB-HSVI and PBVI-BB can be used for infinite-horizon Dec-POMDPs, and FB-HSVI gives $\epsilon$-optimal solutions by approximating infinite-horizon using finite horizons within an error bound. Moreover, oSARSA extends the FB-HSVI to the generative model setting where an explicit Dec-POMDP is unavailable. However, all those methods may face a combinatorial explosion issue when facing large problems.

* algorithms that alternate between agents, including JESP and Dec-BPI, which avoid this combinatorial explosion of all agents' policies by optimizing each agent's policy in turn while considering others' policies are fixed. But its associated drawback is that such methods can only find Nash equilibria at best. In this category, JESP is limited to finite horizons, and Dec-BPI can be used for infinite-horizon Dec-POMDPs with any starting state distribution.

* algorithms based on the EM approach transform the Dec-POMDP planning problem into a probabilistic inference. Each agent's policy is represented as an FSC, and its parameters are optimized using the EM algorithm. EM-based methods can be used for infinite-horizon settings, and an adaption of Monte-Carlo integration extends their usage with generative models. However, EM methods only guarantee to converge to local optima or even worse saddle points.

Moreover, we conclude those representative Dec-POMDP algorithms in Figure 3.2, to our knowledge, the JESP scheme has been introduced to neither infinite-horizon nor simulator-based settings. Therefore, in this thesis, two of our main contributions (see Chapter 4) consist of: 1. a first algorithm that extends the JESP approach to the infinite-horizon setting called Inf-JESP; 2. an extension of Inf-JESP that works with generative models (MC-JESP).
<figure><img src="image_12.png" /><figcaption>Figure 3.2: An overview of representative algorithms for Dec-POMDPs: The area colored with light green gives the methods based on transforming Dec-POMDPs to (PO)MDPs with sufficient statistics; The light pink area contains algorithms that directly search in the joint policy space; Algorithms that find Nash equilibrium solutions are presented inside the light blue area. All those methods are also categorized with the temporal horizons (finite or infinite) and model types (explicit model or generative model).</figcaption></figure>
# Searching for an Equilibrium in an Infinite-Horizon Multi-agent Problem

As we discussed in Chapter 2, a Decentralized Partially Observable Markov Decision Process (Dec-POMDP) represents a multi-agent sequential decision-making problem where the objective is to derive the policies of all agents so that their decentralized execution maximizes the average cumulative reward. Each agent's policy is a mapping from his individual history (the sequence of his executed actions and received observations up to now) to individual actions. However, solving a Dec-POMDP is difficult and is proved to be NEXP complete in the worst case [Bernstein et al., 2002]. The main difficulties when solving a Dec-POMDP lie in two aspects: first, the state of the environment evolves according to all agents' actions; and, second, each agent picks his actions based on his own action-observation history, making it difficult for agents to coordinate. Therefore, all policies are interdependent, which means each agent's optimal decision depends on others' possible histories and future policies.

In this thesis, most of our contributions rely on computing the best response to other agents. For instance, in our contributions to compute robust robot policies for HRC in Chapter 6, the robot policy is the best response to possible human behaviors. For solving Dec-POMDPs, we are interested in finding a Nash equilibrium solution consisting of each agent's policy being a best response to the other agents' policies. To that end, we propose to solve Dec-POMDPs through a JESP approach (Joint Equilibrium-Based Search for Policies) [Nair et al., 2003], which searches for Nash equilibrium solutions by optimizing each agent's policy one after the other while fixing the other's policies, until convergence (see Figure 4.1). However, JESP has two weaknesses:

1. in JESP, policies are represented by trees; therefore, this algorithm addresses only finite-horizon Dec-POMDPs;

2. the Nash equilibria solutions obtained by JESP are local but not global optima.

This thesis addresses JESP's first drawback by extending it to the infinite-horizon setting. Our starting point is to rely not on policy trees but on finite-state controllers (FSCs). Then, we demonstrate how to derive the (best-response) POMDP faced by an agent while other agents' policies are fixed. From there, we solve this POMDP to find individual best-response policies (in FSCs), and integrate this step into a JESP scheme.

We propose two novel algorithms in this chapter based on the above ideas. The first algorithm (Inf-JESP), presented in Section 4.1, solves Dec-POMDPs with explicit models. And the second method (MC-JESP), shown in Section 4.2, assumes that generative models of Dec-POMDPs (i.e., simulators) are available. Experiments on state-of-the-art benchmark problems have been
<figure><img src="image_13.png" /><figcaption>Figure 4.1: JESP’s iterative optimization process for a 2-agent problem, starting with policies $\pi_1$ and $\pi_a$</figcaption></figure>

conducted to evaluate our algorithms in Section 4.3. Finally, we conclude this chapter and discuss perspectives in Section 4.4.

# 4.1 Infinite-Horizon JESP

The JESP algorithm finds Nash equilibrium solutions by iteratively building one agent’s best response to other agents’ fixed policies. JESP (with its policy trees) is meant for a finite-horizon setting. Although one can approximate an infinite-horizon Dec-POMDP as a finite-horizon one, this approximation usually needs a long horizon (see Equation (2.18)). Thus, it requires overly large policy trees and extended state spaces for the POMDP built in each iteration of JESP (see Section 2.5). Also, no action is prescribed when going beyond this approximated long horizon (because any action can be applied), which the end-user may not appreciate. Therefore, those drawbacks make JESP unsuitable for solving infinite-horizon problems. To address this issue, we propose solving infinite-horizon Dec-POMDPs using finite state controller (FSC) policy representations in a JESP scheme. FSCs are meant to represent infinite-horizon policies, and we try to control their size in our work. We call this new algorithm Inf-JESP.

Inf-JESP’s main algorithm is introduced in Section 4.1.1, and we explain how to combine FSCs with a Dec-POMDP to generate the POMDP required at each iteration of Inf-JESP in Section 4.1.2. Then, in order to use state-of-the-art point-based POMDP solvers, Section 4.1.3 proposes an algorithm to generate an agent’s FSC from a set of $\alpha$-vectors. Moreover, heuristic initialization methods are provided in Section 4.1.4.

## 4.1.1 Inf-JESP Main Algorithm

Inf-JESP relies on a local search procedure, which is typically restarted multiple times with different random initializations to converge to different local optima. This local search, presented in this section, relies iteratively on (i) defining the best-response POMDP for each agent based on the policies of other agents (see Section 4.1.2), and (ii) solving it to extract and evaluate the associated FSC (see Section 4.1.3). (Note that we also provide experiments with a non-random initialization of Inf-JESP, which is described in Section 4.1.4)

As described in Algorithm 6, each agent’s policy is represented as an FSC. To control the computational cost at each iteration, the size of solution FSCs is bounded by a parameter $K \in \mathbb{N}^*$.
The local search thus starts with $|\mathcal{I}|$ randomly generated $K$-FSCs in vector $fsc$ (line 2). Then, it loops over the agents, each iteration attempting to improve an agent $i$'s policy by finding (line 7) a $K$-FSC $fsc'_i$ that is a best response to the current (fixed) FSCs $fsc_{\ne i}$ of the $|\mathcal{I}| - 1$ other agents (denoted $\ne i$). Line 8 relies on Equation (2.21) (page 19) to evaluate $\langle fsc'_i, fsc_{\ne i} \rangle$ at $b_0$, unless the POMDP solver at line 7 provides this information. Then, in line 10, if an improved solution has been found, $fsc'_i$ replaces $fsc_i$ in $fsc$. The process stops if the number of consecutive iterations without improvement, $\#ni$, reaches $|\mathcal{I}|$.

<caption>**Algorithm 6: $\infty$-horizon JESP**</caption>

1 [Input:] $K$: FSC size $|fsc|$: initial FSCs
2 **Fct LocalSearch**($K, fsc \stackrel{\text{def}}{=} \langle fsc_1, \dots, fsc_{|\mathcal{I}|} \rangle$)
3 &nbsp;&nbsp;&nbsp; $v_{bestL} \leftarrow \text{eval}(fsc)$
4 &nbsp;&nbsp;&nbsp; $\#ni \leftarrow 0$ &nbsp;&nbsp;&nbsp;&nbsp; // $(\text{iterations w/o improvement})$
5 &nbsp;&nbsp;&nbsp; $i \leftarrow 1$ &nbsp;&nbsp;&nbsp;&nbsp; // Id of current agent
6 &nbsp;&nbsp;&nbsp; **repeat**
7 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $fsc'_i \leftarrow \text{Solve2FSC}(fsc_{\ne i}, K)$
8 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $v \leftarrow \text{eval}(fsc'_i, fsc_{\ne i})$
9 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $v > v_{bestL}$ **then**
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $fsc_i \leftarrow fsc'_i$ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; // replace the current agent $i$'s policy with an improved one
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $v_{bestL} \leftarrow v$
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\#ni \leftarrow 0$
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **else**
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lfloor \#ni \leftarrow \#ni + 1 \rfloor$
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $i \leftarrow (i \bmod |\mathcal{I}|) + 1$
16 &nbsp;&nbsp;&nbsp; **until** $\#ni = |\mathcal{I}|$ &nbsp;&nbsp;&nbsp;&nbsp; // looped over agents w/o improving
17 &nbsp;&nbsp;&nbsp; **return** $\langle fsc, v_{bestL} \rangle$

**Properties** For agent $i$, each of its $K$ nodes is attached to an action in $A_i$, and each of its $K \times |\Omega|$ edges is attached to a node, so that the number of deterministic FSCs $|\mathcal{FSC}_i|$ is at most $|A_i^K \cdot K^{K \times |\Omega|}$.<fnref n="2" /> Thus, assuming an optimal POMDP solver leads to the following properties.

**Proposition 1** Inf-JESP's local search converges in finitely many iterations to a Nash equilibrium.

**Proof 1** The search only accepts increasingly better solutions so that the number of iterations (over all agents) is, at most, the number of possible solutions: $|\mathcal{FSC}| = \prod_i |\mathcal{FSC}_i|$.

The search stops when all agents have no more improvements by only modifying their own policies. This being said, each agent's FSC is a best response to the other agents' FSCs, i.e., in a Nash equilibrium.

While these equilibria are only local optima, allowing for infinitely many random restarts guarantees to converge to a global optimum with probability 1. Of course, the set of Nash

<footnote n="2">²The exact number is smaller due to symmetries and because, in some FSCs, not all internal nodes are reachable.</footnote>
equilibria depends on the set of policies at hand, thus on the parameter *K* in our setting. Increasing *K* just allows for more policies, and thus possibly better Nash equilibria.

In practice (see Section 4.1.2), we use a sub-optimal POMDP solver in **Solve2FSC** (line 7) in which FSC sizes are implicitly bounded (*K* is not actually used) because the solving time is bounded. If this POMDP solver returns a solution $fsc'_i$ worse than $fsc_i$, it will be ignored, so that monotonic improvements are preserved, and the search still necessarily terminates in finite time. Final solutions may be close to Nash equilibria if the POMDP solver returns $\epsilon$-optimal solutions.

### 4.1.2 Building Best-Response POMDP for Agent *i*

As we introduced in Section 2.5, in each iteration, an extended state POMDP is built for agent *i* while considering that other agents' policies $\pi_{\ne i}$ are known and fixed. Solving this POMDP will derive a policy for agent *i*, which is the best response to other agents' fixed policies $\pi_i$. In this chapter, we call this POMDP for agent *i* a best-response POMDP (BR-POMDP). In JESP's finite horizon setting, the state in agent *i*'s best-response POMDP' is denoted $e^t \stackrel{\text{def}}{=} \langle s^t, \vec{\omega}_{\ne i}^t \rangle$, with $s^t$ the current state and $\vec{\omega}_{\ne i}^t$ the observation histories of other agents. Agent *i* maintains a belief $b_{JESP}^t$ over $e^t$, which is a sufficient statistic for planning as it allows predicting the system's evolution (including other agents) as well as future expected rewards. However, as we pointed out above, in infinite-horizon problems, the number of observation histories $\vec{\omega}_{\ne i}^t$ grows exponentially with time, making for an infinite state space. We thus consider using FSCs to represent other agents' policies so that agent *i* can reason about other agents' internal nodes instead of their histories. But then, an important question is raised: how to derive a valid BR-POMDP for agent *i* given the Dec-POMDP and other agents' FSCs?

In Inf-JESP, to construct a BR-POMDP for agent *i* in each iteration, we first need to decide which variables are contained in its extended state $e^t$. Then, the action and observation sets of this BR-POMDP should correspond to the action and observation sets of this agent *i* as defined in the Dec-POMDP model. Moreover, the choice we made for the extended state, along with agent *i*'s actions and observations, has to guarantee that we get a proper POMDP that contains valid transition, observation, and reward functions. In this section, we present one possible way to construct this BR-POMDP, but we also provide other possible formalizations in appendix (see Section A.1). Here, we choose to represent the extended state $e^t \in \mathcal{E}$ as shown in Figure 4.2, i.e., containing:

* $s^t$, the current state of the Dec-POMDP problem;

* $n_{\ne i}^t \equiv \langle n_1^t, \dots, n_{i-1}^t, n_{i+1}^t, \dots, n_n^t \rangle$, the nodes of the $|\mathcal{I}| - 1$ other agents' (agents $\ne i$) FSCs at the current time step, and;

* $o_i^t$, agent *i*'s current observation.

We thus have $\mathcal{E} \stackrel{\text{def}}{=} \mathcal{S} \times \mathcal{N}_{\ne i} \times \Omega_i$. Given an action $a_j^t$, the extended state $e^t = \langle s^t, n_{\ne i}^t, o_i^t \rangle$ evolves according to the following steps:

1. each agent $j \ne i$ selects its action $a_j^t$ based on its current node;

2. $s^t$ transitions to $s^{t+1}$ according to $T$ under joint action $a^t = \langle a_i^t, a_{\ne i}^t \rangle$; and

3. the FSC nodes of agents $j$ (including $i$) evolve jointly according to their observations $o_j^{t+1}$, which can be inferred from $s^{t+1}$ and the joint action $a^t$; these observations may not be independent from each other, so that the FSC nodes may not evolve independently from each other.
This design choice for $e^t$ induces a POMDP because of the following properties:

* it induces a Markov process controlled by the action (see dynamics below);

* the observation $o_i^t$ depends on $a_i^t$ and $e^{t+1}$; and

* the reward depends on $e^t$ and $a_i^t$.

Indeed, deriving the transition, observation, and reward functions for this POMDP (as detailed in Appendix Sec. A.1) leads to:

$$ 
\begin{aligned}
T_e(e^t, a_i^t, e^{t+1}) &= Pr(e^{t+1} | e^t, a_i^t) \\
&= \sum_{o_{\neq i}^{t+1}} T(s^t, \langle \psi_{\neq i}(n_{\neq i}^t), a_i^t \rangle, s^{t+1}) \cdot \eta_{\neq i}(n_{\neq i}^t, o_{\neq i}^{t+1}, n_{\neq i}^{t+1}) \\
&\qquad \cdot O(s^{t+1}, \langle \psi_{\neq i}(n_{\neq i}^t), a_i^t \rangle, \langle o_{\neq i}^{t+1}, o_i^{t+1} \rangle),
\end{aligned}
$$

$$ 
\begin{aligned}
O_e(a_i^t, e_i^{t+1}, o_i^{t+1}) &= Pr(o_i^{t+1} | a_i^t, e_i^{t+1}) \\
&= Pr(o_i^{t+1} | a_i^t, \langle s^{t+1}, n_{\neq i}^{t+1}, \tilde{o}_i^{t+1} \rangle) \\
&= \mathbf{1}_{o_i^{t+1} = \tilde{o}_i^{t+1}}, \\
r_e(e^t, a_i^t) &= r(s^t, a_i^t, \psi_{\neq i}(n_{\neq i}^t)),
\end{aligned}
$$

where $\eta_{\neq i}(n_{\neq i}^t, o_{\neq i}^{t+1}, n_{\neq i}^{t+1}) = \prod_{j \neq i} \eta(n_j^t, \tilde{o}_j^{t+1}, n_j^{t+1})$ and $\psi_{\neq i}(n_{\neq i}^t) = a_{\neq i}^t$.

Note that, if some of the state variables are fully observable, then the problem is more precisely a *Mixed Observability Markov Decision Processes* (MOMDP), and this mixed observability can be exploited to accelerate the solving process [Ong et al., 2009, Araya-López et al., 2010]. But, since this is not the priority in this thesis, we only consider standard POMDP solvers.

Moreover, we observe that some extended states will never be reached starting from the initial belief. We thus make $\mathcal{E}$ smaller through a *state elimination* process. More specifically, we first initialize $\mathcal{E}$ by computing all possible starting extended states given the initial belief $b_0$, and an open list is initialized with the same elements. Then, an extended state $e^t$ is popped out from this open list and processed with all possible agent $i$'s actions to gather possible $s^{t+1}$, $n_{\neq i}^{t+1}$, and $o_i^{t+1}$, which result in a list of next possible extended states $\{e^{t+1}\}$. If an extended state in $\{e^{t+1}\}$ does not exist in $\mathcal{E}$, we insert it to $\mathcal{E}$ and the open list. We repeat this process until the open list is empty. At the end of the process, $\mathcal{E}$ contains only the extended states that are reachable from the initial belief.

### 4.1.3 Building Agent $i$'s FSC with bounded size

In Section 4.1.2, we presented how to build a best-response POMDP for agent $i$ considering others' fixed policies. Then, once the BR-POMDP for agent $i$ is built, we need a POMDP solver to obtain agent $i$'s policy. As we introduced in Section 2.3.3, there are different types of POMDP solvers. For Inf-JESP, we take advantage of modern point-based solvers and choose SARSOP [Kurniawati et al., 2008] for solving the built POMDP, but other point-based approaches such as PBVI [Pineau et al., 2003] or HSVI [Smith and Simmons, 2004] are also applicable. On the other hand, the policy search methods [Hansen, 1997, Spaan and Vlassis, 2005] can directly give an FSC that can be used to build the next BR-POMDP, but they are usually less efficient than state-of-the-art point-based solvers.
<figure><img src="image_14.png" /><figcaption>Figure 4.2: An illustration of the best-response POMDP for agent *i* based on the Dec-POMDP model and other agents’ fixed FSCs.</figcaption></figure>

**Algorithm Description** In Section 2.3.2 (page 19), we mentioned that one could transform a set of α-vectors Γ to an FSC, and Grześ et al. proposed an approximate method *Alpha2FSC*. However, Alpha2FSC assumes each α-vector in Γ (the POMDP solution) comes with an associated belief. This assumption is not true in our work (with the POMDP solver SARSOP), and we need to compute a representative belief for each α-vector. Therefore, we propose a new transformation method as presented in Algorithm 7, to turn an α-vector set Γ into an FSC. In our method, each FSC node $n \stackrel{\text{def}}{=} \langle \alpha, a, b, w \rangle$ contains an α-vector $\alpha$ with its (sometimes omitted) action $a$, and a representative belief $b$ (weighted average of the encountered beliefs mapped to this node) with its positive weight $w$. This weight tries to capture the importance of the attached node by approximating its visit frequency and is computed incrementally when building the FSC.

More specifically, Algorithm 7 begins by a start node $n_0$ from $b_0$ and $\Gamma$ with $w = 1$ (line 2), and adds it to both the new FSC ($N$) and an open list ($G$). Then, each $n$ in $G$ is processed (in `PIO` order) with each observation $o_i$ as follows (0-probability observations induce a self-loop (line 22)). Lines 10–12 compute the updated belief $b_{o_i}^n$, and the associated $w'$ and $\alpha_i$. The node $n' \in N$ that contains $\alpha_i$ is extracted if it exists and $b_{o_i}^n$ is merged into its representative belief (lines 18–20), otherwise a new node $n' \stackrel{\text{def}}{=} \langle \alpha_i, b_{o_i}^n, w' \rangle$ is created (line 14) and added to both $N$ and $G$. An edge $n \to n'$, labeled with $o_i$, is then added (line 23).

Note that our method (as Alpha2FSC) returns an FSC that approximates the policy induced by the α-vectors set Γ (which might need a possibly infinite FSC to represent). This approximation leads to an FSC result that may be better or worse compared with Γ.

**About Self-Loops** As in Grześ et al.’s work, self-loops are added when an impossible observation $Pr(o_i|b, a_i) = 0$ is received. This may happen because, when building the FSC, each node $n_i$ is associated to a tuple $\langle \alpha_i, b_i \rangle$, and outgoing edges from $n_i$ will be created only for observa-
tions that have non-zero probability in $b_i$. Yet, during execution, $n_i$ may be reached while in a different belief $b'$ from which $a_i$ (the action attached to $\alpha_i$, thus $n_i$) may induce “unexpected” observations.<fnref n="3" /> Adding self-loops is a way to equip the agent with a default strategy when such an unexpected observation occurs.

**Differences with Alpha2FSC** There are three differences in our method compared with Grześ et al.'s work: First, in [Grześ et al., 2015], each input α-vector comes with an associated belief, while we instead try to compute a belief representative of the reachable beliefs “attached” to the vector. Second, in [Grześ et al., 2015], each α-vector induces an FSC node ($|N| = |\Gamma|$), while we only consider α-vectors reachable by the algorithm from $b_0$. Third, in our JESP setting, we have another reason for adding self-loops. Indeed, each agent *i*'s FSC is obtained considering fixed agent ≠ *i*'s FSCs; yet, changing other agents' FSCs will induce a new POMDP from *i*'s point of view, potentially with new possible observations when in certain nodes of $fsc_i$.

<caption>**Algorithm 7:** Extract FSC $\langle N, \eta, \psi \rangle$ from set $\Gamma$</caption>

1 [Input:] $\Gamma$: α-vector set
2 Start node $n_0 \leftarrow node(\langle \arg\max_{\alpha \in \Gamma}(\alpha \cdot b_0), b_0, 1 \rangle)$
3 $N \leftarrow \{n_0\}$
4 $G.pushback(n_0)$
5 **while** $|G| > 0$ **do**
6 $n \leftarrow G.popfront()$
7 $\langle b, a_i, w \rangle \leftarrow \langle n.b, \psi(n), n.w \rangle$
8 **forall** $o_i \in \Omega_i$ **do**
9 $\quad$ **if** $Pr(o_i|b, a_i) > 0$ **then**
10 $\quad\quad$ $b_{a_i}^{o_i} \leftarrow beliefUpdate(b, a_i, o_i)$
11 $\quad\quad$ $w' \leftarrow w \cdot Pr(o_i|b, a_i)$
12 $\quad\quad$ $\alpha_i \leftarrow argmax_{\alpha \in \Gamma}(\alpha \cdot b_{a_i}^{o_i})$
13 $\quad$ **if** $\alpha_i \notin N$ **then**
14 $\quad\quad$ $n' \leftarrow node(\langle \alpha_i, b_{a_i}^{o_i}, w' \rangle)$
15 $\quad\quad$ $N \leftarrow N \cup \{n'\}$
16 $\quad\quad$ $G.pushback(n')$
17 $\quad$ **else**
18 $\quad\quad$ $n' \leftarrow N(\alpha_i)$
19 $\quad\quad$ $n'.b \leftarrow \frac{n'.w}{n'.w+w'} \cdot n'.b + \frac{w'}{n'.w+w'} \cdot b_{a_i}^{o_i}$
20 $\quad\quad$ $n'.w \leftarrow n'.w + w'$
21 $\quad$ **else**
22 $\quad\quad$ $n' \leftarrow n$
23 $\quad\quad$ $\eta(n, o_i) \leftarrow n'$
24 **return** $\langle N, \eta, \psi \rangle$

Note that this algorithm does not bound the resulting number of internal nodes explicitly. Instead, we rely on (i) SARSOP returning finitely many α-vectors, and (ii) the FSC extraction

<footnote n="3">³This will happen when some state *s* has zero-probability in $b_i$ but not in $b'$ and can induce this observation when performing $a_i$.</footnote>
producing (significantly) less than $|\Gamma|$ internal nodes. But one can easily limit the FSC size with a given bound as presented in our second main contribution (see Algorithm 11, page 48).

Once $fsc_i$ is obtained, the next step is to evaluate all agents' policies in the Dec-POMDP. To that end, it is sufficient to evaluate $fsc_i$ in the corresponding best-response POMDP, since the latter combines in a single model the Dec-POMDP and the FSCs for agents $\neq i$. Here we used the FSC evaluation technique described in Section 2.3 on page 19, which computes an FSC's value function by solving a system of linear equations.

### 4.1.4 Heuristic Initialization

As previously mentioned, the initialization of Inf-JESP is important. Even if Inf-JESP improves the value of the joint FSC at each iteration, random initializations may often lead to poor local optima. Thus, we want to investigate if some non-random heuristic initializations allow to find good solutions quickly and reliably.

Our method relies on assuming public observations in the Dec-POMDP, so that we are facing a Multi-agent POMDP (MPOMDP) [Pynadath and Tambe, 2002], i.e., a problem that is formally equivalent to a POMDP and thus solved using a POMDP solver. We extract individual FSCs from the resulting MPOMDP policy as detailed below, and use them to initialize Inf-JESP.

**MPOMDP-based Stochastic Initial FSC (M-S)** – Algorithm 14 extracts a policy $fsc_i$ for agent $i$ from an MPOMDP policy. This approach is similar to Algorithm 7, the main difference being that agents $\neq i$'s observations and actions should also be considered to compute a next belief. Yet, this is not actually feasible since agent $i$ is not aware of them. To address this issue, given agent $i$, let us consider a current node $n = \langle \alpha, b \rangle$ and an individual observation $o_i$ (i.e., with non-zero occurrence probability). The MPOMDP solution specifies a joint action $a = \langle a_i, a_{\neq i} \rangle$ at $b$, $a$ being the action attached to $\alpha$. We arbitrarily assume that (i) each possible stochastic transition of the FSC (from $n$ and coming with observation $o_i$) corresponds to a possible joint observation $o_{\neq i}$ of the other agents, (ii) such a transition occurs with probability $Pr(o_{\neq i} | b, a, o_i)$, and (iii) it “leads” to a new belief $b_a^{\langle o_i, o_{\neq i} \rangle}$ and thus a node $n'$ attached to the dominating MPOMDP $\alpha$-vector ($\alpha_i$, cf. line 12) at this point. As only one FSC node should correspond to a given $\alpha$-vector, a new $n'$ attached to $\alpha_i$ is created only if necessary (lines 13, 14 and 18). As multiple joint observations $o_{\neq i}$ may lead to the same $n'$, the corresponding transition probabilities are cumulated in $\eta(n, o_i, n')$ (line 19). 0-probability joint observations $o_{\neq i}$ given $b, a$ and $o_i$ are ignored. 0-probability individual observations $o_i$ given $b$ and $a$ induce the creation of a self-loop (line 21). This self-loop allows the FSC to still be a valid policy against any possible policies of other agents, which may change in the next iteration.

Note that the resulting FSCs are stochastic, and some of them may never be improved on, so that, in this case, the solution returned by Inf-JESP may contain stochastic FSCs.

**MPOMDP-based Deterministic Initial FSC (M-D)** – A very simple variant of this method is to assume that the only possible transition from $n$ under $o_i$ corresponds to the most probable joint observation $o_{\neq i}$ of the other agents. In this case, lines 10 and 11 are modified as follows:

$$o_{\neq i} \leftarrow \arg \max_{o_{\neq i} \in \Omega_{\neq i}} Pr(o_{\neq i} | o_i, b, a). \qquad (4.1)$$

The transition between nodes is then deterministic ($\eta(n, o_i, n') = 1$).
<caption>**Algorithm 8:** Extracting FSC<sub>i</sub> for agent *i* from MPOMDP α-vector set Γ</caption>

1 [Input:] *i*: agent | Γ: MPOMDP α-vector set
2 Start node *n*₀ ← node(argmax<sub>α∈Γ</sub> α · *b*₀, *b*₀)
3 *N* ← {*n*₀}
4 *G.pushback*(*n*₀)
5 **while** |*G*| > 0 **do**
6 | *n* ← *G.popfront*()
7 | (*b*, *a*) ← (*n*·*b*, ψ(*n*))
8 | **forall** *o*ᵢ ∈ Ωᵢ **do**
9 | | **if** Pr(*o*ᵢ|*b*, *a*) > 0 **then**
10 | | | **forall** *o*ᵢ≠ᵢ ∈ Ωᵢ≠ᵢ **do**
11 | | | | **if** Pr(*o*ᵢ≠ᵢ|*o*ᵢ, *b*, *a*) > 0 **then**
12 | | | | | *α*ᵢ ← argmax<sub>α</sub>(*b*<sup>*o*ᵢ, *o*ᵢ≠ᵢ</sup><sub>a</sub>, Γ)
13 | | | | **if** *α*ᵢ ∉ *N* **then**
14 | | | | | *n'* ← node(*α*ᵢ, *b*<sup>*o*ᵢ, *o*ᵢ≠ᵢ</sup><sub>a</sub>)
15 | | | | | *N* ← *N* ∪ {*n'*}
16 | | | | | *G.pushback*(*n'*)
17 | | | | **else**
18 | | | | | *n'* ← *N*(*α*ᵢ)
19 | | | | | η(*n*, *o*ᵢ, *n'* ← η(*n*, *o*ᵢ, *n'* + Pr(*o*ᵢ≠ᵢ|*o*ᵢ, *b*, *a*)
20 | | | | **else**
21 | | | | | η(*n*, *o*ᵢ, *n*) ← 1
22 **return** ⟨*N*, η, ψ⟩

**MPOMDP-based Average-Belief Initial FSC (M-A) –** Algorithm 9 provides another way to extract a policy *fsc*<sub>*i*</sub> for agent *i* from an MPOMDP policy. In this heuristic initialization, we assume that all agents share the same belief *b* and act according to the same joint action *a*. Then, the belief is updated by agent *i* by marginalizing agents ≠ *i*'s possible observations to ignore them. This *one-sided-observation belief update* (line 10) is obtained as follows:

$$
\Pr(s'|o_i, \langle a_i, a_{\ne i} \rangle, b) = \frac{\Pr(s', o_i, \langle a_i, a_{\ne i} \rangle, b)}{\Pr(o_i, \langle a_i, a_{\ne i} \rangle, b)} \quad (4.2)
$$

$$
= \frac{\sum_s \sum_{o_{\ne i}} \Pr(s', s, \langle o_i, o_{\ne i} \rangle, \langle a_i, a_{\ne i} \rangle, b)}{\sum_{s'} \sum_s \sum_{o_{\ne i}} \Pr(s', s, \langle o_i, o_{\ne i} \rangle, \langle a_i, a_{\ne i} \rangle, b)} \quad (4.3)
$$

$$
= \frac{\sum_{o_{\ne i}} \Pr(\langle o_i, o_{\ne i} \rangle | s', \langle a_i, a_{\ne i} \rangle) \sum_s \Pr(s' | s, \langle a_i, a_{\ne i} \rangle) b(s)}{\sum_{s'} \sum_s \sum_{o_{\ne i}} \Pr(\langle o_i, o_{\ne i} \rangle | s', \langle a_i, a_{\ne i} \rangle) \Pr(s' | s, \langle a_i, a_{\ne i} \rangle) b(s)} \quad (4.4)
$$

$$
= \frac{\sum_{o_{\ne i}} O(\langle o_i, o_{\ne i} \rangle | \langle a_i, a_{\ne i} \rangle, s') \sum_s T(s, \langle a_i, a_{\ne i} \rangle, s') b(s)}{\sum_{s'} \sum_s \sum_{o_{\ne i}} O(\langle o_i, o_{\ne i} \rangle | \langle a_i, a_{\ne i} \rangle, s') T(s, \langle a_i, a_{\ne i} \rangle, s') b(s)}. \quad (4.5)
$$

Notes:

1. As all (i) these heuristic initialization methods and (ii) Inf-JESP's local search are deterministic, using a deterministic procedure to derive best-response FSCs induces a deterministic algorithm for which restarts are useless.
2. These heuristic initialization methods can be also adapted to the finite-horizon setting for JESP by changing the policy representation to finite-horizon trees.

<caption>**Algorithm 9:** Extracting FSC<sub>i</sub> for agent *i* from MPOMDP α-vector set Γ</caption>

1 [Input:] *i*: agent | Γ: MPOMDP α-vector set
2 Start node *n*₀ ← node(*argmax*<sub>α∈Γ</sub> *α* · *b*₀, *b*₀)
3 *N* ← {*n*₀}
4 *G.pushback*(*n*₀)
5 **while** |*G*| > 0 **do**
6 | *n* ← *G.popfront*()
7 | (*b*, *a*) ← (*n*.*b*, *ψ*(*n*)
8 | **forall** *o*ᵢ ∈ Ωᵢ **do**
9 | | **if** Pr(*o*ᵢ|*b*, *a*) > 0 **then**
10 | | | *α* ← argmax<sub>*α* ∈ Ωᵢ</sub>(*b*ᵢ, Γ)
11 | | **if** *α* ∉ *N* **then**
12 | | | *b*ᵢ ← BeliefUpdateOneSide(*b*, *a*, *o*ᵢ)
13 | | *n'* ← node(*α*, *b*ᵢ)
14 | | *N* ← *N* ∪ {*n'*}
15 | | *G.pushback*(*n'*)
16 | | **else**
17 | | | *n'* ← *N*(*α*)
18 | | *η*(*n*, *o*ᵢ, *n'* ← 1
19 | | **else**
20 | | | *η*(*n*, *o*ᵢ, *n*) ← 1
21 **return** ⟨*N*, *η*, *ψ*⟩

For Inf-JESP, we tested M-S and M-D heuristic initialization methods. Since the results are already good, implementing M-A for Inf-JESP is not our main priority and will be considered as a future perspective.

## 4.2 Monte-Carlo JESP

In Section 4.1, we presented the Inf-JESP algorithm, which solves Dec-POMDPs by finding Nash equilibria solutions with explicit models. However, explicit models are not always available, especially for large problems. Building an explicit model may cost a lot of computational resources and memory. In this section, we present another algorithm based on the Monte-Carlo search in a JESP scheme, which only requires a generative model, i.e., a simulator. We name this algorithm *MC-JESP*. Also, as Inf-JESP, we will use FSCs to represent agent policies. In Section 4.2.1, we present how to use the generative Dec-POMDP model and other agents’ policies to build a *best-response generative model* for agent *i*, and we introduce its relation with the best-response POMDP detailed in Section 4.1.2. Then, Section 4.2.2 describes how to build agent *i*'s FSC policy with its best-response generative model. MC-JESP's main algorithm and an initialization method are presented in Section 4.2.3.
### 4.2.1 Building Best Response Generative Model for Agent *i*

Similar to Inf-JESP, we aim to find Nash equilibrium solutions by iteratively building each agent's best response to other agents' fixed policies. We thus stick to representing policies as FSCs since we still address infinite-horizon problems, and we rely on the same formalism for best-response POMDPs as in Inf-JESP, i.e., in particular with the same representations of extended states, actions, and observations. However, the method described in Section 4.1.2 for building the best response POMDP for agent *i* is only possible if we have an explicit Dec-POMDP model. Then, a question for MC-JESP is how to build such a best response model if only a generative model of the Dec-POMDP is available? To address this issue, in MC-JESP, we propose an alternative approach that builds a best-response generative model relying on a Dec-POMDP simulator and other agents' FSCs. In the following content, we call this model "$G_{BR}$" for simplicity.

**Algorithm Description:** The problem of building a $G_{BR}$ for agent *i* is to sample the next extended state $e^{t+1}$, observation $o_i^{t+1}$, and reward $r^{t+1}$, given a current extended state $e^t$ and action $a_i^t$, and as shown in Figure 4.3, we can only rely on the available functions of the Dec-POMDP simulator and other agents' FSCs. Algorithm 10 details the process of building such an extended generative model for agent *i*. It first decomposes the extended state, and gets other agents' actions $a_{\ne i}^t$ according to action selection functions $\psi_{\ne i} \equiv \langle \psi_1, \dots, \psi_{i-1}, \psi_{i+1}, \dots, \psi_{|I|} \rangle$ (lines 3 and 4). Then, in line 5, the joint action $\langle a_i^t, a_{\ne i}^t \rangle$ is passed to the Dec-POMDP simulator *G*, which outputs the next state $s^{t+1}$, joint observation $\langle o_i^{t+1}, o_{\ne i}^{t+1} \rangle$ and instant reward $r^{t+1}$. With the obtained others' observation $o_{\ne i}^{t+1}$, line 6 computes their next nodes $n_{\ne i}^{t+1} \equiv \langle n_1^{t+1}, \dots, n_{i-1}^{t+1}, n_{i+1}^{t+1}, \dots, n_{|I|}^{t+1} \rangle$. In the end, we build the next extended state $s_e^{t+1}$ and return the results (lines 7 and 8). In this algorithm, stochasticity exists only in the Dec-POMDP simulator *G*, the FSC functions $\psi$ and $\eta$ are deterministic.

<caption>**Algorithm 10: Agent *i*'s Best Response Generative Model $G_{BR-POMDP}$**</caption>

1. [Input:] $s_e^t$: extended state | $a_i^t$: agent *i*'s action
2. [Parameter:] *G*: Dec-POMDP simulator | $\langle N_{\ne i}, \psi_{\ne i}, \eta_{\ne i} \rangle$: other agents' FSCs
3. $\langle s^t, n_{\ne i}^t, o_i^t \rangle \leftarrow s_e^t$
4. $a_{\ne i}^t \leftarrow \psi_{\ne i}(n_{\ne i}^t)$
5. $s^{t+1} = \langle o_i^{t+1}, o_{\ne i}^{t+1} \rangle$, $r^{t+1} \leftarrow G(s^t, \langle a_i^t, a_{\ne i}^t \rangle)$
6. $n_{\ne i}^{t+1} \leftarrow \eta(n_{\ne i}^t, o_{\ne i}^{t+1})$
7. $s_e^{t+1} \leftarrow \langle s^{t+1}, n_{\ne i}^{t+1}, o_i^{t+1} \rangle$
8. **return** $s_e^{t+1}, o_i^{t+1}, r^{t+1}$

$\triangleright$ return step results

### 4.2.2 Computing Agent *i*'s FSC using Monte Carlo Methods

In the previous section, we saw how to build the best-response generative model $G_{BR-POMDP}$ for agent *i* considering others' fixed FSCs. However, unlike in Inf-JESP, modern point-based POMDP solvers can not be applied to solve such generative models in MC-JESP. We thus need to rely on a simulation-based solver, i.e., POMCP [Silver and Veness, 2010], which is an online algorithm that gives only the best action for the current belief. Therefore, the question is how to use a simulator ($G_{BR}$) and a simulation-based solver to obtain agent *i*'s FSC. To address this issue, we propose an algorithm that
<figure><img src="image_15.png" /><figcaption>Figure 4.3: Structure of the best-response generative model $G_{BR}$: The black arrows are the inputs and outputs of the POMDP generative model; The blue arrows show the inputs and outputs of a Dec-POMDP simulator $G$; The green arrows show the evolution of agents $\neq i$'s FSCs.</figcaption></figure>

* uses the Monte-Carlo approach (POMCP) to compute the best action for a given node, which is labeled by a unique belief;

* expands reachable beliefs and creates new nodes using computed actions to gradually build an FSC.

Moreover, to avoid building an infinite-size FSC (with infinite-size beliefs), we explicitly bound the FSC size with a given parameter $N_{max-fsc}$.

**Algorithm Description:** We use Algorithm 11 to build a policy $fsc_i$ for agent $i$ with bounded size $N_{max-fsc}$ given its best-response generative model $G_{BR}$. First, POMCP is used to compute agent $i$'s best action $a_i^0$ at the start belief in line 4. Then, before creating a new node, we process the computed action for the given belief (line 5). This *ProcessAction* function samples many transitions until each feasible observation (according to the samples) is attached to a sufficient number of particles $N_{min-particles}$ (line 31), and returns the set of feasible observations $\Omega_i^{t+1}$ and the set of induced beliefs $B_i^{t+1}$ (each belief is a collection of particles). Then, in line 6, a start node $n_0$ is created with $b_{BR}^0, a_i^0, B_i^1, \Omega_i^1$, and a weight $w = 1$. This start node is added to the FSC under construction ($N$) and an open list ($L$). While $L$ is not empty, $L$ is sorted according to the node weights $w$ (from higher weights to lower weights), and the first node $n$ stored in the sorted $L$ is popped out (lines 10–11). Node $n$'s compatibility with each individual observation $o_i$ is then checked, i.e., $o_i \in n.\Omega_i$, and self-loops are introduced for impossible observations (line 27). Line 14 gets the new belief of receiving observation $o_i$, and a new associated weight $w' = w$ is computed in line 15. Then, line 16 computes agent $i$'s best action $a_i'$ given its new belief $b_{BR}'$ using POMCP. Before creating a new node $n'$, in line 17, the algorithm verifies (i) the non-existence of $b_{BR}'$,
i.e., measuring the distance between (estimated) belief states in Norm-1 and comparing it to $\epsilon$: $\|b'_{BR} - b\|_1 \le \epsilon$; and (ii) if the current FSC size is smaller than $N_{max-fsc}$. If those conditions are not satisfied, we update the weight of the closest existing node (lines 23–24); otherwise, $n'$ is added to both $N$ and $L$ (lines 19–21). In line 25, an edge $n \to n'$ is created with a label $o_i$.

### 4.2.3 Main Algorithm and Initialization

**Main Algorithm:** The main algorithm of MC-JESP is presented in Algorithm 12. Compared with Inf-JESP's main algorithm, the differences are threefold:

* in line 7, MC-JESP needs to construct a best-response generative model $G_{BR}$ for agent $i$ in each iteration, while Inf-JESP constructs an explicit best-response POMDP model;

* MC-JESP uses a Monte-Carlo method to construct agent $i$'s FSC (line 8) which differs from Inf-JESP's extraction process (see Algorithm 7);

* simulations are conducted in line 9 to estimate the value obtained using agent $i$'s policy $f_{sc_i}$ under initial distribution $b_{BR}^0$ with simulator $G_{BR}$, while in Inf-JESP, the value can be directly computed following a system of linear equations (see Equation (2.21)).

As in Inf-JESP, the FSC size is bounded in MC-JESP, and in each iteration of MC-JESP, the value improves monotonically (assuming perfect evaluation of FSCs). Therefore, the search will necessarily terminate in finite time. In the end, the final solution may be close to a Nash equilibrium, given that POMCP is an approximate online solver.

**Heuristic Initialization:** Although MC-JESP monotonically improves the value of the joint policy at each iteration, some random initializations may lead to poor locally optimal solutions. Therefore, based on Algorithm 11, we develop a heuristic initialization method for MC-JESP similar to the one used in Inf-JESP (we use the same MPOMDP extraction process and belief update method as described for Algorithm 9). Algorithm 13 shows the process to build a heuristic FSC for agent $i$. As shown in red, it differs from Algorithm 11 in two aspects:

* the Dec-POMDP simulator $G$ is used as an MPOMDP simulator for POMCP to get the best joint action with a given belief (lines 3 and 16);

* instead of a standard belief update, we use a one-sided-belief-update method (lines 4 and 18) which is first presented in Equation (4.2) when using an exact model. The *ProcessAction* function repeatedly samples transitions using the computed joint action and collects particles for each encountered agent $i$'s observation.

## 4.3 Experiments

This section evaluates our contributions with other state-of-the-art solvers on various Dec-POMDP benchmarks (cf. http://masplan.org/problem_domain):

* Decentralized Tiger (Dec-Tiger) [Nair et al., 2003],

* Recycling Robots (Recycling) [Amato et al., 2012],

* Meeting in a 3 × 3 grid (Grid 3 × 3) [Amato et al., 2009],
<caption>**Algorithm 11:** Compute agent *i*'s FSC</caption>

1 **[Input:]** $b_{BR}^0$: initial (extended) state distribution of $G_{BR}$
2 **[Parameters:]** $G_{BR}$: best response generative model for agent *i* | $N_{max-fsc}$: max FSC size for agent *i* | $N_{min-particles}$: minimum particle size for each belief
3 **Fct BuildFSC**($b_{BR}^0$)
4 &nbsp;&nbsp;&nbsp;&nbsp;$a_i^0 \leftarrow POMCP(G_{BR}, b_{BR}^0)$
5 &nbsp;&nbsp;&nbsp;&nbsp;$B_i^1, \Omega_i^1 \leftarrow ProcessAction(b_{BR}^0, a_i^0)$
6 &nbsp;&nbsp;&nbsp;&nbsp;$n_0 \leftarrow node(b_{BR}^0, a_i^0, B_i^1, \Omega_i^1, w = 1)$
7 &nbsp;&nbsp;&nbsp;&nbsp;$N \leftarrow \{n_0\}$
8 &nbsp;&nbsp;&nbsp;&nbsp;$L[w] \leftarrow n_0$
9 &nbsp;&nbsp;&nbsp;&nbsp;**while** $|L| > 0$ **do**
10 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$L.sort()$
11 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$n \leftarrow L.popfront()$
12 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**for** $o_i \in \Omega$ **do**
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $o_i \in n.\Omega_i$ **then**
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$b'_{BR} \leftarrow n.B'_i(o_i)$
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$w' \leftarrow n.w * \frac{|B'_i(o_i)|}{|B'_i|}$
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$a'_i \leftarrow POMCP(G_{BR}, b'_{BR})$
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $(b'_{BR} \notin N(\epsilon)) \land (N.size < N_{max})$ **then**
18 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$B''_i, \Omega''_i \leftarrow ProcessAction(b'_{BR}, a'_i)$
19 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$n' \leftarrow node(b'_{BR}, a'_i, B''_i, \Omega''_i, w')$
20 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$N \leftarrow N \cup \{n'\}$
21 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$L[w] \leftarrow n'$
22 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
23 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$n' \leftarrow N.find(b'_{BR})$
24 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$n'.w \leftarrow n'.w + w'$
25 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\eta(n, o_i, n') \leftarrow 1$
26 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**else**
27 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\eta(n, o_i, n) \leftarrow 1$
28 **Fct ProcessAction**($b_{BR}^t, a_i^t$)
29 &nbsp;&nbsp;&nbsp;&nbsp;$B_i^{t+1} \leftarrow \emptyset$
30 &nbsp;&nbsp;&nbsp;&nbsp;$\Omega_i^{t+1} \leftarrow \emptyset$
31 &nbsp;&nbsp;&nbsp;&nbsp;**repeat**
32 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$e^t \sim b_{BR}^t$
33 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\langle e^{t+1}, o_i^{t+1}, o_{\neq i}^{t+1}, r^{t+1} \rangle \sim G_{BR}(e^t, a_i^t)$
34 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**if** $o_i^{t+1} \notin \Omega_i^{t+1}$ **then**
35 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$\lfloor \Omega_i^{t+1} \leftarrow \Omega_i^{t+1} \cup \{o_i^{t+1}\} \rfloor$
36 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;$B^{t+1}[o_i^{t+1}] \leftarrow B^{t+1}[o_i^{t+1}] \cup \{e^{t+1}\}$
37 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**until** $Timeout() \lor (MinBeliefParticles(B^{t+1}) > N_{min-particles})$
38 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** $B_i^{t+1}, \Omega_i^{t+1}$
<caption>**Algorithm 12:** Monte-Carlo JESP</caption>

1 [Input:] K: FSC size | fsc: initial FSCs | b⁰: initial belief | G: Dec-POMDP simulator
2 Fct LocalSearch(K, fsc def = ⟨fsc₁, ..., fsc|I|⟩, G)
3 | vbestL ← eval(fsc)
4 | #ni ← 0 // #(iterations w/o improvement)
5 | i ← 1 // Id of current agent
6 | repeat
7 | GBR, b₀BR ← BuildBestResponseGenerativeModel(G, b⁰, fsc≠i)
8 | fsc'_i ← ComputeFSC(b₀BR | GBR, K)
9 | v ← EvalSim(fsc'_i, b₀BR | GBR)
10 | if v > vbestL then
11 | | fsc_i ← fsc'_i
12 | | vbestL ← v
13 | | #ni ← 0
14 | else
15 | | #ni ← #ni + 1
16 | i ← (i mod |I|) + 1
17 | until #ni = |I|
18 | return ⟨fsc, vbestL⟩

• Cooperative Box Pushing (Box-Pushing) [Seuken and Zilberstein, 2007],

• Mars Rover [Amato and Zilberstein, 2009].

The evaluation of Inf-JESP is presented in Section 4.3.1 and compared with other Dec-POMDP solvers which rely on explicit models. Section 4.3.2 evaluates MC-JESP, which only requires a Dec-POMDP simulator, and we compare MC-JESP's results with other existing Dec-POMDP solvers (including algorithms relying on explicit models and simulators). Moreover, all the evaluations are conducted in an infinite-horizon setting.

## 4.3.1 Evaluation of Inf-JESP

### Algorithm settings

We compare the different variants of Inf-JESP with state-of-the-art Dec-POMDP solvers, namely: FB-HSVI [Dibangoye et al., 2016], Peri [Pajarinen and Peltonen, 2011], PeriEM [Pajarinen and Peltonen, 2011], PBVI-BB [MacDermed and Isbell, 2013] and MealyNLP [Amato et al., 2010]. We ignore JESP as it only handles finite horizons with policy trees, and it will cost a large number of memories and time to approximate infinite horizons with long horizons. Dec-BPI is compared separately because we can only estimate values from empirical curves on some benchmark problems [Bernstein et al., 2009].

For Inf-JESP, SARSOP [Kurniawati et al., 2008] is used as our POMDP solver, with a 0.001 Bellman residual (also for FSC evaluation) and a 5 s timeout. Moreover, we have tested 4 variants of Inf-JESP:

• IJ(M-D) and IJ(M-S) are Inf-JESP initialized with the M-D and M-S heuristics (Section 4.1.4) and without restarts (because they behave deterministically).
<caption>**Algorithm 13: Build a heuristic FSC for agent i**</caption>

1 [Input:] $b^0$: initial state distribution of G | i: heuristic agent index
2 [Parameter:] G: Dec-POMDP simulator | $N_{max}$: max FSC size for agent i
3 $\langle a_i^0, a_{\neq i}^0 \rangle \leftarrow POMCP(G, b^0)$
4 $B_i^1, \Omega_i^1 \leftarrow ProcessAction(b^0, \langle a_i^0, a_{\neq i}^0 \rangle)$
5 $n_0 \leftarrow node(b^0, a_i^0, B_i^1, \Omega_i^1, w = 1)$
6 $N \leftarrow \{n_0\}$
7 $G[w] \leftarrow n_0$
8 **while** $|G| > 0$ **do**
9 &nbsp;&nbsp;&nbsp;&nbsp; $G.sort()$
10 &nbsp;&nbsp;&nbsp;&nbsp; $n \leftarrow G.popfront()$
11 &nbsp;&nbsp;&nbsp;&nbsp; $\langle b, a \rangle \leftarrow n$
12 &nbsp;&nbsp;&nbsp;&nbsp; **for** $o_i \in \Omega$ **do**
13 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $o_i \in n.\Omega_i$ **then**
14 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $b' \leftarrow n.B_i'(o_i)$
15 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $w' \leftarrow n.w * \frac{|B_i'(o_i)|}{|B_i'|}$
16 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\langle a_i', a_{\neq i'}' \rangle \leftarrow POMCP(G, b')$
17 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **if** $(b' \notin N(\epsilon)) \land (N.size < N_{max})$ **then**
18 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $B_i'', \Omega_i'' \leftarrow ProcessAction(b', \langle a_i', a_{\neq i'}' \rangle)$
19 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $n' \leftarrow node(b', a_i', B_i'', \Omega_i'', w')$
20 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $N \leftarrow N \cup \{n'\}$
21 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $G[w] \leftarrow n'$
22 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; **else**
23 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $n' \leftarrow N.find(b')$
24 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $n'.w \leftarrow n'.w + w'$
25 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\eta(n, o_i, n') \leftarrow 1$
26 &nbsp;&nbsp;&nbsp;&nbsp; **else**
27 &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; $\lfloor \eta(n, o_i, n) \leftarrow 1 \rfloor$

* IJ(R-1) and IJ(R-100) are Inf-JESP with random initializations (at most 5 nodes per FSC) and, respectively, 1 (re)start and 100 restarts.

Each restart has a timeout of 7200 s (2 h), and IJ(R-x<sub>y</sub>) denotes y runs of IJ(R-x) used to compute statistics. Due to a large number of iterations which often lead to a timeout and cost memories, we did not perform full random-restart tests on the Box-Pushing and Mars Rover domains.

The experiments with Inf-JESP were conducted on a laptop with an i5-1.6 GHz CPU and 8 GB RAM. The source code is available at https://gitlab.inria.fr/ANR-FCW/InfJESP.

Comparison with state-of-the-art algorithms

Table 4.1 presents the results for the 5 problems. For IJ(R-x<sub>y</sub>), we kept the highest value among the restarts in each run, and then computed the average of this value over the various runs. The columns provide:

* (Alg.) the different algorithms at hand;
<table><caption>Table 4.1: Comparison of different algorithms in terms of final FSC size, number of iterations, time, and value, on five infinite-horizon benchmark problems with $\gamma = 0.9$ for all domains. R-R$_N$ = N runs with R random restarts each. M-S and M-D = deterministic initializations with stochastic FSCs and deterministic FSCs extracted from an MPOMDP solution. Solvers are arranged in descending order by their values.</caption><thead><tr><th>Alg.</th><th>FSC size</th><th>#Iterations</th><th>Time (s)</th><th>Value</th></tr></thead><tbody><tr><td colspan="5">DecTiger (|I| = 2, |S| = 2, |A<sup>i</sup>| = 3, |Z<sup>i</sup>| = 2)</td></tr><tr><td>FB-HSVI</td><td></td><td></td><td>154</td><td>13.45</td></tr><tr><td>PBVI-BB</td><td></td><td></td><td></td><td>13.45</td></tr><tr><td>Peri</td><td></td><td></td><td>220</td><td>13.45</td></tr><tr><td><b>IJ(R-100<sub>5</sub>)</b></td><td>9±3 × 8±4</td><td>33 ±1</td><td>12 418</td><td>13.44</td></tr><tr><td><b>IJ(M-D)</b></td><td>6 × 6</td><td>36</td><td>201</td><td>13.44</td></tr><tr><td><b>IJ(M-S)</b></td><td>6 × 6</td><td>27</td><td>213</td><td>13.44</td></tr><tr><td>PeriEM</td><td></td><td></td><td>6450</td><td>9.42</td></tr><tr><td>MealyNLP</td><td></td><td></td><td>29</td><td>-1.49</td></tr><tr><td><b>IJ(R-1<sub>500</sub>)</b></td><td>29±55 × 32±54</td><td>21 ±14</td><td>124</td><td>-35.47</td></tr><tr><td colspan="5">Recycling (|I| = 2, |S| = 4, |A<sup>i</sup>| = 3, |Z<sup>i</sup>| = 2)</td></tr><tr><td>FB-HSVI</td><td></td><td></td><td>3</td><td>31.93</td></tr><tr><td>PBVI-BB</td><td></td><td></td><td></td><td>31.93</td></tr><tr><td>MealyNLP</td><td></td><td></td><td>0</td><td>31.93</td></tr><tr><td>Peri</td><td></td><td></td><td>77</td><td>31.84</td></tr><tr><td>PeriEM</td><td></td><td></td><td>272</td><td>31.80</td></tr><tr><td><b>IJ(R-100<sub>10</sub>)</b></td><td>2±0 × 2±0</td><td>3 ±0</td><td>3</td><td>31.62</td></tr><tr><td><b>IJ(R-1<sub>1000</sub>)</b></td><td>3±2 × 3±2</td><td>3 ±0</td><td>0</td><td>30.60</td></tr><tr><td><b>IJ(M-S)</b></td><td>8 × 8</td><td>3</td><td>0</td><td>26.57</td></tr><tr><td><b>IJ(M-D)</b></td><td>4 × 4</td><td>3</td><td>0</td><td>25.65</td></tr><tr><td colspan="5">Grid3*3 (|I| = 2, |S| = 81, |A<sup>i</sup>| = 5, |Z<sup>i</sup>| = 9)</td></tr><tr><td><b>IJ(M-D)</b></td><td>8 × 10</td><td>3</td><td>2</td><td>5.81</td></tr><tr><td><b>IJ(M-S)</b></td><td>9 × 17</td><td>3</td><td>9</td><td>5.81</td></tr><tr><td><b>IJ(R-100<sub>5</sub>)</b></td><td>13±6 × 9±0</td><td>4 ±0</td><td>414</td><td>5.81</td></tr><tr><td>FB-HSVI</td><td></td><td></td><td>67</td><td>5.80</td></tr><tr><td><b>IJ(R-1<sub>500</sub>)</b></td><td>11±18 × 11±18</td><td>3 ±1</td><td>4</td><td>5.79</td></tr><tr><td>Peri</td><td></td><td></td><td>9714</td><td>4.64</td></tr><tr><td colspan="5">Box-pushing (|I| = 2, |S| = 100, |A<sup>i</sup>| = 4, |Z<sup>i</sup>| = 5)</td></tr><tr><td>FB-HSVI</td><td></td><td></td><td>1715</td><td>224.43</td></tr><tr><td>PBVI-BB</td><td></td><td></td><td></td><td>224.12</td></tr><tr><td><b>IJ(M-S)</b></td><td>250 × 408</td><td>6</td><td>963</td><td>220.25</td></tr><tr><td><b>IJ(M-D)</b></td><td>274 × 342</td><td>8</td><td>1436</td><td>203.41</td></tr><tr><td>Peri</td><td></td><td></td><td>5675</td><td>148.65</td></tr><tr><td>MealyNLP</td><td></td><td></td><td>774</td><td>143.14</td></tr><tr><td>PeriEM</td><td></td><td></td><td>7164</td><td>106.65</td></tr><tr><td colspan="5">Mars Rover (|I| = 2, |S| = 256, |A<sup>i</sup>| = 6, |Z<sup>i</sup>| = 8)</td></tr><tr><td>FB-HSVI</td><td></td><td></td><td>74</td><td>26.94</td></tr><tr><td><b>IJ(M-D)</b></td><td>125 × 183</td><td>6</td><td>122</td><td>26.91</td></tr><tr><td><b>IJ(M-S)</b></td><td>84 × 64</td><td>5</td><td>66</td><td>24.17</td></tr><tr><td>Peri</td><td></td><td></td><td>6088</td><td>24.13</td></tr><tr><td>MealyNLP</td><td></td><td></td><td>396</td><td>19.67</td></tr><tr><td>PeriEM</td><td></td><td></td><td>7132</td><td>18.13</td></tr></tbody></table>
• (FSC size) the final FSC sizes obtained for Inf-JESPs;

• (Iterations) the number of iterations required to converge (for Inf-JESPs);

• (Time) the running time, recorded in seconds;

• (Value) the final value (lower bounds for Inf-JESPs; the true value is at most 0.01 higher).

In terms of final value achieved, Inf-JESP variants find good to very good solutions in most cases, often very close to FB-HSVI's near-optimal solutions. Comparing with estimated values obtained by Dec-BPI on the Dec-Tiger, Grid, and Box-Pushing problems (using the figures in [Bernstein et al., 2009, p. 123]), Inf-JESP outperforms Dec-BPI in these three problems. Note also that Dec-BPI's results highly depend on the size of the considered FSCs and that Dec-BPI faces difficulties with large FSCs, e.g., in the Dec-Tiger problem [Bernstein et al., 2009].

Regarding the solving time, Inf-JESP variants have different behaviors depending on the problem at hand. For example, in Dec-Tiger, IJ(M-S) and IJ(M-D) have almost the same solving time, and both of them require more time than IJ(R-1<sub>500</sub>). However, in other problems, IJ(M-D) and IJ(M-S) may require very different solving times. For instance, IJ(M-D) converges faster than IJ(M-S) in Grid but behaves contrary in Box-pushing and Mars Rover domains. As mentioned above, we give a timeout of 5 s for SARSOP in each iteration to solve one agent's POMDP. In Dec-Tiger, most of the time is spent calling SARSOP for multiple iterations, but in Box-Pushing and Mars Rovers, most of the time is used for building the explicit POMDP model and evaluating the obtained FSC in each iteration. Overall, IJ(M-D) and IJ(M-S) can give good solutions within an acceptable time.

Last but not least, we observe that the number of iterations before converging behaves in-
dependently of the solving time. For example, the shortest solving time in Dec-Tiger does not
correspond to the smallest number of iterations.

A Closer Look at Inf-JESP’s behavior

Figure 4.4 (right) presents the distribution over final values of IJ(R-1). Most runs end with (near) globally optimal values in the three problems at hand, despite initial FSCs limited to 5 nodes. Other local optima turn out to be rarely obtained, except in Dec-Tiger. These distributions show that few restarts are needed to reach a global optimum with high probability.

Figure 4.4 (left) presents the evolution of the FSC values during a JESP run as a function of the iteration number for IJ(R-1) (average + 10th and 90th percentiles, in blue), IJ(M-D) (in green) and IJ(M-S) (in red). For random initialization (IJ(R-1)), at each iteration, the average is computed over all runs, even if they have already converged. This figure first shows that (i) Inf-JESP’s solution quality monotonically increases during a run, and (ii) most runs converge to local optima in a few iterations. It also illustrates that MPOMDP initializations are rather good heuristics compared to random ones but, as expected, do not always lead to a global optimum. For example, in the Recycling problem, the MPOMDP heuristic leads to a sub-optimal solution, while random initializations often lead to near-globally-optimal (thus better) solutions.

Complementary results

Regarding *state elimination* (as explained in Section 4.1.2), it turned out that, for the “MOMDP”
best-response POMDP, the ratio of the initial number of (extended) states over its number of
states after state elimination depends on the problem at hand, but does not depend on the Inf-
JESP run (see Figure 4.5). This ratio was 1 for the Dec-Tiger problem, 50 for the Grid problem,
<figure><img src="image_16.png" /><figcaption>Figure 4.4: Values of the joint policy for the Dec-Tiger, Grid and Recycling problems (from top to bottom). The left part of each figure presents the evolution (during a run) of the value of the joint policy at each iteration of: IJ(R-1) (avg + 10th and 90th percentiles in blue), and the deterministic IJ(M-D) (in red) and IJ(M-S) (in green). The dashed line represents FB-HSVI's final value. The right part presents the value distribution after convergence of IJ(R-1).</figcaption></figure>
<figure><img src="image_17.png" /><figcaption>Figure 4.5: Effect of the state elimination for the Dec-Tiger, Grid and Recycling problems (from left to right). Each figure plots, for each Best-Response POMDP obtained while executing Inf-JESP(R-1₁), the number of states of that POMDP after state elimination as a function of that number before state elimination.</figcaption></figure>

<figure><img src="image_18.png" /><figcaption>Figure 4.6: Sizes of the final FSCs obtained with Inf-JESP(R-1₁) after convergence for the Dec-Tiger, Grid and Recycling problems (from left to right). Each dot corresponds to a pair containing the sizes of both agents’ FSCs.</figcaption></figure>

and 5 for the Recycling problem. These differences are due to the stochasticity of the observation process, which limits or even prevents state elimination. As it is currently done, state elimination is based on the probability of generating a specific observation from a state considering possible actions. However, for the Dec-Tiger problem, every observation can be generated whatever the considered action, leading to no state elimination (contrary to the Grid and the Recycling problem).

Regarding the size of the final FSCs obtained after convergence of an Inf-JESP run with a random initialization (see Figure 4.6), we also observed different behaviors. Applied to the Dec-Tiger problem, Inf-JESP leads to a very large distribution of the sizes of the final FSCs. Applied to the Recycling problem, Inf-JESP also leads to a large distribution of the sizes of the final FSC, but the sizes of the FSCs of both agents are symmetrical. Applied to the Grid problem, Inf-JESP generates a large number of FSC pairs of size 10 with sometimes huge variation and with a tendency to be asymmetrical, the first optimized agent having a tendency to have more FSC nodes. These results need to be further investigated in order to understand them clearly and see if it is possible to link them to the nature of the addressed domain.

It must also be noted that the sizes of the FSCs do not monotonically increase during one Inf-JESP iteration (data not presented here). Sometimes the size of the FSC computed during one Inf-JESP improvement decreases, meaning that the solution to the best-response POMDP is an FSC with a smaller size but a higher value (as commonly observed in the Dec-Tiger problem). When looking at the FSCs obtained at the end of one Inf-JESP run on Figure 4.7, another observed phenomenon is that the more iterations required to reach the equilibrium, the smaller
<figure><img src="image_19.png" /><figcaption>Figure 4.7: Sum of the sizes of the final FSCs obtained with Inf-JESP(R-1₁) after convergence as a function of the required number of iterations for the Dec-Tiger, Grid and Recycling problems (from left to right).</figcaption></figure>

<figure><img src="image_20.png" /><figcaption>Figure 4.8: Value of the final FSCs obtained with Inf-JESP(R-1₁) after convergence as a function of the required number of iterations for the Dec-Tiger, Grid and Recycling problems (from left to right).</figcaption></figure>

the sizes of the final FSCs. But this does not mean that the associated value is higher (see Figure 4.8).

Finally, Figure 4.9 presents the values of the obtained equilibria as a function of the sum of sizes of the FSCs obtained by Inf-JESP(R-1₁) after convergence. It can be observed that small FSCs seem to be sufficient to generate a high value, opening new directions on combining Inf-JESP with FSC compression.

**Summary** Those experiments showed that Inf-JESP exhibits different behaviors depending on the problem at hand. For instance, removing unreachable extended states (Section 4.1.2) divides

<figure><img src="image_21.png" /><figcaption>Figure 4.9: Value of the final FSCs obtained with Inf-JESP(R-1₁) after convergence as a function of the sum of the sizes of final FSCs for the Dec-Tiger, Grid and Recycling problems (from left to right).</figcaption></figure>
their number on average by

* 1 in Dec-Tiger;

* 50 in Grid3×3, and;

* 5 in Recycling.

We also observed that final FSCs with the highest values are not obtained with more iterations and do not contain more nodes. Small FSCs seem sufficient to obtain good solutions, opening an interesting research direction to combine Inf-JESP with FSC compression, e.g., one may want to force restarts to use small FSCs at the beginning, and then only progressively increase the maximum FSC size.

### 4.3.2 Evaluation of MC-JESP

#### Algorithm settings

The experiments with MC-JESP were conducted on a laptop with a 2.3 GHz i9 CPU. We compare MC-JESP with two types of state-of-the-art Dec-POMDP solvers:

* algorithms which rely on explicit models: FB-HSVI [Dibangoye et al., 2016], Peri [Pajarinen and Peltonen, 2011], PeriEM [Pajarinen and Peltonen, 2011], PBVI-BB [MacDermed and Isbell, 2013], MealyNLP [Amato et al., 2010] and Inf-JESP; and

* algorithms which rely on generative models: MCEM [Wu et al., 2013], Dec-SBPR [Liu et al., 2015] and oSARSA [Dibangoye and Buffet, 2018].

Although MC-JESP is a sampling-based algorithm, we still compared it with the methods which rely on explicit models to show MC-JESP's power. For MC-JESP, POMCP is used as our sampling-based POMDP planner with a timeout of 5 s. Moreover, we experiment with MC-JESP using three different bounds on the FSC sizes: 10, 30, and 50, respectively, when building each agent's best-response policy.

#### Comparison with state-of-the-art algorithms

Table 4.2 presents the results for the 5 problems in which the solvers are ordered from best to worse value. For MC-JESP(M-x), we kept the highest value among x restarts and then computed the average of this value over the various runs in MC-JESP(M-1x). The columns provide:

* (Alg.) the different algorithms at hand, with a * exponent for those who rely on an explicit model;

* (FSC size) the final FSC size (for Inf-JESP and MC-JESP respectively);

* (Iterations) the number of iterations required to converge (for Inf-JESPs and MC-JESP);

* (Time) the running time;

* (Value) the final value (lower bounds for Inf-JESPs and MC-JESP, the true value being at most 0.01 higher).
<table><caption>Table 4.2: Comparison of different algorithms in terms of final FSC size, number of iterations, time, and value, on five infinite-horizon benchmark problems with $\gamma = 0.9$ for all domains. The solvers are listed in a decreasing order of value.</caption><thead><tr><th>Alg.</th><th>FSC size</th><th>Iterations</th><th>Time (s)</th><th>Value</th></tr></thead><tbody><tr><td colspan="5">DecTiger (|I| = 2, |S| = 2, |A<sup>i</sup>| = 3, |Z<sup>i</sup>| = 2)</td></tr><tr><td>FB-HSVI*</td><td></td><td></td><td>154</td><td>13.45</td></tr><tr><td>Peri*</td><td></td><td></td><td>220</td><td>13.45</td></tr><tr><td>INF-JESP*</td><td>6 × 6</td><td>27</td><td>213</td><td>13.44</td></tr><tr><td>MC-JESP(M-20)</td><td>10 × 10</td><td>5</td><td></td><td>13.44</td></tr><tr><td>PeriEM*</td><td></td><td></td><td>6450</td><td>9.42</td></tr><tr><td>oSARSA</td><td></td><td></td><td></td><td>-0.20</td></tr><tr><td>MC-JESP(M-1<sub>20</sub>)</td><td>10 × 10</td><td>3</td><td>235</td><td>-5.86</td></tr><tr><td>Dec-SBPR</td><td></td><td></td><td>96</td><td>-18.63</td></tr><tr><td>MCEM</td><td></td><td></td><td>20</td><td>-32.31</td></tr><tr><td colspan="5">Recycling (|I| = 2, |S| = 4, |A<sup>i</sup>| = 3, |Z<sup>i</sup>| = 2)</td></tr><tr><td>FB-HSVI*</td><td></td><td></td><td>3</td><td>31.93</td></tr><tr><td>Peri*</td><td></td><td></td><td>77</td><td>31.84</td></tr><tr><td>PeriEM*</td><td></td><td></td><td>272</td><td>31.80</td></tr><tr><td>INF-JESP*</td><td>2 × 2</td><td>3</td><td>3</td><td>31.62</td></tr><tr><td>Dec-SBPR</td><td></td><td></td><td>147</td><td>31.26</td></tr><tr><td>MC-JESP(M-20)</td><td>50 × 50</td><td>3</td><td></td><td>31.12</td></tr><tr><td>MC-JESP(M-1<sub>20</sub>)</td><td>50 × 50</td><td>3</td><td>606</td><td>30.51</td></tr><tr><td colspan="5">Grid3*3 (|I| = 2, |S| = 81, |A<sup>i</sup>| = 5, |Z<sup>i</sup>| = 9)</td></tr><tr><td>INF-JESP*</td><td>8 × 10</td><td>3</td><td>2</td><td>5.81</td></tr><tr><td>MC-JESP(M-20)</td><td>50 × 50</td><td>5</td><td></td><td>5.81</td></tr><tr><td>FB-HSVI*</td><td></td><td></td><td>67</td><td>5.80</td></tr><tr><td>MC-JESP(M-1<sub>20</sub>)</td><td>50 × 50</td><td>5</td><td>1495</td><td>5.78</td></tr><tr><td>Peri*</td><td></td><td></td><td>9714</td><td>4.64</td></tr><tr><td colspan="5">Box-pushing (|I| = 2, |S| = 100, |A<sup>i</sup>| = 4, |Z<sup>i</sup>| = 5)</td></tr><tr><td>FB-HSVI*</td><td></td><td></td><td>1715</td><td>224.43</td></tr><tr><td>MC-JESP(M-20)</td><td>50 × 50</td><td>4</td><td></td><td>223.26</td></tr><tr><td>INF-JESP*</td><td>250 × 408</td><td>6</td><td>963</td><td>220.25</td></tr><tr><td>MC-JESP(M-1<sub>20</sub>)</td><td>50 × 50</td><td>4</td><td>1245</td><td>220.00</td></tr><tr><td>Peri*</td><td></td><td></td><td>5675</td><td>148.65</td></tr><tr><td>oSARSA</td><td></td><td></td><td></td><td>144.57</td></tr><tr><td>PeriEM*</td><td></td><td></td><td>7164</td><td>106.65</td></tr><tr><td>Dec-SBPR</td><td></td><td></td><td>290</td><td>77.65</td></tr><tr><td colspan="5">Mars Rover (|I| = 2, |S| = 256, |A<sup>i</sup>| = 6, |Z<sup>i</sup>| = 8)</td></tr><tr><td>FB-HSVI*</td><td></td><td></td><td>74</td><td>26.94</td></tr><tr><td>INF-JESP*</td><td>125 × 183</td><td>6</td><td>122</td><td>26.91</td></tr><tr><td>MC-JESP(M-20)</td><td>50 × 50</td><td>4</td><td></td><td>26.78</td></tr><tr><td>MC-JESP(M-1<sub>20</sub>)</td><td>50 × 50</td><td>4</td><td>1543</td><td>25.36</td></tr><tr><td>Peri*</td><td></td><td></td><td>6088</td><td>24.13</td></tr><tr><td>Dec-SBPR</td><td></td><td></td><td>1286</td><td>20.62</td></tr><tr><td>PeriEM*</td><td></td><td></td><td>7132</td><td>18.13</td></tr></tbody></table>
In terms of final value achieved, MC-JESP finds good solutions in most cases, often very close to FB-HSVI's near-optimal solutions, which rely on an explicit Dec-POMDP model. Compared with other explicit model-based algorithms, MC-JESP can achieve even better solutions. On the other hand, compared with other sampling-based methods, MC-JESP shows its dominance in large problems (Grid, Box-pushing, and Mars Rovers), achieving much better solutions, close to FB-HSVI, while other sampling-based methods fail.

However, compared with the explicit model-based algorithms, MC-JESP requires more solving time. For example, in large problems such as Mars Rovers, MC-JESP takes 1543s on average to solve the task, while Inf-JESP takes 122s with M-D initialization. But this is not surprising since MC-JESP only uses a black-box simulator and, with restarts, MC-JESP can give good solutions within an acceptable time.

## A Closer Look at MC-JESP's behavior

We study the MC-JESP's performance with three different bounded FSC sizes (brown for 10, orange for 30, and blue for 50). Figures 4.10 and 4.11 (right parts) present the distribution over final values of MC-JESP with 20 restarts. In the five problems at hand, MC-JESP with max FSC size 50 (blue) has distributions more concentrated on good values than others, and most values are close to FB-HSVI's ones (thus, near-optimal values). These distributions show that few restarts are needed to reach good solutions with high probability if we give large enough FSC sizes for the given problem.

The left parts of Figures 4.10 and 4.11 present the evolution of the values during each iteration of MC-JESP with three different maximum FSC sizes. The average is computed over all runs, even if they have already converged. This figure first shows that MC-JESP monotonically increases during each run, as Inf-JESP, and most runs converge to good local optima in a few iterations. Second, we observe that, for large problems (Box-Pushing and Mars Rovers), there are already significant drops from MC-JESP in the first iteration with an FSC size limit decreasing from 50 to 10. This indicates that, for large problems, we must give large enough FSC size limits, while this is not necessary for small problems.

Last but not least, in Dec-Tiger, although some restarts of MC-JESP end with optimal values, we observe that the average value is still relatively low compared with FB-HSVI. Therefore, we conducted another experiment to investigate the impact of different POMCP timeouts (note that there is a fixed timeout of 5s for the experiments illustrated in Figures 4.10 and 4.11). To that end, we limit the FSC size in each iteration to at most 50 nodes, and we test MC-JESP with five POMCP timeouts (1s, 5s, 10s, 20s, and 30s). The distribution of final values is shown in Figure 4.12. We observe that the average value increases and the variability is shrunk when we give more time to POMCP. However, it also indicates that, when we increase the time budget, we have a lower chance of getting “lucky” good values.

## 4.4 Conclusion and Perspectives

### 4.4.1 Conclusion

**Inf-JESP** We proposed a new infinite-horizon Dec-POMDP solver, Inf-JESP, which is based on JESP, but using FSC representations for policies instead of trees. FSCs allow not only to handle infinite horizons but also to possibly derive compact policies. Any restart of the ideal algorithm provably converges to a Nash equilibrium, and, despite the existence of local optima, experiments show frequent convergence close to global optima in five standard benchmark problems. One
<figure><img src="image_22.png" /><figcaption>Figure 4.10: Values of the joint policy for the Dec-Tiger, Grid and Recycling problems (from top to bottom). The left part of each figure presents the evolution (during a run) of the value of the joint policy at each iteration of MC-JESP($1_{20}$) (avg + 10th and 90th percentiles) with different bounded FSC sizes (10, 30, and 50, respectively). The dashed line represents FB-HSVI's final value. The right part presents the value distribution after convergence of MC-JESP($1_{20}$).</figcaption></figure>
<figure><img src="image_23.png" /><figcaption>Figure 4.11: Values of the joint policy for the Box-Pushing and Mars Rovers problems (from top to bottom). The left part of each figure presents the evolution (during a run) of the value of the joint policy at each iteration of MC-JESP($1_{20}$) (avg + 10th and 90th percentiles) with different bounded FSC sizes (10, 30, and 50, respectively). The dashed line represents FB-HSVI's final value. The right part presents the value distribution after convergence of MC-JESP($1_{20}$).</figcaption></figure>

ingredient, the derivation of a POMDP from $|\mathcal{I}| - 1$ fixed FSCs, could also be useful in other settings where other agents' behaviors are defined independently as games [Oliehoek et al., 2005] or human-robot interactions [Bestick et al., 2017], and serves as an important intermediate step in our contributions to human-robot collaborations (see Chapter 6). Moreover, Inf-JESP provides a theoretic foundation for finding Nash equilibrium solutions using explicit Dec-POMDP models, which is used and extended by MC-JESP for generative models.

We also provided a method to extract individual policies (FSCs) from an MPOMDP solution $\alpha$-vector set $\Gamma$ to initialize Inf-JESP. This approach can be easily adapted to JESP for the finite-horizon setting. Empirical results showed that this initialization method could, in some cases, reach good solutions with a value higher than the average answer of Inf-JESP with random initialization. However, this approach does not always work. In the Recycling problem, it is worse than the average Inf-JESP value with random initializations. How to derive (possibly randomly) better heuristic initializations from MPOMDP policies remains an open question.
<figure><img src="image_24.png" /><figcaption>Figure 4.12: Values of the joint policy for the Dec-Tiger problem. The x-axis indicates the different POMCP timeout used when building the FSC node in the MC-JESP algorithm. The y-axis represents the final value obtained through the MC-JESP method.</figcaption></figure>

**MC-JESP** Based on the approach followed for Inf-JESP, we propose the MC-JESP algorithm, which only requires a generative Dec-POMDP model. We describe how to build the best response generative model (the generative model of the POMDP faced by some agent *i* assuming known FSCs for other agents), and the process to extract an FSC for each agent. Moreover, we also provide a heuristic initialization for MC-JESP, which leads to good solutions confirmed by our experiments. To sum up, MC-JESP has the following properties:

* It does not require an explicit model, a black box simulator being sufficient. Therefore, this method can scale to very large problems where Inf-JESP cannot;

* It has good results similar to Inf-JESP, and even performs better than many explicit model-based methods. To our knowledge, MC-JESP seems to be a very good solution compared with existing sampling-based methods for solving Dec-POMDPs;

* The good performance may be due to the “best-response iteration” itself but is not linked to the completeness of the model (explicit or generative model). This would explain why MC-JESP and Inf-JESP share the same good performance.
4.4.2 Perspectives

For future works, we summarize several directions worth further investigation for Inf-JESP and
MC-JESP.

Influence of different parameters and possible optimizations

First, we could do more experiments with different parameters to analyze our contributions as
follows:

* different FSC size limits: in this thesis, we don't give an explicit FSC size limit for Inf-JESP, and we could develop a strategy that increases the FSC size limit through consecutive restarts;

* different best-response POMDP formalizations: in Section A.1, we also provide other possible formulations to build best-response POMDPs;

* different heuristic initialization methods: our current heuristic initialization method is based on extracting the individual policies from the MPOMDP solution, other heuristic initialization methods should be investigated.

Through experiments, we also demonstrate that parameters greatly influence our algorithms, especially for MC-JESP. Therefore, an improvement could be designing an online parameter optimization process that uses the data gathered through multiple restarts.

Second, both Inf-JESP and MC-JESP have the potential to further speed up with parallel restarts to find the best solution. Moreover, MC-JESP could greatly improve its efficiency by using the previous policy tree computed by the POMCP for the child nodes' computations. In the current setting, each node in an FSC is computed with a new POMCP from scratch.

Last but not least, in MC-JESP, we currently evaluate agents' FSCs in each iteration with a fixed number of simulations. An improvement here is adapting tools from *statistical hypothesis testing* (or developing new ones using *concentration inequalities*) to verify if there is a value increase after each iteration, e.g., to check if $fsc_i$ better or worse than $fsc'_i$ with 0.95 probability, or if the difference is negligible.

Extending MC-JESP to continuous domains

In this thesis, MC-JESP is tested with discrete Dec-POMDP problems. However, as a simulation-
based solver, it can be improved to solve continuous problems (continuous states, actions, and
observations). To do so, we consider to apply *double progressive widening* when building each
agent's FSC, which is already utilized to handle continuous POMDPs [Sunberg and Kochenderfer,
2018].

Evaluating the difficulty of a collaboration problem

There are multiple ways to achieve a given task in many collaboration problems. If we model
such a collaboration problem with a Dec-POMDP, current solvers only give one best joint policy
for all agents. However, if the agents in one team do not follow the same joint policy, a question
is thus raised how to evaluate the difficulty of collaboration for a given Dec-POMDP. One way
to assess the difficulty of collaboration is to look at whether several optimal joint policies exists
and, if so, whether they can be “mixed” successfully or not. For a 2-agent problem, assuming one
can generate *N* FSC pairs $\langle fsc_i^1, fsc_i^2 \rangle_{i=1}^N$ using Inf-JESP of MC-JESP, one could evaluate every