 
# Table of Contents

  1. Title Page
  2. Copyright
  3. Preface
    1. References
  4. Chapter 1: A Brief Review of Supervised Learning
    1. 1.1 Least Squares Estimates
    2. 1.2 Recursive Least Squares
    3. 1.3 Least Mean Squares
    4. 1.4 Stochastic Approximation
    5. References
  5. Chapter 2: Single-Agent Reinforcement Learning
    1. 2.1 Introduction
    2. 2.2  -Armed Bandit Problem
    3. 2.3 The Learning Structure
    4. 2.4 The Value Function
    5. 2.5 The Optimal Value Functions
    6. 2.6 Markov Decision Processes
    7. 2.7 Learning Value Functions
    8. 2.8 Policy Iteration
    9. 2.9 Temporal Difference Learning
    10. 2.10 TD Learning of the State-Action Function
    11. 2.11 Q-Learning
    12. 2.12 Eligibility Traces
    13. References
  6. Chapter 3: Learning in Two-Player Matrix Games
    1. 3.1 Matrix Games
    2. 3.2 Nash Equilibria in Two-Player Matrix Games
    3. 3.3 Linear Programming in Two-Player Zero-Sum Matrix Games
    4. 3.4 The Learning Algorithms
    5. 3.5 Gradient Ascent Algorithm
    6. 3.6 WoLF-IGA Algorithm
    7. 3.7 Policy Hill Climbing (PHC)
    8. 3.8 WoLF-PHC Algorithm
    9. 3.9 Decentralized Learning in Matrix Games
    10. 3.10 Learning Automata
    11. 3.11 Linear Reward–Inaction Algorithm
    12. 3.12 Linear Reward–Penalty Algorithm
    13. 3.13 The Lagging Anchor Algorithm
    14. 3.14   Lagging Anchor Algorithm
    15. References
  7. Chapter 4: Learning in Multiplayer Stochastic Games
    1. 4.1 Introduction
    2. 4.2 Multiplayer Stochastic Games
    3. 4.3 Minimax-Q Algorithm
    4. 4.3 Minimax-Q Algorithm
    5. 4.5 The Simplex Algorithm
    6. 4.6 The Lemke–Howson Algorithm
    7. 4.7 Nash-Q Implementation
    8. 4.8 Friend-or-Foe Q-Learning
    9. 4.9 Infinite Gradient Ascent
    10. 4.10 Policy Hill Climbing
    11. 4.11 WoLF-PHC Algorithm
    12. 4.12 Guarding a Territory Problem in a Grid World
    13. 4.13 Extension of   Lagging Anchor Algorithm to Stochastic Games
    14. 4.14 The Exponential Moving-Average Q-Learning (EMA Q-Learning) Algorithm
    15. 4.15 Simulation and Results Comparing EMA Q-Learning to Other Methods
    16. References
  8. Chapter 5: Differential Games
    1. 5.1 Introduction
    2. 5.2 A Brief Tutorial on Fuzzy Systems
    3. 5.3 Fuzzy Q-Learning
    4. 5.4 Fuzzy Actor–Critic Learning
    5. 5.5 Homicidal Chauffeur Differential Game
    6. 5.6 Fuzzy Controller Structure
    7. 5.7 Q( )-Learning Fuzzy Inference System
    8. 5.9 Learning in the Evader–Pursuer Game with Two Cars
    9. 5.6 Fuzzy Controller Structure
    10. 5.10 Simulation of the Game of Two Cars
    11. 5.11 Differential Game of Guarding a Territory
    12. 5.12 Reward Shaping in the Differential Game of Guarding a Territory
    13. 5.13 Simulation Results
    14. References
  9. Chapter 6: Swarm Intelligence and the Evolution of Personality Traits
    1. 6.1 Introduction
    2. 6.2 The Evolution of Swarm Intelligence
    3. 6.3 Representation of the Environment
    4. 6.4 Swarm-Based Robotics in Terms of Personalities
    5. 6.5 Evolution of Personality Traits
    6. 6.6 Simulation Framework
    7. 6.7 A Zero-Sum Game Example
    8. 6.8 Implementation for Next Sections
    9. 6.9 Robots Leaving a Room
    10. 6.10 Tracking a Target
    11. 6.11 Conclusion
    12. References
  10. Index
  11. End User License Agreement

## Pages

  1. ix
  2. x
  3. xi
  4. 
  5. 
  6. 
  7. 
  8. 
  9. 
  10. 
  11. 
  12. 
  13. 
  14. 
  15. 
  16. 
  17. 
  18. 
  19. 
  20. 
  21. 
  22. 
  23. 
  24. 
  25. 
  26. 
  27. 
  28. 
  29. 
  30. 
  31. 
  32. 
  33. 
  34. 
  35. 
  36. 
  37. 
  38. 
  39. 
  40. 
  41. 
  42. 
  43. 
  44. 
  45. 
  46. 
  47. 
  48. 
  49. 
  50. 
  51. 
  52. 
  53. 
  54. 
  55. 
  56. 
  57. 
  58. 
  59. 
  60. 
  61. 
  62. 
  63. 
  64. 
  65. 
  66. 
  67. 
  68. 
  69. 
  70. 
  71. 
  72. 
  73. 
  74. 
  75. 
  76. 
  77. 
  78. 
  79. 
  80. 
  81. 
  82. 
  83. 
  84. 
  85. 
  86. 
  87. 
  88. 
  89. 
  90. 
  91. 
  92. 
  93. 
  94. 
  95. 
  96. 
  97. 
  98. 
  99. 
  100. 
  101. 
  102. 
  103. 
  104. 
  105. 
  106. 
  107. 
  108. 
  109. 
  110. 
  111. 
  112. 
  113. 
  114. 
  115. 
  116. 
  117. 
  118. 
  119. 
  120. 
  121. 
  122. 
  123. 
  124. 
  125. 
  126. 
  127. 
  128. 
  129. 
  130. 
  131. 
  132. 
  133. 
  134. 
  135. 
  136. 
  137. 
  138. 
  139. 
  140. 
  141. 
  142. 
  143. 
  144. 
  145. 
  146. 
  147. 
  148. 
  149. 
  150. 
  151. 
  152. 
  153. 
  154. 
  155. 
  156. 
  157. 
  158. 
  159. 
  160. 
  161. 
  162. 
  163. 
  164. 
  165. 
  166. 
  167. 
  168. 
  169. 
  170. 
  171. 
  172. 
  173. 
  174. 
  175. 
  176. 
  177. 
  178. 
  179. 
  180. 
  181. 
  182. 
  183. 
  184. 
  185. 
  186. 
  187. 
  188. 
  189. 
  190. 
  191. 
  192. 
  193. 
  194. 
  195. 
  196. 
  197. 
  198. 
  199. 
  200. 
  201. 
  202. 
  203. 
  204. 
  205. 
  206. 
  207. 
  208. 
  209. 
  210. 
  211. 
  212. 
  213. 
  214. 
  215. 
  216. 
  217. 
  218. 
  219. 
  220. 
  221. 
  222. 
  223. 
  224. 
  225. 
  226. 
  227. 
  228. 
  229. 
  230. 
  231. 
  232. 
  233. 
  234. 
  235. 
  236. 
  237. 
  238. 
  239. 
  240. 
  241. 
  242. 
  243. 
  244.

## Guide

  1. Table of Contents

## List of Illustrations

  1. Figure 2-1
  2. Figure 2-2
  3. Figure 2-3
  4. Figure 2-4
  5. Figure 2-5
  6. Figure 2-6
  7. Figure 2-7
  8. Figure 2-8
  9. Figure 3-1
  10. Figure 3-2
  11. Figure 3-3
  12. Figure 3-4
  13. Figure 3-5
  14. Figure 3-6
  15. Figure 3-7
  16. Figure 3-8
  17. Figure 3-9
  18. Figure 3-10
  19. Figure 3-11
  20. Figure 4-1
  21. Figure 4-2
  22. Figure 4-3
  23. Figure 4-4
  24. Figure 4-5
  25. Figure 4-6
  26. Figure 4-7
  27. Figure 4-8
  28. Figure 4-9
  29. Figure 4-10
  30. Figure 4-11
  31. Figure 4-12
  32. Figure 4-13
  33. Figure 4-14
  34. Figure 4-15
  35. Figure 4-16
  36. Figure 4-17
  37. Figure 4-18
  38. Figure 4-19
  39. Figure 4-20
  40. Figure 4-21
  41. Figure 4-22
  42. Figure 4-23
  43. Figure 4-24
  44. Figure 4-25
  45. Figure 4-26
  46. Figure 4-27
  47. Figure 4-28
  48. Figure 4-29
  49. Figure 5-1
  50. Figure 5-2
  51. Figure 5-3
  52. Figure 5-4
  53. Figure 5-5
  54. Figure 5-6
  55. Figure 5-7
  56. Figure 5-8
  57. Figure 5-9
  58. Figure 5-10
  59. Figure 5-11
  60. Figure 5-12
  61. Figure 5-13
  62. Figure 5-14
  63. Figure 5-15
  64. Figure 5-16
  65. Figure 5-17
  66. Figure 5-18
  67. Figure 5-19
  68. Figure 5-20
  69. Figure 5-21
  70. Figure 5-22
  71. Figure 5-23
  72. Figure 5-24
  73. Figure 5-25
  74. Figure 5-26
  75. Figure 5-27
  76. Figure 5-28
  77. Figure 5-29
  78. Figure 5-30
  79. Figure 5-31
  80. Figure 5-32
  81. Figure 5-33
  82. Figure 5-34
  83. Figure 5-35
  84. Figure 5-36
  85. Figure 6-1
  86. Figure 6-2
  87. Figure 6-3
  88. Figure 6-4
  89. Figure 6-5
  90. Figure 6-6
  91. Figure 6-7
  92. Figure 6-8
  93. Figure 6-9
  94. Figure 6-10

## List of Tables

  1. Table 2.1
  2. Table 2.2
  3. Table 3.1
  4. Table 3.2
  5. Table 3.3
  6. Table 4.1
  7. Table 4.2
  8. Table 4.3
  9. Table 4.4
  10. Table 4.5
  11. Table 4.6
  12. Table 4.7
  13. Table 5.1
  14. Table 5.2
  15. Table 5.3
  16. Table 5.4
  17. Table 5.5
  18. Table 5.6
  19. Table 5.7
  20. Table 5.8
  21. Table 5.9
  22. Table 6.1
  23. Table 6.2
  24. Table 6.3
  25. Table 6.4
  26. Table 6.5
  27. Table 6.6
  28. Table 6.7

# Multi-Agent Machine Learning

## A Reinforcement Approach

_Editors_

Howard M. Schwartz

Department of Systems and Computer Engineering

Carleton University

Copyright © 2014 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New Jersey

Published simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, (978) 750-8400, fax (978) 750-4470, or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, (201) 748-6011, fax (201) 748-6008, or online at <http://www.wiley.com/go/permissions>.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at (800) 762-2974, outside the United States at (317) 572-3993 or fax (317) 572-4002.

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

**_Library of Congress Cataloging-in-Publication Data:_**

Schwartz, Howard M., editor.

Multi-agent machine learning : a reinforcement approach / Howard M. Schwartz.

pages cm

Includes bibliographical references and index.

ISBN 978-1-118-36208-2 (hardback)

1. Reinforcement learning. 2. Differential games. 3. Swarm intelligence. 4. Machine learning. I. Title.

Q325.6.S39 2014

519.3–dc23

2014016950

# Preface

For a decade I have taught a course on adaptive control. The course focused on the classical methods of system identification, using such classic texts as Ljung [1, 2]. The course addressed traditional methods of model reference adaptive control and nonlinear adaptive control using Lyapunov techniques. However, the theory had become out of sync with current engineering practice. As such, my own research and the focus of the graduate course changed to include adaptive signal processing, and to incorporate adaptive channel equalization and echo cancellation using the least mean squares (LMS) algorithm. The course name likewise changed, from "Adaptive Control" to "Adaptive and Learning Systems." My research was still focused on system identification and nonlinear adaptive control with application to robotics. However, by the early 2000s, I had started work with teams of robots. It was now possible to use handy robot kits and low-cost microcontroller boards to build several robots that could work together. The graduate course in adaptive and learning systems changed again; the theoretical material on nonlinear adaptive control using Lyapunov techniques was reduced, replaced with ideas from reinforcement learning. A whole new range of applications developed. The teams of robots had to learn to work together and to compete.

Today, the graduate course focuses on system identification using recursive least squares techniques, some model reference adaptive control (still using Lyapunov techniques), adaptive signal processing using the LMS algorithm, and reinforcement learning using Q-learning. The first two chapters of this book present these ideas in an abridged form, but in sufficient detail to demonstrate the connections among the learning algorithms that are available; how they are the same; and how they are different. There are other texts that cover this material in detail [2–4].

The research then began to focus on teams of robots learning to work together. The work examined applications of robots working together for search and rescue applications, securing important infrastructure and border regions. It also began to focus on reinforcement learning and multiagent reinforcement learning. The robots are the learning agents. How do children learn how to play tag? How do we learn to play football, or how do police work together to capture a criminal? What strategies do we use, and how do we formulate these strategies? Why can I play touch football with a new group of people and quickly be able to assess everyone's capabilities and then take a particular strategy in the game?

As our research team began to delve further into the ideas associated with multiagent machine learning and game theory, we discovered that the published literature covered many ideas but was poorly coordinated or focused. Although there are a few survey articles [5], they do not give sufficient details to appreciate the different methods. The purpose of this book is to introduce the reader to a particular form of machine learning. The book focuses on multiagent machine learning, but it is tied together with the central theme of learning algorithms in general. Learning algorithms come in many different forms. However, they tend to have a similar approach. We will present the differences and similarities of these methods.

This book is based on my own work and the work of several doctoral and masters students who have worked under my supervision over the past 10 years. In particular, I would like to thank Prof. Sidney Givigi. Prof. Givigi was instrumental in developing the ideas and algorithms presented in Chapter 6. The doctoral research of Xiaosong (Eric) Lu has also found its way into this book. The work on guarding a territory is largely based on his doctoral dissertation. Other graduate students who helped me in this work include Badr Al Faiya, Mostafa Awheda, Pascal De Beck-Courcelle, and Sameh Desouky. Without the dedicated work of this group of students, this book would not have been possible.

H. M. Schwartz

Ottawa, Canada

September, 2013

## References

  1. [1] L. Ljung, _System Identification: Theory for the User_. Upper Saddle River, NJ: Prentice Hall, 2nd ed., 1999.
  2. [2] L. Ljung and T. Soderstrom, _Theory and Practice of Recursive Identification_. Cambridge, Massachusetts: The MIT Press, 1983.
  3. [3] R. S. Sutton and A. G. Barto, _Reinforcement learning: An Introduction_. Cambridge, Massachusetts: The MIT Press, 1998.
  4. [4] Astrom, K. J. and Wittenmark, B., _Adaptive Control_. Boston, Massachusetts: Addison-Wesley Longman Publishing Co., Inc., 2nd ed., 1994, ISBN = 0201558661.
  5. [5] L. Bu oniu and R. Babuška, and B. D. Schutter, "A comprehensive survey of multiagent reinforcement learning," _IEEE Trans. Syst. Man Cybern. Part C_ , Vol. **38** , no. 2, pp. 156–172, 2008.

# Chapter 1  
A Brief Review of Supervised Learning

There are a number of algorithms that are typically used for system identification, adaptive control, adaptive signal processing, and machine learning. These algorithms all have particular similarities and differences. However, they all need to process some type of experimental data. How we collect the data and process it determines the most suitable algorithm to use. In adaptive control, there is a device referred to as the _self-tuning regulator_. In this case, the algorithm measures the states as outputs, estimates the model parameters, and outputs the control signals. In reinforcement learning, the algorithms process rewards, estimate value functions, and output actions. Although one may refer to the recursive least squares (RLS) algorithm in the self-tuning regulator as a supervised learning algorithm and reinforcement learning as an unsupervised learning algorithm, they are both very similar. In this chapter, we will present a number of well-known baseline supervised learning algorithms.

## 1.1 Least Squares Estimates

The least squares (LS) algorithm is a well-known and robust algorithm for fitting experimental data to a model. The first step is for the user to define a mathematical structure or model that he/she believes will fit the data. The second step is to design an experiment to collect data under suitable conditions. "Suitable conditions" usually means the operating conditions under which the system will typically operate. The next step is to run the estimation algorithm, which can take several forms, and, finally, validate the identified or "learned" model. The LS algorithm is often used to fit the data. Let us look at the case of the classical two-dimensional linear regression fit that we are all familiar with:

**1.1**

In this a simple linear regression model, where the input is the sampled signal   and the output is  . The model structure defined is a straight line. Therefore, we are assuming that the data collected will fit a straight line. This can be written in the form

**1.2**

where   and  . How one chooses   determines the model structure, and this reflects how one believes the data should behave. This is the essence of machine learning, and virtually all university students will at some point learn the basic statistics of linear regression. Behind the computations of the linear regression algorithm is the scalar cost function, given by

**1.3**

The term   is the estimate of the LS parameter  . The goal is for the estimate   to minimize the cost function  . To find the "optimal" value of the parameter estimate  , one takes the partial derivative of the cost function   with respect to   and sets this derivative to zero. Therefore, one gets

**1.4**

Setting  , we get

**1.5**

Solving for  , we get the LS solution

**1.6**

where the inverse,   exists. If the inverse does not exist, then the system is not identifiable. For example, if in the straight line case one only had a single point, then the inverse would not span the two-dimensional space and it would not exist. One needs at least two independent points to draw a straight line. Or, for example, if one had exactly the same point over and over again, then the inverse would not exist. One needs at least two independent points to draw a straight line. The matrix   is referred to as the _information matrix_ and is related to how well one can estimate the parameters. The inverse of the information matrix is the covariance matrix, and it is proportional to the variance of the parameter estimates. Both these matrices are positive definite and symmetric. These are very important properties which are used extensively in analyzing the behavior of the algorithm. In the literature, one will often see the covariance matrix referred to as  . We can write the second equation on the right of Eq. (1.4) in the form

**1.7**

and one can define the prediction errors as

**1.8**

The term within brackets in Eq. (1.7) is known as the _prediction error_ or, as some people will refer to it, the _innovations_. The term   represents the error in predicting the output of the system. In this case, the output term   is the correct answer, which is what we want to estimate. Since we know the correct answer, this is referred to as _supervised learning_. Notice that the value of the prediction error times the data vector is equal to zero. We then say that the prediction errors are orthogonal to the data, or that the data sits in the null space of the prediction errors. In simplistic terms, this means that, if one has chosen a good model structure  , then the prediction errors should appear as white noise. Always plot the prediction errors as a quick check to see how good your predictor is. If the errors appear to be correlated (i.e., not white noise), then you can improve your model and get a better prediction.

One does not typically write the linear regression in the form of Eq. (1.2), but typically will add a white noise term, and then the linear regression takes the form

**1.9**

where   is a white noise term. Equation (1.9) can represent an infinite number of possible model structures. For example, let us assume that we want to learn the dynamics of a second-order linear system or the parameters of a second-order infinite impulse response (IIR) filter. Then we could choose the second-order model structure given by

**1.10**

Then the model structure would be defined in   as

**1.11**

In general, one can write an arbitrary  th-order autoregressive exogenous (ARX) model structure as

**1.12**

and   takes the form

**1.13**

One then collects the data from a suitable experiment (easier said than done!), and then computes the parameters using Eq. (1.6). The vector   can take many different forms; in fact, it can contain nonlinear functions of the data, for example, logarithmic terms or square terms, and it can have different delay terms. To a large degree, one can use ones professional judgment as to what to put into  . One will often write the data in the matrix form, in which case the matrix is defined as

**1.14**

and the output matrix as

**1.15**

Then one can write the LS estimate as

**1.16**

Furthermore, one can write the prediction errors as

**1.17**

We can also write the orthogonality condition as  .

The LS method of parameter identification or machine learning is very well developed and there are many properties associated with the technique. In fact, much of the work in statistical inference is derived from the few equations described in this section. This is the beginning of many scientific investigations including work in the social sciences.

## 1.2 Recursive Least Squares

The LS algorithm has been extended to the RLS algorithm. In this case, the parameter estimate is developed as the machine collects the data in real time. In the previous section, all the data was collected first, and then the parameter estimates were computed on the basis of Eq. (1.6). The RLS algorithm is derived by assuming a solution to the LS algorithm and then adding a single data point. The derivation is shown in Reference [1]. In the RLS implementation, the cost function takes a slightly different form. The cost function in this case is

**1.18**

where  . The term   is known as the _forgetting factor_. This term will place less weight on older data points. As such, the resulting RLS algorithm will be able track changes to the parameters. Once again, taking the partial derivative of   with respect to   and setting the derivative to zero, we get

**1.19**

The forgetting factor should be set as  . If one sets the forgetting factor near 0.95, then old data is forgotten very quickly; the rule of thumb is that the estimate of the parameters   is approximately based on   data points.

The RLS algorithm is as follows:

**1.20**

One implements Eq. (1.20) by initializing the parameter estimation vector   to the users best initial estimate of the parameters, which is often simply zero. The covariance matrix   is typically initialized to a relatively large diagonal matrix, and represents the initial uncertainty in the parameter estimate.

One can implement the RLS algorithm as in Eq. (1.20), but the user should be careful that the covariance matrix   is always positive definite and symmetric. If the   matrix, because of numerical error by repeatedly computing the RLS, ceases to be positive definite and symmetric, then the algorithm will diverge. There are a number of well-developed algorithms to ensure that the   matrix remains positive definite. One can use a square-roots approach whereby the   matrix is factored into its Cholesky factorization or the   factorization. Such methods are described in Reference [1].

Let us examine Eq. (1.20) and notice that the update to the parameter estimate is the previous estimate plus a matrix   times the current prediction error. We will see this structure in almost every algorithm that will be described in machine learning. In this case, we have an actual correct answer, which is the measurement  , and we call such algorithms _supervised learning_.

## 1.3 Least Mean Squares

In the field of signal processing, there are a few commonly used techniques to model or characterize the dynamics of a communications channel and then compensate for the effects of the channel on the signal. These techniques are referred to as _channel equalization_ and _echo cancellation_. There are numerous books on adaptive signal processing and adaptive filtering [2]. Most of these techniques use the least mean squares (LMS) approach to identify the coefficients of a model of the channel. Once again, as in the LS and RLS algorithms, we must choose an appropriate model structure to define the communication channel dynamics. In the field of signal processing, one would typically use what is known as a _finite impulse response_ (FIR) filter as the underlying model structure that describes the system. To maintain consistency with the previous section, one can write the channel dynamics as

**1.21**

where   is the output of the filter, or the communications channel, at time step  ,   are the filter coefficients that we want to estimate or _learn_ , and   is the input signal. Typically, the signal   is the communication signal that we want to recover from the output signal  . We define an error signal

**1.22**

where  . This is the same signal as the prediction error in Eq. (1.8). The LMS algorithm defines the cost function as the expected value of the prediction errors as

**1.23**

We can write the squared error term as

**1.24**

We take the expectation and get

**1.25**

We then define the variance   as the mean squared power, and the cross-correlation vector is defined as  . Then we define the information matrix, which is almost the same matrix as in Section 1.1, as  . If the system statistics are stationary, that is, the statistics do not change, the terms  , and  , are constants and the cost function, as a function of changing  , will have the shape of a bowl. The cost function   can be written as

**1.26**

Once again, as in Eq. (1.4), to find the _optimal_ parameter estimate   to minimize the cost function, we take the partial derivative of the cost function   with respect to  , and determine the value of   that sets the partial derivative to zero. We can take the partial derivative of   as

**1.27**

We then compute the partial derivative for each of the terms on the right-hand side of Eq. (1.27). Taking each term separately, we get

**1.28**

Substituting into Eq. (1.27), we get

**1.29**

Solving for  , we get the solution for the optimal parameter estimate as

**1.30**

Equation (1.30) is the well-known Wiener solution. However, the Wiener solution in Eq. (1.30) requires the computation of the inverse of a large matrix  . Notice the similarity between the Wiener solution and the LS solution in Eq. (1.6). Let us say that we want to estimate the expectations in Eq. (1.25); then we would get the average by computing

**1.31**

Substituting the above values into Eq. (1.30), we get the LS solution given by Eq. (1.6). In essence, the LMS Wiener solution and the LS solution are essentially the same.

In the world of signal processing and in particular adaptive signal processing, the processing speed is very important. Furthermore, the model structure used in adaptive signal processing, especially for communication applications, can have many parameters. It would not be unusual to have   terms in the   vector, which means the term   in Eq. (1.21) would be  . In that case, the   matrix will be  , which would be prohibitively large to take the inverse of in Eq. (1.30). As such, a gradient _steepest descent_ method is normally implemented. This is a very common technique throughout the fields of engineering and is very similar to the well-known Newton–Raphson method of finding the zeros and roots of various functions. The steepest descent method is an iterative method. The idea is to start with an initial guess of the parameter values: often one will simply choose zero for the parameter values. In the lexicon of signal processing, one would refer to the parameters as _tap weights_. Then one iteratively adjusts the parameters such that one moves down the cost function along the gradient. Let us say that the current estimate of the parameter vector is  ; then we compute the next value of the parameter vector as

**1.32**

where   is the gradient and is given by the derivative of the cost function with respect to the parameter estimation vector,   as defined in Eq. (1.29). Then, substituting for   in Eq. (1.32), we get

**1.33**

In recursive form, it is written as

**1.34**

We can also write Eq. (1.34) in the form

**1.35**

where  . One may recognize, from systems theory, that if the eigenvalues of   are less than  , then the recursion in Eq. (1.35) will converge. This places a limit on the step size of the steepest descent method. We will come back to this point in the next section when we look at the stochastic approximation methods. The effect of step size is an important parameter in machine learning algorithms.

The difficulty in computing the recursion in Eq. (1.34) is the computation of the statistical terms   and  , where   is the information matrix or the autocorrelation matrix, and   is the cross-correlation matrix. Their statistics are often unknown and have to be estimated as we did in Eq. (1.31). However, these estimates are computationally intensive and one has to wait until   data points are collected. Instead, the LMS algorithm proposes that one estimate these matrices based on a single data point at each sampling time, as

**1.36**

This is sometimes referred to as the _dirty gradient_ method or the _stochastic gradient_ method. The idea is that one has to descent in the general direction of the gradient and not exactly along the gradient. Think of yourself walking down a hill; you can either go straight down or, if it is really steep, you may choose to go back and forth traversing the hill, much the same way as a skier. Either way, you end up at the bottom of the hill. Now we substitute the estimates for   and   given by Eq. (1.36) into the recursive equation given by Eq. (1.34) and we get

**1.37**

Now we factor out the term   and get the standard LMS recursive algorithm as

**1.38**

Recall that the term in brackets on the right-hand side, given by  , is the prediction error or the innovation. The term   is the current prediction of the output  . If we compare the RLS algorithm in Eq. (1.20) to Eq. (1.38), we see that the update has a similar form. The update to the parameters is the previous estimate plus a matrix vector times the prediction error. In fact, it can be shown that at the stationary point, or the value at which the covarinace matrix update takes the value   in Eq. (1.20), the LMS algorithm is equivalent to the RLS algorithm for a particular set of parameters.

There is a vast literature on various implementations and convergence results associated with the LMS algorithm, but the key element for this book is that the machine learns the parameters of a preconceived model of the system based on the available experimental data and knowledge of the correct answer given by  . The new parameter is the old parameter plus a vector based on the data times the known error in the predicted output.

## 1.4 Stochastic Approximation

The method of stochastic approximation is an older method of system identification. In fact, it is a method of finding the zeros of a function and is very similar to both the RLS and LMS methods, and it is the fundamental structure for the Q-learning algorithms associated with reinforcement learning and much of the machine learning literature. The early work in stochastic approximation comes from the work by Robbins and Monro [3] and Wolfowitz [4]. A good textbook on the topic is by Kushner and Yin [5]. Monro formulated the problem as finding the level at which a continuous function  . Writing the problem in the form   converts it into the problem of finding the zeros of a function. If one knows the gradient of the function, then one can use the well-known Newton–Raphson method to find the zeros, but in this case one takes the noise-corrupted measurements of the function at different values of  . One then makes small corrections to   in the estimated direction of zero.

The method of stochastic approximation and the theoretical proofs of stability are used in the proofs of convergence for several fundamental algorithms in reinforcement learning. Formulating the problem in a similar form to the previous sections, we get the function   and we can write the prediction error and the error in getting to zero as  . The stochastic approximation algorithm is

**1.39**

where   is a variable step size that goes to zero such that

**1.40**

## References

  1. [1] L. Ljung and T. Soderstrom, _Theory and Practice of Recursive Identification_. Cambridge, Massachusetts: The MIT Press, 1983.
  2. [2] B. Farhang-Boroujeny, _Adaptive Filters: Theory and Applications_. New York: John Wiley & Sons, Inc., 1998.
  3. [3] H. Robbins and S. Monro, "A stochastic approximation method," _Annals of Mathematical Statistics_ , vol. **22** , no. 3, pp. 400–407, 1951.
  4. [4] J. Wolfowitz, "On the stochastic approximation method of robbins and monro," _Annals of Mathematical Statistics_ , vol. **23** , no. 3, pp. 457–461, 1952.
  5. [5] H. J. Kushner and G. G. Yin, _Recursive Approximation and Recursive Algorithms and Applications_. New York: Springer-Verlag, 2nd ed., 2003.

# Chapter 2  
Single-Agent Reinforcement Learning

The objective of this chapter is to introduce the reader to reinforcement learning. A good introductory book on the topic is Reference [1] and we will follow their notation. The goal of reinforcement learning is to maximize a reward. The interesting aspect of reinforcement learning, as well as unsupervised learning methods, is the choice of rewards. In this chapter, we will discuss some of the fundamental ideas in reinforcement learning which we will refer to in the rest of the book. We will start with the simple  -armed bandit problem and then present ideas on the meaning of the "value" function.

## 2.1 Introduction

Reinforcement learning is learning to map situations to actions so as to maximize a numerical reward [1]. Without knowing which actions to take, the learner must discover which actions yield the most reward by trying them. Actions may affect not only the immediate reward but also the next situation and all subsequent rewards [1]. Different from supervised learning, which is learning from examples provided by a knowledgeable external supervisor, reinforcement learning is used for learning from interaction [1]. Since it is often impractical to obtain examples of desired behavior that are both correct and representative of all the situations, the learner must be able to learn from its own experience [1]. Therefore, the reinforcement learning problem is a problem of learning from interaction to achieve a goal.

The learner is called the _agent_ or the _player_ and the outside which the agent interacts with is called the _environment_. The agent chooses actions to maximize the rewards presented by the environment. Suppose we have a sequence of discrete time steps  . At each time step  , the agent receives a state   from the environment. We define   as the action the agent takes at time  . At the next time step, as a consequence of its action  , the agent receives a numerical reward   and moves to a new state  , as shown in Fig. 2-1. At each time step, the agent implements a mapping from states to probabilities of selecting each possible action [1]. This mapping is called the _agent's policy_ and is denoted as  , and   is the probability of   at  . Reinforcement learning methods specify how the agent changes its policy as a result of its experience to maximize the total amount of reward it receives over the long run [1].

**Figure 2-1** Agent–environment interaction in reinforcement learning.

Reproduced from [1], with permission of MIT Press.

A reinforcement learning problem can be studied under the framework of stochastic games [2]. Such a framework contains two simpler frameworks: Markov decision processes (MDPs), and matrix games [2]. MDPs involve a single agent and multiple states, while matrix games include multiple agents and a single state. Combining MDPs and matrix games, stochastic games are considered as reinforcement learning problems with multiple agents and multiple states.

## 2.2  -Armed Bandit Problem

The  -armed bandit problem is taken from playing slot machines. The idea is that one is playing a slot machine with   arms. Each arm will give you a different reward, or a different probability of winning or losing. The idea is to determine which of the   arms will give you the greatest reward. Therefore, there are   actions that one can take, each of the actions representing one of the arms that you can pull. The action that gives the greatest reward is referred to as the _greedy_ reward. How would one learn which is the best arm to pull to get the greatest expected reward? You would probably try and pull each arm many times and try to compute a running average of which arm seemed to give you the most reward. We will define the value of each arm as the expected reward for the arm, or action. In this case, pulling a given arm is the same as choosing an action. Let us estimate the value of an action at trial   as

**2.1**

where   is the reward of choosing arm   on the  th time step. However, there were   actions played in total, but only   of those times was the arm or action   played. We will denote the actual value of the arm or action   as  . The rule for choosing which action to take is to always choose the _greedy_ action except for the relatively small probability of   of choosing a random action. The _greedy_ actions are taken based on which action has the highest expected reward at that particular time step. However, sometimes one should explore to find out if some other choice of action would be better. This random selection of some action that is not the _greedy_ one is referred to as _exploration_. Within machine learning, there is a kind of tension between how much _exploration_ there should be and how much _exploitation_ there should be.

Let us take a simple example of the 10-armed bandit. We start by assigning a random reward for each of the 10 arms from a normal random distribution with mean zero and variance 1. We take 10 numbers from the distribution  . These 10 numbers will represent the true value or the expected reward for each of the 10 arms. We get the true reward for each arm as

**2.2**

We know that the best choice of action is action 8, with  . This is the correct answer that we want the machine to learn. We also set the _exploration_ variable to  . This means that there is a 20% chance that on any given choice the machine will randomly choose an action without regard to the estimate of the reward.

We start the learning process by guessing at the expected reward for each arm by choosing our initial guess from the same normal distribution that we chose the true rewards from, and the true rewards are given in Eq. (2.2). We then get our first estimate of the true reward as

**2.3**

Based on the initial estimate, we should choose action 5, which is estimated by Eq. (2.3) as  , but the true value of action 5 is really  , and therefore the initial _greedy_ choice we took is a very poor choice. The machine chooses action 5, and the resulting reward is selected from a random distribution of  , which has a mean of   and a variance of 1. The machine gets the reward  . The machine then updates the   table or vector according to Eq. (2.1) as

**2.4**

The machine then chooses another arm based on its most recent estimate of the rewards given by Eq. (2.4). The machine once again makes the _greedy_ choice and chooses action 9 because  . The machine chooses action  , and the machine gets the reward  . We then get the estimate of   as

**2.5**

We repeat this process and, on trial number  , the machine explores and arbitrarily chooses action  , which we know is not a good choice, because from Eq. (2.2) the true average reward for action   is  . The reward the machine gets for choosing action   on the sixth trial is  . The learning process continues until the 18th trial, when it finally recognizes action   as the best choice. The results of implementing the 10-armed bandit problem for different values of   is illustrated in Fig. 2-2.

**Figure 2-2** Armed bandit with varying  .

## 2.3 The Learning Structure

In this section, we will formulate the basic structure for reinforcement learning. We will take the case of a single agent. The agent, or robot, is in a particular state and in that state it can take one of a number of actions. In some cases, there exists a particular action that is in some sense optimal for that particular state. We will sometimes refer to that action as the _greedy_ action and the set of actions the agent should _optimally_ take in each state is the action _policy_ or the _strategy_. The terms _policy_ and _strategy_ are sometimes used interchangeably and sometimes they may have slightly different meanings: it depends on the context. If in a particular state the agent should choose a particular action, we will refer to that as a _pure strategy_ , whereas if the agent should choose an action with a particular probability, then we refer to that as a _distributed policy_ , or a mixed strategy. For example, if you are playing the rock-paper-scissors game, then the optimal strategy is to take each action with a probability of  , but if you knew in advance that your opponent will always choose Rock, then your _optimal_ strategy or policy is to choose the pure strategy of paper.

We will define the actions as  . The action is a member of an action set for the given state. The possible actions an agent can take depend on the state the agent is in. Furthermore, there is a defined number of possible states. Here we have  . If it is currently time  , our goal will be to maximize future rewards, given by

**2.6**

where   is the terminal time. This type of reward function works well when we have episodic games that have a well-defined terminal time. However, in many cases we do not have a terminal time and the game continues indefinitely, such as a regulator in control applications. In those cases, without well-defined terminal times, one typically uses discounted future rewards. In this case, the reward is defined as

**2.7**

where   is the discount factor given as  . If   is close to zero, then we refer to the algorithm as _myopic_ , but if   is close to 1, then the algorithm is maximizing future rewards.

In reinforcement learning, we want the current state to be a good basis for predicting the future. Such systems are called _MDPs_. A decision system is said to have the Markov property when the current state is all one needs to know to make decisions about what to do next and into the future. What to do in the next step does not depend on what happened in the past, but just the state the system is currently in. For example, a game of checkers depends only on the current state of the game and not how one got to that position. A more engineering example is that the future flight of a ball depends only on its current position and velocity vector; it does not depend on how it got there. In the Markov world, we can define the Markov property as the probability of receiving a particular reward, and changing to another state is completely defined by the current state and action as  ; whereas in the non-Markovian world the same probability would be written as  . We can define the probability of taking action   and transitioning from state   to the next state   as  . Furthermore, we can define the expected reward as  .

## 2.4 The Value Function

The value function, in the framework of reinforcement learning defines _how good_ a particular state is. The measure of how good a given state is, is based on the expected future rewards that will be achieved from that state. The players in the game follow a strategy  , which is the probability of taking action   when in state  . The value of a state   is the expected future return of following policy   starting from  , and can be written as

**2.8**

We also define the action value function for policy or strategy,  :

**2.9**

The term   is a little different from  . The term   is the expected return if we choose action _a_ in state _s_ and then follow policy or strategy   afterwards. We can write the value function as

**2.10**

**2.11**

**2.12**

We can then write this in the form

**2.13**

The first sum on the right-hand side of Eq. (2.13) represents the sum over all the possible actions in state  , where   is the probability of taking a particular action. The second sum in Eq. (2.13) is taken over all the possible next states. Recall that   is the probability of transitioning from state   to state   given one has chosen action  . The last term in brackets on the right represents the immediate reward   plus the future discounted rewards from the next state onwards, given by  . Equation (2.13) is known as the _Bellman equation_ for  . Similarly, we can write the state-action value function as

**2.14**

## 2.5 The Optimal Value Functions

We define the optimal state-value function as

**2.15**

and, similarly, the optimal state-action value function is given as

**2.16**

As such, we are searching for the policy, or the choice of actions that will give the greatest reward. Then   can be written as

**2.17**

Then the optimal value becomes

**2.18**

The term   represents one getting an immediate reward of   for taking action   and then following the optimal policy thereafter. We can write the value function in the following form:

**2.19**

The value function and the state-action function look to the future. They refer to the expected future rewards. Therefore, if we know the maximum future rewards from the next state onwards, then all we have to do is to choose the best action right now. We can write Eq. (2.19) as

**2.20**

Similarly we can write

**2.21**

### 2.5.1 The Grid World Example

We will take an example of a   grid, as shown in Fig. 2-3. The robot or agent can be in one of the nine cells at any starting time. It can then move in one of four directions. The actions then are taken from the set  . When the robot or learning agent moves to cell 1, it then immediately moves to cell 9 and gets a reward of  . If the agent hits a wall, it remains in its current cell and gets a negative reward (punishment) of  . We will use Eq. (2.20) to derive the nine equations and nine unknowns. We will solve Eq. (2.20) with the following parameters: the discount factor for future rewards  , and the action selection strategy is  ; in other words, the agent will arbitrarily choose to go either up, down, left, or right with equal probability. There are four possible actions to transition from a particular state. The only reward is when the agent gets to state 1 and then transitions with 100% probability to state 9 and receives a reward of +10. The rewards are all zero except for   and, when the agent hits the wall,   . The transition probabilities are as follows:

**2.22**

We can now substitute these into Eq. (2.13) to get the nine equations and nine unknowns for each state. Let us specifically write out the first equation for the first state, recalling that  , representing equal probability for the taking of each action and  . Writing out the   equation is a special case because, regardless of which action we take, the we always move to state 9 and receive a reward of  . Therefore, we get

**2.23**

The term

**2.24**

dropping the superscript on   for ease of writing, gives the first equation as

**2.25**

Now we will go through the same process for state 2. In this case, we do not automatically jump to another state but we can move to one of four other states. Recall that hitting a wall will give us a negative reward of  . Then we can write

**2.26**

If we examine the probabilities on the right of Eq. (2.26), we note that they take a value of either 1 or 0. For example, if we look at the term  , it only takes a value for  , and all other state transitions for  . Furthermore, if the agent tries to go up, it hits the wall and gets a reward of  . We can now rewrite equation 2.26 as

Just for some further practice, we will write out the equation for  . In this case, the agent will hit the wall if it moves up or right, and will receive a reward of  . Then we get

We continue going through the process of determining the equations for each state, and we then write out the equations in matrix form as  , where   is given as

and   is given by

Solving for this set of nine equations and nine unknowns, we get the true value of each state as

**2.27**

Recall that the value function for each state is for the future discounted rewards. Therefore, state 1 does not get a value of 10 but a value of 8.85 because we do not know where the agent goes from state 9 onwards. We show the value of each state in the grid in Fig. 2-4.

**Figure 2-3** Example of the grid world.

**Figure 2-4** Values for each of the states.

This is an important result as we delve into machine learning algorithms. In some way, we need to learn the value of the state. Furthermore, even for this relatively simple stochastic game, look at the amount of information we needed to know to solve for the value of the state. We needed to know all the transition probabilities from state to state, based on what action was taken, and in this case it was relatively easy; the transition probabilities were either 1 or 0. We have to know all possible actions in each state, and we need to know the rewards a priori.

The goal of machine learning is to try to automatically learn what would be the best path to take, given any initial state, such that you collect the greatest reward. You and I can look at this game and almost immediately recognize the best path to take, but what if you knew nothing about the game. How would you learn what the best path would be? You would try out some steps until you eventually hit state 1 and collected your big reward. This is what we want the agent to eventually learn how to do.

## 2.6 Markov Decision Processes

An MDP [3] is a tuple  , where   is the state space,   is the action space,   is the transition function,   is the discount factor, and   is the reward function. The transition function denotes a probability distribution over next states given the current state and action such that

**2.28**

where   represents a possible state at the next time step. The reward function denotes the received reward at the next state given the current action and the current state. An MDP has the following Markov property: the player's next state and reward depend only on the player's current state and action. A player's policy   is defined as a probability distribution over the player's actions from a given state. A player's policy   satisfies

**2.29**

For any MDP, there exists a deterministic optimal policy for the player, where   [4]. The goal of a player in an MDP is to maximize the expected long-term reward. In order to evaluate a player's policy, we have the following concept of the state-value function: The value of a state   (or the state-value function) under a policy   is defined as the expected return when the player starts at state   and follows a policy   thereafter. Then the state-value function   becomes

**2.30**

where   is a final time step,   is the current time step,   is the received immediate reward at the time step  , and   is a discount factor. In (2.30), we have   if the task is an infinite-horizon task such that the task will run over an infinite period. If the task is episodic,   is defined as the terminal time when each episode is terminated at the time step  . Then we call the state where each episode ends as the _terminal state_  . In a terminal state, the state-value function is always zero such that    . An optimal policy   will maximize the player's discounted future reward for all states such that

**2.31**

The state-value function under a policy in (2.30) can be rewritten as a recursive equation called the _Bellman equation_ [5] as follows:

**2.32**

where   is the probability of the next state being   given the current state   and action   at time step  , and   is the expected immediate reward received at state   given the current state   and action  . If the player starts at state   and follows the optimal policy   thereafter, we have the optimal state-value function denoted by  . The optimal state-value function   is also called the _Bellman optimality equation_ , where

**2.33**

We can also define the action-value function as the expected return of choosing a particular action   at state   and following a policy   thereafter. The action-value function   is given as

**2.34**

If the player chooses action   at state   and follows the optimal policy   thereafter, the action-value function becomes the optimal action-value function  , where

**2.35**

In a terminal state  , the action-value function is always zero such that      .

## 2.7 Learning Value Functions

In the previous section, we computed the value function for each state by solving nine equations and nine unknowns. Also we saw in the previous section that just writing out the equations can be tedious even for the relatively simple example that we had. In this section, we will present the iterative computer algorithm that will solve the equation for the value functions. This type of approach is known more widely as _dynamic programming_. Given that we already know the transition probabilities, the action strategies, and the rewards, we can compute the value of the state as in Eq. (2.13). Recall that we wrote the equation for the value function in the form  , and we can also write it as  , which is solved for as  , and most of us learned to solve this equation using Gaussian elimination. Let us say we just write an algorithm to find the zero of  . Any dirty type gradient algorithm can work. Most people who have done technical work have done this type of thing. Sometimes they tried to find the argument of a function by trial and error. The idea is to solve Eq. (2.36) iteratively. We will not write out the set of equations, but we will write a machine learning algorithm to find it. Furthermore, we will construct this learning algorithm as a gradient search algorithm to find the zero of a function. In more formal terms, we are

searching for the stationary point of a recursive algorithm, which is similar to stochastic approximation.

The algorithm works as follows: we initialize the value function to zero as  . We then compute Eq. (2.13) and repeating it for convenience as

**2.36**

This gives us the first guess at the value of each state. Recall, we must know  ,   and   in advance. We then compute the difference  . Once this difference becomes small enough, we stop the recursion given by Eq. (2.36). Once we get to  , then the algorithm given by the recursion in (2.36) has reached a stationary point. The value iteration algorithm is given in Algorithm 2.1. We set  , and the algorithm executes 40 iterations before it exits with the result

**2.37**

which is the same result that we got with the exact solution in Eq. (2.27).

## 2.8 Policy Iteration

In the previous section, we presented a recursive algorithm to solve the   equations and   unknown problem to compute the value of each state. However, we used the known state transition matrices  , the known rewards  , and the known action strategies   to do the computations. However, can we determine whether a better strategy would give us a higher reward. If we searched over all the possible strategies, could we find a strategy that would yield a higher reward and what would the resulting value of the states be under that new strategy? In this section, we present the _policy iteration_ algorithm. This algorithm will compute both the value of the state and the _optimal_ action strategy. Recall, we wrote out the state-action value function in Eq. (2.14) as

**2.38**

The goal is to search for the policy that maximizes  , as

**2.39**

The algorithm has two phases. In the first phase, the value of each state is computed as was done in the value iteration algorithm. In the next phase, we compute Eq. (2.39) and search for the maximizing action. If more than one action yields the equivalent maximizing result, then we assign the probability of each action equivalently. For example, if two actions give the same maximizing result, then each action gets a probability of 50%. We implement the _policy iteration_ Algorithm 2.2 on the previous grid game. This time we get

a different strategy and the value function increases substantially. Figure 2-5 illustrates the resulting strategies for each state and the associated probability. For example, state 1 has four directions and equal probability of choosing any action because the next state is always state 9 regardless of the chosen action; whereas in state 2 the optimal action is to always choose with 100% probability to take action _left_ and move to state 1. When in state 5, the _up_ and _left_ actions each have equal probability of 50% (Fig. 2-6). Based on this new strategy, the value of each state can then be computed as

Notice the dramatic improvement in the value of each state in comparison to the values in (2.37). This is because we have now computed the value of the state based on the _optimal_ action strategy.

**Figure 2-5** Resulting optimal policies.

**Figure 2-6** Resulting state values based on the optimal policies.

## 2.9 Temporal Difference Learning

The idea of reinforcement learning is to learn the best policy and actions. In Section 2.7 we iteratively learnt, or more accurately we calculated, the value of the state on the basis of the knowledge of the action strategies  , the state transition probabilities  , and the rewards  . In Section 2.8, we presented the policy iteration algorithm that searched for the _optimal_ policy and we saw how the optimal policy would improve the value of the states. However, in this case we had to know the state transition probabilities   and the rewards  . In this section, we will present a machine learning algorithm that will learn the value of the state based on just observing the rewards from the environment.

Let us return to the original definition of the value of the state as the expected future rewards as we wrote in (2.13):

**2.40**

**2.41**

**2.42**

We can then write this in the form

**2.43**

Notice that we have identified the value of the state with the action strategy  . If we know the transition probabilities and the rewards, then we can solve for the value of the state by either deriving the   equations and   unknowns as we did in Section 2.5.1 or by dynamic programming as we did in Section 2.7. However, in this case we do not have the luxury of knowing the transition probabilities   nor the rewards  . Therefore, we will use another search method that we are familiar with from the least mean square (LMS) approach. Let us begin with an initial estimate of the value function for each state. We will often, in practice, initialize the value function to zero. Let us rewrite Eq. (2.43) in the form

**2.44**

Now we will update our estimate of the value of the state as

**2.45**

This is the same structure that we saw in the case of the LMS algorithm defined in Eq. (1.38). The update is the previous value plus learning rate   (or step size) times the prediction error. The algorithm takes the following form: We apply

this algorithm to the previous grid game. We initialize the action probabilities to be equal in all directions; therefore, as in Section 2.7,  . We set the discount factor  , just as we did in the previous example, and set the learning rate to  . We then run the algorithm for 1,000,000 steps and get the value of the state as

Recall that the true value of the state is

There is a major difference in what we are doing in this section and what we did in the case of value iteration. In the case of value iteration we knew the state transition probabilities   and the rewards  , and we simply implemented an iterative search algorithm for the zero of the function but we did not actually play the game. In this section, the agent has to play the game many times to _learn_ the value of the states. In the value iteration case, it required only 40 iterations to get an excellent estimate of the value function, and in this section we played the game taking   steps and getting the rewards and then estimating the state value function.

## 2.10 TD Learning of the State-Action Function

In this section, we estimate the state-action function  . We will use essentially the same algorithm as in the previous section. However, in this case we use an  -greedy action selection process. Therefore, we do not select an action based solely on the current policy, but we choose the next action based on the highest value in the state-action table. This is similar to the  -armed bandit problem. Then with a small probability   we arbitrarily choose another action; this is the exploration phase. The recursive equation is

**2.46**

We begin the algorithm by initializing the Q-table to random numbers. In our grid game, the Q-table is a   table. In this case, the algorithm will converge to the optimal Q-table as the algorithm will adapt the action policy to the greedy action. We have set   and  . We run this algorithm for one million steps through the grid. Table 2.1 shows the result.

**Table 2.1** Temporal difference Q-table learning result.

State | Up | Down | Right | Left  
---|---|---|---|---  
1 | 22.7 | 22.6 | 22.8 | 22.7  
2 | 17.1 | 16.0 | 16.4 | 20.7  
3 | 15.3 | 14.1 | 15.1 | 18.5  
4 | 20.7 | 16.4 | 16.0 | 17.6  
5 | 18.7 | 14.4 | 14.2 | 18.0  
6 | 16.0 | 12.8 | 13.5 | 16.7  
7 | 18.5 | 15.1 | 14.3 | 15.5  
8 | 15.5 | 13.7 | 12.6 | 16.4  
9 | 14.8 | 11.6 | 11.9 | 13.9

Recall, the value for the _optimal_ action policy is

State 1 has the same value regardless of the action taken because from state 1 the agent always goes to state 9 and receives a reward of +10. In this simulation, state 1 was visited nearly 200,000 times and each action was taken approximately 45,000 times and the estimated value of the state-action function is  . If we look at state 2, we find that action _left_ has the highest value of  ; therefore, in state 2 the best choice would be to go _left_. We can go down the rest of the table and choose the action that has the highest expected value. As such, an agent playing this grid game can look at its current state and then look up in the Q-table to find which action would give it the highest reward and then, if it were a _rational_ agent, it would take the action with the highest reward.

## 2.11 Q-Learning

This is a well-established reinforcement learning method. It was first proposed in Reference [6] and the proof of stability of this algorithm is based on stochastic approximation and presented in Reference [7]. The recursive equation for the Q-table takes the form

**2.47**

This algorithm is very similar to the temporal difference (TD) learning algorithm in the previous section. The key difference is that we now search for a strictly greedy policy, without exploration, when we compute  . We once again begin by initializing the state   arbitrarily and initializing the Q-table   arbitrarily. We choose an action based on an  -greedy action selection policy and then move to the next state   and get a reward. Then, when we compute the prediction error as  , we do not use an  -greedy algorithm, we search for the maximum value in the Q-table. The algorithm can be written as Algorithm 2.5.

**Table 2.2** Temporal difference Q-table learning result.

State | Up | Down | Right | Left  
---|---|---|---|---  
1 | 23.6 | 23.7 | 24.1 | 23.8  
2 | 18.3 | 17.2 | 16.7 | 21.7  
3 | 16.3 | 15.0 | 16.3 | 19.0  
4 | 21.5 | 17.2 | 17.1 | 18.3  
5 | 19.5 | 15.4 | 15.4 | 18.9  
6 | 16.8 | 13.6 | 14.5 | 17.3  
7 | 19.3 | 16.4 | 14.9 | 16.1  
8 | 17.5 | 14.3 | 13.7 | 16.7  
9 | 15.1 | 13.0 | 12.9 | 15.7

Once again, we set   and   and run this algorithm for one million steps through the grid. We get almost exactly the same Q-table as before. We then run the algorithm again, but this time we set the exploration parameter  , where   is the step number. We then get the results illustrated in (Table 2.2). In this case, the algorithm has converged closer to the optimal values.

## 2.12 Eligibility Traces

In the previous sections, in the TD learning of the state-value function or the Q-table we used what is known as a _one-step predictor_. The update equations had the form

**2.48**

where the TD term   is based only on what happened in the last time step. In other words, we only updated the effect of the last step. In the case of eligibility traces, we will look back further in time. For example, if the current reward is good, then let us not only update the current state but also give some of the reward to some of the previous states that led us to this point. This should improve the time of convergence of the algorithm. Recall, we are defining the rewards in terms of discounted future rewards as

**2.49**

A two-step predictor has the form

**2.50**

The eligibility trace keeps track of the last time we visited a particular state. The current reward is then assigned to recently visited states. States that have not been visited for a long time are not given much credit for the current reward.

Let us define the eligibility trace for each state at time   as  . The eligibility trace for each state decays as  , and the eligibility trace for the state just visited is increased by 1. Therefore, we update the eligibility trace as

**2.51**

The one-step prediction error is

**2.52**

The correction for each state becomes

**2.53**

We run the TD( ) described in Algorithm 2.6, and set  ,   and  . We run through the grid for 1,000,000 steps. The estimated value of the value function is then

However, this is almost the same result as we got when we used the traditional TD learning algorithm described in Algorithm 2.3. The promise of using eligibility traces is the increased speed of convergence. Therefore, we run the simulation again and illustrate the convergence of  . As illustrated in Fig. 2-7, the curve representing the eligibility trace does converge faster. Whether the improvement in the convergence rate is worth the extra effort and computational requirements is a users decision. Furthermore, in this particular example, the algorithm is not sensitive to changes in the parameter  .

**Figure 2-7** Comparison of TD learning with and without eligibility traces for  .

The final algorithm in this chapter is the   learning algorithm. In this case we apply the TD( ) corrections to the state-action Q-table. The eligibility functions then become  . Everything else is largely the same as in the previous algorithm. As usual, we will compute the prediction error as

**2.54**

and the eligibility trace becomes

**2.55**

and then the update for   becomes

**2.56**

The algorithm is described in Algorithm 2.7.

Setting   and   and   and  , we get almost the same answer as with the standard  -learning as shown in Table 2.2. Once again, we examine the rate of convergence for the first value in the table, namely Q(1, UP). The graphs of the convergence of the term Q(1, UP) is illustrated in Fig. 2-8. The difference between the convergence rates for the  -learning algorithm and the  -learning algorithm is relatively minor in this particular case. One has to use good judgement to determine whether using the more complex  -learning algorithm is of significant value.

**Figure 2-8** Comparison of Q-learning with and without eligibility traces for Q(1, UP).

## References

  1. [1] R. S. Sutton and A. G. Barto, _Reinforcement Learning: An Introduction_. Cambridge, Massachusetts: The MIT Press, 1998.
  2. [2] M. Bowling and M. Veloso, "Multiagent learning using a variable learning rate," _Artificial Intelligence_ , vol. **136** , no. 2, pp. 215–250, 2002.
  3. [3] R. Bellman, _Dynamic Programming_. Princeton, New Jersey: Princeton University Press, 1957.
  4. [4] D. P. Bertsekas, _Dynamic Programming: Deterministic and Stochastic Models_. Englewood Cliffs, New Jersey: Prentice-Hall, 1987.
  5. [5] R. A. Howard, _Dynamic Programming and Markov Processes_. Cambridge, Massachusetts: MIT Press, 1960.
  6. [6] C. J. C. H. Watkins and P. Dayan, "Q-learning," _Machine Learning_ , vol. **8** , no. 3, pp. 279–292, 1992.
  7. [7] T. Jaakkola, M. Jordan, and S. Singh, "On the convergence of stochasticiterative dynamic programming algorithms," _Neural Computation_ , vol. **6** , no. 6, pp. 1185–1201, 1994.

# Chapter 3  
Learning in Two-Player Matrix Games

## 3.1 Matrix Games

In this chapter, we will examine the two-player stage game or the matrix game problem. Now, we have two players each learning how to play the game. In some cases they may be competing with each other, or they may be cooperating with other. In this section, we will introduce the class of game that we will investigate in this chapter. In fact, almost every child has played some version of these games. We will focus on three different games: matching pennies, rock-paper-scissors, and prisoners' dilemma. These are all called _matrix games_ or _stage games_ because there is no state transition involved. We will limit how far we delve into game theory and focus on the learning algorithms associated with these games. The idea is for the agents to play these games repetitively and learn their best strategy. In some cases one gets a pure strategy; in other words the agent will choose the same particular action all the time, and in some cases it is best to pick an action with a particular probability, which is known as a _mixed strategy_.

In the prisoners' dilemma game, two prisoners who committed a crime together are being interrogated by the police. Each prisoner has two choices; one choice is to cooperate with the police and defect on his accomplice, and the other is to cooperate with his accomplice and lie to the police. If both of them cooperate with each other and do not confess to the crime, then they will get just a few months in jail. If they both defect and cooperate with the police, then they will get a longer time in jail. However, if one of them defects and cooperates with the police and the other one cooperates with his accomplice and lies to the police, then the one who lied to the police and tried to cooperate with the accomplice will go to jail for a very long time. In Table 3.1, the payoff matrix for the game is shown. This matrix stipulates the rewards for player 1. In the matrix, the entries represent the rewards to the row player, and the first row represents cooperation with the accomplice and the second row represents defection and confession to the police. If the prisoners cooperate with each other and both of them pick the first row and column, then they only go to jail for a short time, a few months, and they get a good reward of 5. However, if row player defects and tells the truth to the police and the column player lies to the police and cooperates with his accomplice, the row player gets a big reward of 10 and goes free, whereas the column player would get a reward of 0 and be sent to jail for life. If they both defect and tell the truth to the police, then they each get a small reward of 1 and go to jail for a couple of years. If this was you, would you trust your criminal accomplice to cooperate with you because if he defects to the police and you lie to the police then you will go to jail for a very long time? Most rational people will confess to the police and limit the time that they may spend in jail. The choice of action to defect is known as the _Nash equilibrium_ (NE). If a machine learning agent were to play this game repetitively, it should learn to play the action of _Defect_ all the time, with 100% probability. This is known as a _pure_ strategy game. A _pure_ strategy means that one picks the same action all the time.

**Table 3.1** Examples of two-player matrix games.

---

The next game we will define is the matching pennies game. In this game two children each hold a penny. They then independently choose to show either heads or tails. If they show two tails or two heads, then player 1 will win a reward of 1 and player 2 loses and gets a reward of  . If they both show different sides of the coin, then player 2 wins. On any given play, one will win and one will lose. This is known as a _zero-sum matrix_ game. When we say that it is a zero-sum game, we mean that one wins the same amount as the other loses. This game's _optimal_ solution, or its NE, is the mixed strategy of choosing heads 50% of the time and choosing tails also 50% of the time. If player 2 always played heads, then quickly player 1 would realize that player 2 always plays heads and player 1 would also start to always play heads and would begin to win all the time. If player 2 always played heads, then we would say that player 2 was an irrational player. So clearly, each one of them should play either heads or tails 50% of the time to maximize their reward. This is known as a _mixed strategy_ game; whereas in the prisoner's dilemma game the optimal strategy was always to defect 100% of the time and as such we refer to that as a _pure_ strategy.

The next game of interest to us is the game of rock-paper-scissors. This game is well known to most children. The idea is to display your hand as either a rock (clenched fist), scissors, or as a flat piece of paper. Then, paper _covers_ (beats) rock, rock _breaks_ (beats) scissors, and scissors _cuts_ (beats) paper. If both players display the same entity, then it is a tie. This game is a mixed strategy zero-sum game. The obvious solution is to randomly play each action, rock, paper, or scissors with a 33.3% probability. The only difference to this game is that we now have three actions instead of two.

More formally, a matrix game (strategic game) [1, 2] can be described as a tuple  , where   is the agents' number,   is the discrete space of agent  's available actions, and   is the payoff function that agent   receives. In matrix games, the objective of agents is to find pure or mixed strategies that maximize their payoffs. A pure strategy is the strategy that chooses actions deterministically, whereas a mixed strategy is the strategy that chooses actions based on a probability distribution over the agent's available actions. The NE in the rock-paper-scissors game and the matching pennies game are mixed strategies that execute actions with equal probability [3].

The player  's reward function   is determined by all players' joint action from joint action space  . In a matrix game, each player tries to maximize its own reward based on the player's strategy. A player's strategy in a matrix game is a probability distribution over the player's action set. To evaluate a player's strategy, we introduce the following concept of NE:

* * *

### Definition 3.1

A Nash equilibrium in a matrix game is a collection of all players' strategies   such that

**3.1**

**3.2**

where   is player  's value function which is player  's expected reward given all players' strategies, and   is any strategy of player   from the strategy space  .

* * *

In other words, an NE is a collection of strategies for all players such that no player can do better by changing its own strategy given that other players continue playing their NE strategies [4]. We define   as the received reward of player   given players' joint action  , and     as the probability of player   choosing action  . Then the NE defined in (3.1) becomes

**3.3**

where   is the probability of player   choosing action   under the player  's NE strategy  .

We provide the following definitions regarding matrix games:

* * *

### Definition 3.2

A Nash equilibrium is called a **strict** Nash equilibrium if (3.1) is strict [5].

* * *

* * *

### Definition 3.3

If the probability of any action from the action set is greater than 0, then the player's strategy is called a **fully mixed strategy**.

* * *

* * *

### Definition 3.4

If the player selects one action with probability 1 and other actions with probability 0, then the player's strategy is called a **pure strategy**.

* * *

* * *

### Definition 3.5

A Nash equilibrium is called a **strict Nash equilibrium in pure strategies** if each player's equilibrium action is better than all its other actions, given the other players' actions [6].

* * *

## 3.2 Nash Equilibria in Two-Player Matrix Games

For a two-player matrix game, we can set up a matrix with each element containing a reward for each joint action pair. Then the reward function   for player   becomes a matrix.

A two-player matrix game is called a _zero-sum game_ if the two players are fully competitive. In this way, we have  . A zero-sum game has a unique NE in the sense of the expected reward. This means that, although each player may have multiple NE strategies in a zero-sum game, the value of the expected reward   under these NE strategies will be the same. A _general-sum matrix game_ refers to all types of matrix games. In a general-sum matrix game, the NE is no longer unique and the game might have multiple NEs.

For a two-player matrix game, we define   as the set of all probability distributions over player  's action set  . Then   becomes

**3.4**

An NE for a two-player matrix game is the strategy pair   for two players such that, for  ,

**3.5**

where   denotes any other player than player  , and   is the set of all probability distributions over player  's action set  .

Given that each player has two actions in the game, we can define a two-player two-action general-sum game as

**3.6**

where   and   denote the reward to the row player (player 1) and the reward to the column player (player 2), respectively. The row player chooses action   and the column player chooses action  . Based on Definition 3.2 and (3.5), the pure strategies   and   are called a _strict NE in pure strategies_ if

**3.7**

where   and   denote any row other than row   and any column other than column  , respectively.

## 3.3 Linear Programming in Two-Player Zero-Sum Matrix Games

One of the issues that arise in some of the machine learning algorithms is to solve for the NE. This is easier said than done. In this section, we will demonstrate how to compute the NE in competitive zero-sum games. In some of the algorithms to follow, a step in the algorithm will be to solve for the NE using linear programming or quadratic programming. To do this, we will be required to set up a constrained minimization/maximization problem that will be solved with the simplex method. The simplex method is well known in the linear programming community.

Finding the NE in a two-player zero-sum matrix game is equal to finding the minimax solution for the following equation [7]:

**3.8**

where   denotes the probability distribution over player  's action  , and   denotes any action from another player other than player  . According to (3.8), each player tries to maximize the reward in the worst case scenario against its opponent. To find the solution for (3.8), one can use linear programming.

Assume we have a   zero-sum matrix game given as

**3.9**

where   is player 1's reward matrix and   is player 2's reward matrix. We define     as the probability distribution over player  's  th action and   as the probability distribution over player  's  th action.

Then the linear program for player 1 is

subject to

**3.10**

**3.11**

**3.12**

**3.13**

The linear program for player 2 is

subject to

**3.14**

**3.15**

**3.16**

**3.17**

To solve the above linear programming problem, one can use the simplex method to find the optimal points geometrically. We provide three   zero-sum games below.

* * *

### Example 3.1

We take the matching pennies game, for example. The reward matrix for player 1 is

**3.18**

Since  , the linear program for player   becomes

subject to

**3.19**

**3.20**

**3.21**

We use the simplex method to find the solution geometrically. Figure 3-1 shows the plot of   over   where the gray area satisfies the constraints (3.19)–(3.21). From the plot, the maximum value of   within the gray area is   when  . Therefore,   is the Nash equilibrium strategy for player  . Similarly, we can use the simplex method to find the Nash equilibrium strategy for player  . After solving (3.14)–(3.17), we can find that the maximum value of   is   when  . Then this game has a Nash equilibrium  , which is a fully mixed strategy Nash equilibrium.

* * *

**Figure 3-1** Simplex method for player 1 in the matching pennies game.

Reproduced from [8], © X. Lu.

* * *

### Example 3.2

We change the reward   from   in (3.18) to   and call this game as the revised version of the matching pennies game. The reward matrix for player 1 becomes

**3.22**

The linear program for player   is

subject to

**3.23**

**3.24**

**3.25**

From the plot in Fig. 3-2, we can find that the maximum value of   in the gray area is   when  . Similarly, we can find the maximum value of

  when  . Therefore, this game has a Nash equilibrium  , which is a pure strategy Nash equilibrium.

* * *

* * *

### Example 3.3

We now consider the following zero-sum matrix game:

**3.26**

where  . Based on different values of  , we want to find the Nash equilibrium strategies  . The linear program for each player becomes

subject to

**3.27**

**3.28**

**3.29**

subject to

**3.30**

**3.31**

**3.32**

We use the simplex method to find the Nash equilibria for the players with a varying  . When  , we find that the Nash equilibrium is in pure strategies  . When  , we find that the Nash equilibrium is in fully mixed strategies  . For  , we plot the players' strategies over their value functions in Fig. 3-3. From the plot we find that player 1's Nash equilibrium strategy is  , and player 2's Nash equilibrium strategy is  , which is a set of strategies. Therefore, at  , we have multiple Nash equilibria which are   We also plot the Nash equilibria ( ,  ) over   in Fig. 3-4.

* * *

**Figure 3-2** Simplex method for player 1 in the revised matching pennies game.

Reproduced from [8], © X. Lu.

**Figure 3-3** Simplex method at   in Example 3.3. (a) Simplex method for player 1 at  . (b) Simplex method for player 2 at  .

Reproduced from [8], © X. Lu.

**Figure 3-4** Players' NE strategies versus  .

Reproduced from [8], © X. Lu.

## 3.4 The Learning Algorithms

In this section, we will present several algorithms that have gained popularity within the field of machine learning. We will focus on the algorithms that have been used for learning how to choose the _optimal_ actions when agents are playing matrix games. Once again, these algorithms will look like gradient descent (ascent) algorithms. We will discuss their strengths and weaknesses. In particular, we are going to look at the gradient ascent (GA) algorithm and its related version the infinitesimal gradient ascent (IGA) algorithm and the policy hill climbing (PHC) algorithm and the variable learning rate version called the _win or learn fast-policy hill climbing_ (WoLF-PHC) algorithm [3]. We will then examine the linear reward-inaction ( ) and the lagging anchor algorithm. Finally, we will discuss the advantages of the   lagging anchor algorithm. There are a number of versions of these algorithms in the literature, but they tend to be minor variations of the ones being discussed here. Of course, one could argue that all learning algorithms are minor variations of the stochastic approximation technique.

## 3.5 Gradient Ascent Algorithm

One of the fundamental algorithms associated with learning in matrix games is the GA algorithm and its related formulation called the _IGA_ algorithm. This algorithm is used in relatively simple two-action/two-player general-sum games. Theoretically, this algorithm will fail to converge. It can be shown that by introducing a variable learning rate that tends to zero as  , the GA algorithm will converge.

We will examine the GA algorithm presented by Singh et al. [9]. We examine the case of a   matrix game as two payoff matrices, one for the row player and one for the column player. The matrices are

**3.33**

and

**3.34**

Then, if the row player chooses action 1 and the column player chooses action 2, then the reward to player 1 (the row player) is   and the reward to player 2 (the column player) is  . This is a two-action two-player game and we are assuming the existence of a mixed strategy, although the algorithm can be used for pure strategy games as well. In a mixed strategy game, the probability that the row player chooses action 1 is   and, therefore, the probability that the row player chooses action 2 must be given by  . Similarly, for player 2 (the column player), the probability that player 2 chooses action 1 is given by   and, therefore, the probability of choosing action 2 is  . The strategy of the matrix game is completely defined by the joint strategy  , where   and   are constrained to remain within the unit square. We define the expected payoff to each player as   and  . We can write the expected payoffs as

**3.35**

**3.36**

**3.37**

**3.38**

**3.39**

**3.40**

where

**3.41**

**3.42**

We can now compute the gradient of the payoff function with respect to the strategy as

**3.43**

**3.44**

The GA algorithm then becomes

**3.45**

**3.46**

* * *

### Theorem 3.1

If both players follow infinitesmal gradient ascent (IGA), where  , then their strategies will converge to a Nash equilibrium, or the average payoffs over time will converge in the limit to the expected payoffs of a Nash equilibrium.

* * *

The first algorithm we will try is the GA algorithm. We will play the mixed strategy games of matching pennies. To implement the GA learning algorithm for the matching pennies game, one needs to know the payoff matrix in advance. One can see from Fig. 3-5 that the strategy oscillates between 0 and 1. If we try to implement the IGA algorithm, one runs into the difficulty of trying to choose an appropriate rate of convergence of the step size to zero. This is not a practical algorithm to use. Therefore, the GA algorithm does not work particularly well; it oscillates and one can show this theoretically [3].

**Figure 3-5** GA in matching pennies game.

## 3.6 WoLF-IGA Algorithm

The WoLF-IGA algorithm was introduced by Bowling and Veloso [3] for two-player two-action matrix games. As a GA learning algorithm, the WoLF-IGA algorithm allows the player to update its strategy based on the current gradient and a variable learning rate. The value of the learning rate is smaller when the player is winning, and it is larger when the player is losing. The term   is the probability of player 1 choosing the first action. Then,   is the probability of player 1 choosing the second action. Accordingly,   is the probability of player 2 choosing the first action and   is the probability of player 2 choosing the second action. The updating rules of the WoLF-IGA algorithm are as follows:

**3.47**

**3.48**

where   is the step size,   is the learning rate for player  ,   is the expected reward of player   at time   given the current two players' strategy pair  , and   are equilibrium strategies for the players. In a two-player two-action matrix game, if each player uses the WoLF-IGA algorithm with  , the players' strategies converge to an NE as the step size   [3].

This algorithm is a GA learning algorithm that can guarantee the convergence to an NE in fully mixed or pure strategies for two-player two-action general-sum matrix games. However, this algorithm is not a decentralized learning algorithm. It requires the knowledge of   and   in order to choose the learning parameters   and   accordingly. In order to obtain   and  , we need to know each player's reward matrix and its opponent's strategy at time  ; whereas in a decentralized learning algorithm, the agents would only have their own actions and reward at time  . Although a practical decentralized learning algorithm called a _WoLF-PHC method_ was provided in Reference [3], there is no proof of convergence to NE strategies.

## 3.7 Policy Hill Climbing (PHC)

A more practical version of the gradient descent algorithm is the PHC algorithm. This algorithm is based on the Q-learning algorithm that we presented in Chapter 2. This is a rational algorithm that can estimate mixed strategies. The algorithm will converge to the _optimal_ mixed strategies if the other players are not learning and are therefore playing _stationary_ strategies.

The PHC algorithm is a simple practical algorithm that can learn mixed strategies. Hill climbing is performed by the PHC algorithm in the space of the mixed strategies. This algorithm was first proposed by Bowling and Veloso [3]. The PHC does not require much information as neither the recent actions executed by the agent nor the current strategy of its opponent is required to be known. The probability that the agent selects the highest valued actions is increased by a small learning rate     (0,1]. The algorithm is equivalent to the single-agent Q-learning when   = 1 as the policy moves to the greedy policy with probability 1. The PHC algorithm is rational and converges to the optimal solution when a fixed (stationary) strategy is followed by the other players. However, the PHC algorithm may not converge to a stationary policy if the other players are learning [3].

The convergence proof is the same as for Q-learning [10], which guarantees that the   values will converge to the optimal   with a suitable exploration policy [9]. However, when both players are learning, then the algorithm will not necessarily converge. The algorithm starts from the Q-learning algorithm and is given as

**3.49**

**3.50**

where

where

The algorithm is given as,

We will now run a simulation of the matching pennies games. To generate the simulation results illustrated in Fig. 3-6, we set the learning rate  , the exploration rate to  , and  . We initialize the probability of player 1 choosing action 1, at 80%. One can see that the algorithm will oscillate about the NE as expected by the theory. In this case, both players are learning. For any practical application, this is a poor result. Furthermore, it takes many iterations to converge about the 50% equilibrium point. Another issue with implementing this algorithm is choosing all the parameters. In a more complex game, this algorithm would not be practical to implement.

**Figure 3-6** PHC matching pennies game, player 1, probability of choosing action 1, heads.

In the next case, we set the column player to always play heads, action 1, and we start the row player at 20% heads and 80% tails. Then the row player should learn to always play heads 100% of the time. As illustrated in Fig. 3-7, the probability of player 1 choosing heads increases and converges to a probability of 100%.

**Figure 3-7** PHC matching pennies game, player 1, probability of choosing action 1, heads when player 2 always chooses heads.

## 3.8 WoLF-PHC Algorithm

In Reference [3], the authors propose to use a variable learning rule as

**3.51**

**3.52**

where the term l is a variable learning rate given by  .

The method for adjusting the learning rate   is referred to as the _WoLF_ approach. The idea is when one is winning the game to adjust the learning rate to learn slowly and be cautious, and when losing or doing poorly to learn quickly. The next step is to determine when the agent is doing well or doing poorly in playing the game. The conceptual idea is for the agent to choose an NE and compare the expected reward it would receive to the NE. If the reward it would receive is greater than the NE, then it is winning and will learn slowly and cautiously. Otherwise, it is losing and it should learn fast; the agent does want to be losing.

The two players each select an NE of their choice independently; they do not need to choose the same equilibrium point. If there are multiple NE points in the game, then the agents could pick different points; that is perfectly acceptable because each NE point will have the same value. Therefore, player 1 may choose NE point   and player 2 may choose NE point  , and the learning rates are chosen as

When we combine the variable learning rate with the IGA algorithm, we refer to it as the _WoLF-IGA algorithm_. Although this is not a practical algorithm to implement, it does have good theoretical properties as defined by the following theorem.

* * *

### Theorem 3.2

If in a two-action iterated general-sum game both players follow the WoLF-IGA algorithm (with  ), then their strategies will converge to a Nash Equilibrium.

* * *

It is interesting to note that winning is defined as the expected reward of the current strategy being greater than the expected reward of the current player's NE strategy and the other player's current strategy.

The difficulty with the WoLF-IGA algorithm is the amount of information that the player must have. The player needs to know its own payoff matrix, the other player's strategy, and its own NE. Of course, if one knows its own payoff matrix, then it will also know its NE point or points. That is a lot of information for the player to know, and as such this is not a practical algorithm to implement.

The WoLF-PHC algorithm is an extension of the PHC algorithm [3]. This algorithm uses the mechanism of win-or-learn-fast (WoLF) so that the PHC algorithm converges to an NE in self-play. The algorithm has two different learning rates,   when the algorithm is winning and   when it is losing. The difference between the average strategy and the current strategy is used as a criterion to decide when the algorithm wins or loses. The learning rate   is larger than the learning rate  . As such, when a player is losing, it learns faster than when winning. This causes the player to adapt quickly to the changes in the strategies of the other player when it is doing more poorly than expected and learns cautiously when it is doing better than expected. This also gives the other player the time to adapt to the player's strategy changes. The WoLF-PHC algorithm exhibits the property of convergence as it makes the player converge to one of its NEs. This algorithm is also a rational learning algorithm because it makes the player converge to its optimal strategy when its opponent plays a stationary strategy. These properties permit the WoLF-PHC algorithm to be widely applied to a variety of stochastic games [3, 11–13]. The recursive Q-learning of a learning agent   is given as

**3.53**

The WoLF-PHC algorithm updates the strategy of the agent   by equation 3.32, whereas Algorithm 2.1 describes the complete formal definition of the WoLF-PHC algorithm for a learning agent  :

**3.54**

where

We simulate the WoLF-PHC algorithm for the matching pennies game. We set the learning parameter   and   and  . The strategy for player 1 is initially set to   and the strategy for player 2 to  . The results are shown in Fig. 3-8.

**Figure 3-8** WoLF-PHC matching pennies game, player 1, probability of choosing action 1.

## 3.9 Decentralized Learning in Matrix Games

Decentralized learning means that there is no central learning strategy for all of the agents. Instead, each agent learns its own strategy. Decentralized learning algorithms can be used by players to learn their NEs in games with incomplete information [14, 15]. When an agent has "incomplete information," it means that the agent knows neither its own reward function, nor the other players' strategies, nor the other players' reward functions. The agent only knows its own action and the received reward at each time step. The main challenge for designing a decentralized learning algorithm with incomplete information is to prove that the players' strategies converge to an NE.

There are a number of multiagent learning algorithms proposed in the literature that can be used for two-player matrix games. Lakshmivarahan and Narendra [14] presented a linear reward–inaction approach that can guarantee the convergence to a NE under the assumption that the game only has strict NEs in pure strategies. The linear reward–penalty approach, introduced in Reference [15], can guarantee that the expected value of players' strategies converges to an NE in fully mixed strategies with the proper choice of parameters. Bowling and Veloso proposed a WoLF-IGA approach that can guarantee the convergence to an NE for two-player two-action matrix games and the NE can be in fully mixed strategies or in pure strategies. However, the WoLF-IGA approach is not a completely decentralized learning algorithm because the player has to know its opponent's strategy at each time step. Dahl [16, 17] proposed a lagging anchor model approach that can guarantee the convergence to an NE in fully mixed strategies. But the lagging anchor algorithm is not a decentralized learning algorithm because each player has to know its reward matrix.

We evaluate the learning automata algorithm   [14] and   [15], the GA algorithm WoLF-IGA [3], and the lagging anchor algorithm [16]. We then propose the new   lagging anchor algorithm. The   lagging anchor algorithm is a combination of learning automata and GA learning. It is a completely decentralized algorithm and, therefore, each agent only needs to know its own action and its own reward at each time step. We prove the convergence of the   lagging anchor algorithm to NEs in two-player two-action general-sum matrix games. Furthermore, the NE can be in games with pure or fully mixed strategies. We then simulate three matrix games to test the performance of the   lagging anchor learning algorithm.

We first review the multiagent learning algorithms in matrix games based on the learning automata scheme and the GA schemes. In Section 3.14, we introduce the new   lagging anchor algorithm and provide the proof of convergence to NEs in two-player two-action general-sum matrix games. Simulationsof three matrix games are also illustrated in Section 3.14 to show the convergence of our proposed   lagging anchor algorithm.

## 3.10 Learning Automata

Learning in a two-player matrix game can be expressed as the process of each player updating its strategy according to the received reward from the environment. A learning scheme is used for each player to update its own strategy toward a NE based on the information from the environment. In order to address the limitations of the previously published multiagent learning algorithms for matrix games, we divide these learning algorithms into two groups. One group is based on learning automata [18], and another group is based on GA learning [9].

Learning automation is a learning unit for adaptive decision making in an unknown environment [18]. The objective of learning automation is to learn the optimal action or strategy by updating its action probability distribution based on the environment response. The learning automata approach is a completely decentralized learning algorithm because each learner only considers its action and the received reward from the environment and ignores any information from other agents such as the actions taken by other agents. The learning automation can be represented as a tuple  , where   is the player's action set,   is the reinforcement signal,   is the probability distribution over the actions, and   is the learning algorithm to update  . There are two typical learning algorithms based on learning automata: the linear reward–inaction ( ) algorithm and the linear reward–penalty ( ) algorithm.

## 3.11 Linear Reward–Inaction Algorithm

The linear reward–inaction ( ) algorithm for player   is defined as follows:

**3.55**

where   is the time step, the superscripts and subscripts on   denote different players and each player's different action, respectively,   is the learning parameter,   is the response of the environment given player  's action   at  , and   is the probability distribution over player  's action  .

In a matrix game with   players, if each player uses the   algorithm, then the   algorithm guarantees the convergence to a NE under the assumption that the game only has strict NEs in pure strategies [14].

## 3.12 Linear Reward–Penalty Algorithm

The linear reward–penalty ( ) algorithm for player   is defined as follows:

**3.56**

where   is the current action the player   has taken,   are learning parameters, and   is the number of actions in the player's action set.

In a two-player zero-sum matrix game, if each player uses the   and chooses  , then the expected value of the fully mixed strategies for both players can be made arbitrarily close to an NE [15]. This means that the   algorithm can guarantee the convergence to an NE in the sense of expected value but not the player's strategy itself.

## 3.13 The Lagging Anchor Algorithm

The lagging anchor algorithm for two-player zero-sum games was introduced by Dahl [16]. As a GA learning method, the lagging anchor algorithm updates the players' strategies according to the gradient. We denote player 1's strategy as a vector  , which is the probability distribution over all the possible actions. Accordingly, player 2's strategy is denoted as a vector  . The updating rules are listed as follows:

**3.57**

where   is the step size,   is the anchor drawing factor, and   is a matrix used to maintain the summation of the elements in the vector   or   to be  .   is a unit vector corresponding to the actions of player 2. If the  th action in player 2's action set is selected at time  , then the  th element in   is set to   and the other elements in   are zeros. Similarly,   is the unit vector corresponding to the actions of player 1, and   and   are the reward matrices for player   and  , respectively. In (3.57),   and   are the anchor parameters for   and  , respectively, which can be represented as the weighted average of the players' strategies. In a two-player zero-sum game with only NEs in fully mixed strategies, if each player uses the lagging anchor algorithm, then the players' strategies converge to an NE as the step size   [17].

This algorithm guarantees the convergence to an NE in fully mixed strategies. However, the convergence to an NE in pure strategies has never been discussed. Furthermore, the lagging anchor algorithm in (3.57) requires full information of the player's reward matrices   and  . Therefore, the lagging anchor algorithm is not a decentralized learning algorithm.

Table 3.2 compares these algorithms based on the allowable number of actions for each player, the convergence to pure strategies or fully mixed strategies, and the level of decentralization. From this table, only the WoLF-IGA algorithm can guarantee the convergence to both pure and mixed-strategy NE. But it is not a decentralized learning algorithm. Although the   algorithm and the   algorithm are decentralized learning algorithms, neither of them can guarantee the convergence to both pure and mixed-strategy NE. The   lagging anchor algorithm presented in the next section can guarantee convergence of both pure and mixed strategies to the NE as shown in Table 3.2.

**Table 3.2** Comparison of learning algorithms in matrix games.

| Existing algorithms | Our proposed Algorithm  
---|---|---  
|  |  |  | Lagging |    
Applicability |   |   | WoLF-IGA | anchor | lagging anchor  
Allowable | No limit | Two actions | Two actions | No limit | Two actions  
actions |  |  |  |  |   
Convergence | Pure | Fully mixed NE | Both | Fully mixed | Both  
| NE | (expected value) |  | NE |   
Decentralized? | Yes | Yes | No | No | Yes

## 3.14   Lagging Anchor Algorithm

In this section, we design an   lagging anchor algorithm which is a completely decentralized learning algorithm and can guarantee the convergence to NEs in both pure and fully mixed strategies. We take the   algorithm defined in (3.55) as the updating law of the player's strategy and add the lagging anchor term in (3.57). Then the   lagging anchor algorithm for player   is defined as follows:

**3.58**

where   is the step size and ( ) are the lagging parameters for ( ). The idea behind the   lagging anchor algorithm is that we consider both the player's current strategy and the long-term average of the player's previous strategies at the same time. We expect that the player's current strategy and the long-term average will be drawn toward the equilibrium point during learning.

To analyze the above   lagging anchor algorithm, we use ordinary differential equations (ODEs). The behavior of the learning algorithm can be approximated by ODEs as the step size goes to zero. Thathachar and Sastry [19] provided the equivalent ODEs of the   algorithm in (3.55) as

**3.59**

where   is the expected reward given that player   is choosing action   and the other players are following their current strategies.

Combining the above ODEs of the   algorithm in (3.59) with the ODEs for the lagging anchor part of our algorithm, we can find the equivalent ODEs for our   lagging anchor algorithm, given as

**3.60**

Based on our proposed   lagging anchor algorithm, we now present the following theorem:

* * *

### Theorem 3.3

We consider a two-player two-action general-sum matrix game and assume the game only has a Nash equilibrium in fully mixed strategies or strict Nash equilibria in pure strategies. If both players follow the   lagging anchor algorithm, when the step size  , then the following is true regarding the asymptotic behavior of the algorithm:

  * All Nash equilibria are asymptotically stable;
  * Any equilibrium point which is not a Nash equilibrium is unstable.

* * *

* * *

### _Proof_

Given a two-player two-action general-sum game defined in (3.6), we denote   as the probability of player 1 taking its first action and   as the probability of player 2 taking its first action. Then the   lagging anchor algorithm becomes

**3.61**

where  ,  ,  , and  . Then (3.61) becomes

**3.62**

where   and  . If we let the right-hand side of the above equation equal to zero, we then get the equilibrium points of the above equations as  . To study the stability of the above learning dynamics, we use a linear approximation of the above equations around the equilibrium point  . Then the linearization matrix   is given as

**3.63**

If we substitute each of the equilibrium points   into (3.63), we get

**3.64**

where

**3.65**

**3.66**

**3.67**

**3.68**

The eigenvalues of the above matrix   are   and  . In order to obtain a stable equilibrium point, the real parts of the eigenvalues of   must be negative. Therefore, the equilibrium point is asymptotically stable if

**3.69**

For the equilibrium point  , the linearization matrix becomes

**3.70**

The characteristic equation of the above matrix is

**3.71**

where  . We set up the Routh table to analyze the locations of the roots in (3.71) as follows:

**3.72**

Based on the Routh–Hurwitz stability criterion, if (3.71) is stable, then all the coefficients of the equation must be positive and all the elements in the first column of the Routh table in (3.72) are positive. In order to meet the Routh–Hurwitz stability criterion, we must have  . Therefore, the equilibrium point   is asymptotically stable if

**3.73**

* * *

* * *

### Case 3.1

### Strict Nash equilibrium in pure strategies

We first consider that the game only has strict Nash equilibrium in pure strategies. Without loss of generality, we assume that the Nash equilibrium in this case is both players' first actions. According to the definition of a strict Nash equilibrium in the inequality (3.7), if the Nash equilibrium strategies are both players' first actions, we can get

**3.74**

Since the Nash equilibrium in this case is the equilibrium point  , we can get   and   based on (3.68) and (3.74). Therefore, the stability condition (3.69) is satisfied and the equilibrium point  , which is the Nash equilibrium in this case, is asymptotically stable.

We now test the other equilibrium points. We first consider the equilibrium point  . According to the stability condition (3.73), if this equilibrium point is stable, we must have  . To be a valid inner point in the probability space (unit square), the equilibrium point   must satisfy

**3.75**

If  , we can get

**3.76**

**3.77**

However, the conditions in the inequalities (3.76) and (3.77) conflict with the inequalities in (3.74). Therefore, the inequality   will not hold and the equilibrium point    is unstable in Case 3.1.

For the equilibrium points   and  , based on (3.66), (3.67), and (3.69), the stability conditions are   for   and   for  . However, these stability conditions conflict with the inequalities   in (3.74). Therefore, the equilibrium points   and   are unstable in Case 3.1.

For the equilibrium point  , the stability condition is   based on conditions (3.65) and (3.69). From the inequality (3.7), we can find that this stability condition also meets the requirement for a strict NE (both players' second actions) in inequality (3.7). Therefore, the equilibrium point   is stable only if it is also an NE point.

Thus, the NE point is asymptotically stable, while any equilibrium point which is not an NE is unstable.

* * *

* * *

### Case 3.2

### Nash equilibrium in fully mixed strategies

We now consider that the game only has Nash equilibrium in fully mixed strategies. Singh et al. [9] showed that a Nash equilibrium in fully mixed strategies for a two-player two-action general-sum matrix game has the form

**3.78**

where ( ) denotes the Nash equilibrium strategies over players' first actions which happens to be the equilibrium point of (3.62). According to the condition (3.73), the equilibrium point   is asymptotically stable if  . If we assume  , we can get

**3.79**

**3.80**

According to the inequality (3.7), the above equations contain multiple NEs in pure strategies:   if   and   if  . However, under our assumption, the game in Case 3.2 only has an NE in fully mixed strategies, and NEs in pure strategies do not exist. Therefore, we always have   in Case 3.2 and the equilibrium point  , which is also the NE point, is asymptotically stable.

For the other equilibrium points, based on conditions (3.65)–(3.68) and (3.69), the stability conditions become

**3.81**

**3.82**

**3.83**

**3.84**

As already noted, the game in Case 3.2 only has an NE in fully mixed strategies and we always have  . Then the inequalities (3.76) and (3.77) are true in Case 3.2. However, the stability conditions (3.81)–(3.84) for the equilibrium points   conflict with the inequalities (3.76) and (3.77). Therefore, the equilibrium points other than   are unstable in this case.

Thus we can conclude that the NE point is asymptotically stable while the other equilibrium points are unstable in Case 3.2.

* * *

### 3.14.1 Simulation

We now simulate three matrix games to show the performance of the   lagging anchor algorithm. The first game is the matching pennies game. This game is a two-player zero-sum game and each player has two actions: heads or tails. If both players choose the same action, then player 1 gets a reward 1 and player 2 gets a reward  . If the actions are different, then player 1 gets   and player 2 gets 1. Based on the reward matrix in Table 3.1(a) and the solutions in Example 3.1, the NE in this game is in fully mixed strategies such that each player plays heads and tails with a probability of 0.5. We set the step size   in (3.58) and  . We run the simulation for 30,000 iterations. In Fig. 3-9, the players' probabilities of taking their first actions start from (0.2, 0.2) and move close to the NE point (0.5, 0.5) as the learning proceeds.

**Figure 3-9** Trajectories of players' strategies during learning in matching pennies.

Reproduced from [8], © X. Lu.

The second game we simulate is a two-player general-sum game, namely the prisoners' dilemma. In this game, we have two players and each player has two actions: defect or cooperate. A player receives a reward of 10 if it defects and the other player cooperates, or receives a reward of 0 if it cooperates and the other player defects. If both players cooperate, each player receives a reward of 5. If they both defect, each player receives a reward of 1. The reward matrix is shown in Table 3.3(b), where one player's reward matrix is the transpose of the other player's reward matrix. This game has a unique NE in pure strategies which is both players playing defect. We set the step size   in (3.58) and  . We run the simulation for 30,000 iterations. Figure 3-10 shows that the players' strategies move close to the NE strategies (both players' second actions) as the learning proceeds.

**Table 3.3** Examples of two-player matrix games.

---

**Figure 3-10** Trajectories of players' strategies during learning in prisoners' dilemma.

Reproduced from [8], © X. Lu.

The third game we simulate in this chapter is the rock-paper-scissors game. This game has two players and each player has three actions: rock, paper, and scissors. A winner in the game is determined by the following rules: paper defeats rock, scissors defeats paper, and rock defeats scissors. The winner receives a reward of 1 and the loser receives  . If both players choose the same action, each player gets 0. The reward matrix is shown in Table 3.3(c). This game has an NE in fully mixed strategies which is each player choosing any action with the same probability of  . We set the step size  ,  , and  . We run the simulation for 50,000 iterations. Although we only prove the convergence for two-player two-action games, the result in Fig. 3-11 shows that the proposed   lagging anchor algorithm may be applicable to a two-player matrix game with more than two actions.

**Figure 3-11** Trajectories of players' strategies during learning in rock-paper-scissors.

Reproduced from [8], © X. Lu.

## References

  1. [1] M. J. Osborne and A. Rubinstein, _A Course in Game Theory_. Cambridge, Massachusetts: The MIT Press, 1994.
  2. [2] G. Owen, _Game Theory_. San Diego, California: Academic Press, 1995.
  3. [3] M. Bowling and M. Veloso, "Multiagent learning using a variable learning rate," _Artificial Intelligence_ , vol. **136** , no. 2, pp. 215–250, 2002.
  4. [4] T. Ba ar and G. J. Olsder, _Dynamic Noncooperative Game Theory_ , SIAM Series in Classics in Applied Mathematics. London: Academic Press, 2nd ed., 1999.
  5. [5] P. Sastry, V. Phansalkar, and M. Thathachar, "Decentralized learning of Nash equilibria in multi-person stochastic games with incomplete information," _IEEE Transactions on Systems, Man, and Cybernetics_ , vol. **24** , no. 5, pp. 769–777, 1994.
  6. [6] M. J. Osborne, _An Introduction to Game Theory_. Oxford: Oxford University Press, 2003.
  7. [7] M. L. Littman, "Markov games as a framework for multi-agent reinforcement learning," in 11th International Conference on Machine Learning, (New Brunswick, United States), July 1994, pp. 157–163, 1994.
  8. [8] X. Lu, Ph.D., "On Multi-Agent Reinforcement Learning in Games." Ph.D. Thesis, Carleton University, Ottawa, ON, 2012.
  9. [9] S. P. Singh, M. J. Kearns, and Y. Mansour, "Nash convergence of gradient dynamics in general-sum games," in UAI '00: Proceedings of the 16th Conference in Uncertainty in Artificial Intelligence, Stanford University, Stanford, California, USA, June 30 - July 3, 2000, pp. 541–548, 2000.
  10. [10] C. J. C. H. Watkins and P. Dayan, "Q-learning," _Machine Learning_ , vol. **8** , no. 3, pp. 279–292, 1992.
  11. [11] E. Yang and D. Gu, "A survey on multiagent reinforcement learning towards multi-robot systems," in Proceedings of IEEE Symposium on Computational Intelligence and Games, 2005.
  12. [12] L. Bu oniu, R. Babuška, and B. D. Schutter, "Multiagent reinforcement learning: a survey," 9th International Conference on Control, Automation, Robotics and Vision (ICARCV), pp. 1–6, 2006.
  13. [13] X. Lu and H. M. Schwartz, "An investigation of guarding a territory problem in a grid world," in American Control Conference, pp. 3204–3210, 2010.
  14. [14] S. Lakshmivarahan and K. S. Narendra, "Learning algorithms for two-person zero-sum stochastic games with incomplete information," _Mathematics of Operations Research_ , vol. 6, no. 3, pp. 379–386, 1981.
  15. [15] S. Lakshmivarahan and K. S. Narendra, "Learning algorithms for two-person zero-sum stochastic games with incomplete information: a unified approach," _SIAM Journal on Control and Optimization_ , vol. **20** , no. 4, pp. 541–552, 1982.
  16. [16] F. A. Dahl, "The lagging anchor algorithm: reinforcement learning in two-player zero-sum games with imperfect information," _Machine Learning_ , vol. **49** , pp. 5–37, 2002.
  17. [17] F. A. Dahl, "The lagging anchor model for game learning—a solution to the crawford puzzle," _Journal of Economic Behavior & Organization_, vol. **57** , pp. 287–303, 2005.
  18. [18] K. S. Narendra and M. A. L. Thathachar, _Learning Automata: An Introduction_. Englewood Cliffs, New Jersey: Prentice Hall, 1989.
  19. [19] M. Thathachar and P. Sastry, _Networks of Learning Automata: Techniques for Online Stochastic Optimization_. Boston, Massachusetts: Kluwer Academic Publishers, 2004.

# Chapter 4  
Learning in Multiplayer Stochastic Games

## 4.1 Introduction

The agents in a multiagent system can be to some degree preprogrammed with behaviors designed in advance. It is often necessary that the agents be able to learn online such that the performance of the multiagent system improves. However, typically a multiagent system is very complex and preprogramming the system is for practical reasons impossible. Furthermore, the dynamics of the agents and the environment can change over time and learning and adaptation is required.

In early work on multiagent reinforcement learning (MARL) for stochastic games [1], it was recognized that no agent works in a vacuum. In his seminal paper, Littman [1] focused on only two agents that had opposite and opposing goals. This means that they could use a single reward function which one tried to maximize and the other tried to minimize. The agent had to work with a competing agent and had to behave so as to maximize their reward in the worst possible case. They also recognized the need for mixed strategies because the agent or player could not be certain of the action taken by its opponent. Littman [1] introduced the minimax Q-learning algorithm. We have already shown the idea of the minimax Q-learning algorithm in Chapter 3, Section 3.2.

In a rational multiagent game, each agent must keep track in some way of what the other learning agents are doing. The types of games and situations that the learning agent may encounter include fully competitive games that are zero-sum games. There are also general-sum cooperative games, where the agents try to get the maximum reward by cooperating with each other. For example, in the prisoners' dilemma problem, if it is a cooperative game, then each player should lie to the police and cooperate with each other and get the least time in jail. However, if it is a competitive game, then they should each defect to mitigate against the worst case scenario where one lies to police and the opponent confesses and the first one goes to jail for life. However, the agents must communicate to cooperate with each other.

Typically, in a multiagent system, the agents must keep track of the other agents' behaviors such that a coherent behavior results. Furthermore, we have the issue of scalability to consider. The agents must keep track of a large number of possiblestates and joint actions.

Learning in stochastic games can be formalized as a MARL problem [2]. Agents select actions simultaneously at the current state and receive rewards at the next state. Different from the algorithm that can solve for a Nash equilibrium in a stochastic game, the goal of a reinforcement learning algorithm is to learn equilibrium strategies through interaction with the environment. Generally, in a MARL problem, agents may not know the transition function or the reward function from the environment. Instead, agents are required to select actions and observe the received reward and the next state in order to gain information of the transition function or the reward function.

Rationality and convergence are two desirable properties for multiagent learning algorithms in stochastic games [2]. When we say that a player is rational, we mean that, if the other players' policies converge to stationary policies, then the learning algorithm for will converge to a policy that is a best response to the other players' policies. What does this mean? Let us say that you are playing the matching pennies game against a _bad_ player who always plays heads. You win whenever you both play heads or tails. At first, you assume that your opponent is a rational player and, therefore, you assume that your opponent is playing the rational strategy of playing heads and tails each 50% of the time. Therefore, you start out playing heads and tails 50% of the time. However, after a number of plays you realize that your opponent always seems to be playing heads as his stationary strategy. You would then quickly shift and begin to also play heads all the time. Then you always win and you are playing the rational strategy but your opponent is not playing a rational strategy.

In the stochastic learning algorithms, we also have the idea of convergence. Let us say that all the other players are playing a stationary strategy. They are not learning or changing their strategy in any way. Then you adapt to this behavior and converge to some rational strategy. Or, let us say that everyone in the game is adapting according to the same algorithm. Then do all the players converge to an optimal strategy or a Nash equilibrium? If all the players use rational learning algorithms and their policies converge, then they must have converged to an equilibrium. Each player will play the best response to all other players.

In this chapter, we review some existing reinforcement learning algorithms in stochastic games. We analyze these algorithms based on their applicability, rationality, and convergence properties.

Isaacs [3] introduced a differential game of guarding a territory where a defender tries to intercept an invader before the invader reaches the territory. In this chapter, we introduce a grid version of Isaacs' game called the _grid game of guarding a territory_. It is a two-player zero-sum stochastic game where the defender plays against the invader in a grid world. We then study how the players learn to play the game using MARL algorithms. We apply two reinforcement learning algorithms to this game and test the performance of these learning algorithms based on the convergence and rationality properties.

## 4.2 Multiplayer Stochastic Games

A Markov decision process contains a single player and multiple states, whereas a matrix game contains multiple players and a single state. For a game with more than one player and multiple states, we define a stochastic game (or Markov game) as the combination of Markov decision processes and matrix games. A stochastic game is a tuple   where   is the number of the players,   is the transition function,   is the action set for the player  ,   is the discount factor, and   is the reward function for player  . The transition function in a stochastic game is a probability distribution over next states given the current state and joint action of the players. The reward function   denotes the reward received by player   in state   after taking joint action   in state  . Similar to Markov decision processes, stochastic games also have the Markov property. That is, the player's next state and reward depend only on the current state and all the players' current actions.

For a multiplayer stochastic game, we want to find the Nash equilibria in the game if we know the reward function and transition function in the game. A Nash equilibrium in a stochastic game can be described as a tuple of   strategies   such that for all   and  ,

**4.1**

where   is the set of strategies available to player  , and   is the expected sum of discounted rewards for player   given the current state and all the players' equilibrium strategies. To simplify notation, we use   to represent   as the state-value function under Nash equilibrium strategies. We can also define the action-value function   as the expected sum of discounted rewards for player   given the current state and the current joint action of all the players, and following the Nash equilibrium strategies thereafter. Then we can get

**4.2**

**4.3**

where   is a probability distribution over action   under player  's Nash equilibrium strategy,   is the probability of the next state being   given the current state   and joint action  , and   is the expected immediate reward received in state   given the current state   and joint action  . Based on (4.2) and (4.3), the Nash equilibrium in (4.1) can be rewritten as

**4.4**

Stochastic games can be classified on the basis of the players' reward functions. If all the players have the same reward function, the game is called a _fully cooperative game_ or a _team game_. If one player's reward function has always the opposite sign of the other player's, the game is called a _two-player fully competitive game_ or _zero-sum game_. For the game with all types of reward functions, we call it a general-sum stochastic game.

To solve a stochastic game, we need to find a strategy   that can maximize player  's discounted future reward with a discount factor  . Similar to the strategy in matrix games, the player's strategy in a stochastic game is probabilistic. An example is the soccer game introduced by Littman [1], where an agent on the offensive side must use a probabilistic strategy to pass an unknown defender. In the literature, a solution to a stochastic game is described as Nash equilibrium strategies in a set of associated _state-specific matrix games_ [1, 4]. A state-specific matrix game is also called a _stage game_. In these state-specific matrix games, we define the action-value function   as the expected reward for player   when all the players take joint action   in state   and follow the Nash equilibrium strategies thereafter. If the value of   is known for all the states, we can find player  's Nash equilibrium strategy by solving the associated state-specific matrix game [4]. Therefore, for each state  , we have a matrix game and we can find the Nash equilibrium strategies in this matrix game. Then the Nash equilibrium strategies for the game are the collection of Nash equilibrium strategies in each state-specific matrix game for all the states. We present an example here.

* * *

### Example 4.1

We define a   grid game with two players denoted as   and  . Two players' initial positions are located at the bottom left corner for player   and the upper right corner for player 2, as shown in Fig. 4-1a. Both players try to reach one of the two goals denoted as "G" in minimum number of steps. Starting from their initial positions, each player has two possible moves which are moving up or right for player  , and moving left or down for player  . Figure 4-1b shows the numbered cells in this game. Each player takes an action and moves one cell at a time. The game ends when either of the players reaches the goal and receives a reward 10. The dashed line between the upper cells and the bottom cells in Figure 4-1a is the barrier that the player can pass through with a probability 0.5. If both players move to the same cell, both players bounce back to their original positions. Figure 4-1c shows the possible transitions in the game. The number of possible states (players' joint positions) is seven containing the players' initial positions   and six terminal states  .

According to the above description of the game, we can find the Nash equilibrium strategies in this example. The players need to avoid the barrier and move to the goals next to them without crossing the barrier. Therefore, the Nash equilibrium is the players' joint action  . Based on (4.2) and (4.3), the state-value function   under the Nash equilibrium strategies is

**4.5**

where  ,  , and   (the state-value functions at terminal states are always zero). We can also find the action-value function  . For example, the action-value function   for player 1 can be written as

**4.6**

Table 4.1 shows the action-value functions under the players' Nash equilibrium strategies.

* * *

**Table 4.1** Action-value function   in Example 4.1.

---

**Figure 4-1** Example of stochastic games. (a) A   grid game with two players. (b) The numbered cells in the game. (c) Possible state transitions given players' joint action ( ). Reproduced from [5], © X. Lu.

## 4.3 Minimax-Q Algorithm

Littman [1] proposed a minimax-Q algorithm specifically designed for two-player zero-sum stochastic games. The minimax-Q algorithm uses the minimax principle to solve for players' Nash equilibrium strategies and values of states for two-player zero-sum stochastic games. Similar to Q-learning, minimax-Q algorithm is a temporal-difference learning method that performs backpropagation on values of states or state-action pairs. We show the minimax-Q algorithm as follows:

In a two-player zero-sum stochastic game, given the current state  , we define the state-value function for player   as

**4.7**

where   denotes player  's opponent,   denotes all the possible strategies of player   at state  , and   is the expected reward when player   and its opponent choose action   and  , respectively, and follow their Nash equilibrium strategies after that. If we know  , we can solve Eq. (4.7) and find player  's Nash equilibrium strategy  . Similar to finding the minimax solution for (3.8), one can use linear programming to solve Eq. (4.7). For a MARL problem,   is unknown to the players in the game.

The minimax-Q algorithm is listed in Algorithm 4.1. The minimax-Q algorithm can guarantee the convergence to a Nash equilibrium if all the possible states and players' possible actions are visited infinitely often. The proof of convergence for the minimax-Q algorithm can be found in Reference [6]. One drawback of this algorithm is that we have to use linear programming to solve for   and   at each iteration in Algorithm 4.1.

This will lead to a slow learning process. Also, in order to perform linear programming, the player   has to know the opponent's action space.

Using the minimax-Q algorithm, the player will always play a "safe" strategy in case of the worst scenario caused by the opponent. However, if the opponent is currently playing a stationary strategy which is not its equilibrium strategy, the minimax-Q algorithm cannot make the player adapt its strategy to the change in the opponent's strategy. The reason is that the minimax-Q algorithm is an opponent-independent algorithm and it will converge to the player's Nash equilibrium strategy no matter what strategy the opponent uses. If the player's opponent is a weak opponent that does not play its equilibrium strategy, then the player's optimal strategy is not the same as its Nash equilibrium strategy. The player's optimal strategy will do better than the player's Nash equilibrium strategy in this case.

Overall, the minimax-Q algorithm, which is applicable to zero-sum stochastic games, does not satisfy the rationality property but satisfies the convergence property. The following example of a   grid game demonstrates the algorithm.

### 4.3.1   Grid Game

The playing field of the   grid game is shown in Fig. 4-2. The territory to be guarded is located at the bottom-right corner. Initially, the invader starts at the top-left corner while the defender starts at the same cell as the territory. To better illustrate the guarding a territory problem, we simplify the possible number of actions of each player to 2. The invader can only move down or right, while the defender can only move up or left. The capture of the invader happens when the defender and the invader move into the same cell excluding the territory cell. The game ends when the invader reaches the territory or the defender catches the invader before it reaches the territory. We suppose both players start from the initial state  , as shown in Fig. 4-2a. There are three nonterminal states ( ) in this game shown in Fig. 4-2. If the invader moves to the right cell and the defender happens to move left, then both players reach the state   in Fig. 4-2b. If the invader moves down and the defender moves up simultaneously, then they will reach the state   in Fig. 4-2c. In states   and  , if the invader is smart enough, it can always reach the territory no matter what action the defender will take. As such, the game only has one step because, if the invader gets to state   or  , it de facto wins. Therefore, starting from the initial state  , a clever defender will try to intercept the invader by guessing which direction the invader will go.

**Figure 4-2** A   grid game. (a) Initial positions of the players: state  . (b) Invader in top-right versus defender in bottom-left: state  . (c) Invader in bottom-left versus defender in top-right: state  . Reproduced from [5], © X. Lu.

We define the reward functions for the players. The reward function for the defender is defined as

**4.9**

where

The reward function for the invader is given by

**4.10**

The reward functions (4.9) and (4.10) are also used in the   grid game.

Before the simulation, we can simply solve this game similar to solving Example 4.1. In the states   and  , a smart invader will always reach the territory without being intercepted. The value of the states   and   for the defender will be   and  . We set the discount factor as 0.9 and we can get  ,  ,  , and  , as shown in Table 4.2 and Table 4.3a. Under the Nash equilibrium, we define the probabilities of the defender moving up and left as   and  , respectively. The probabilities of the invader moving down and right are denoted as   and  , respectively. Based on the  -values in Table 4.3a, we can find the value of the state   for the defender by solving a linear programming problem shown in Table 4.3b. The approach for solving a linear programming problem can be found in Section 3.2.

**Table 4.2** Minimax solution for the defender in the state  .

---

**Table 4.3** Minimax solution for the defender in the state  . (a)  -values of the defender for the state  . (b) Linear constraints for the defender in the state  .

---

We define   to denote the immediate reward to the agent for taking action   in state   when its opponents take action  . The idea is for the agent to maximize its reward in the worst possible case. In other words, the agent assumes that the other agent is playing its best possible strategy in a purely competitive game. Therefore, the agent's optimal policy would be to maximize the minimum possible reward. Just like in the case of the prisoners' dilemma, the action should be to defect because this will limit cost of the worst possible outcome regardless of what the other player does. If the prisoner/player decides not to defect, and if the other player does defect, then the prisoner/player will go to jail for a long time; therefore, to maximize the worst possible outcome, the prisoner/player should defect.

Now imagine that we would be satisfied with a policy that guarantees an expected reward   no matter what the other player, in this case an opponent, chooses as its action. In this case, the defender's reward matrix in state   is

**4.11**

Recall that the policy in this case is given as the probability that the agent in state   will choose to go up,  , and the probability that the agent will choose to go left,  .

Then we get the following equations for the expected reward, regardless of which action the opponent takes:

Therefore, the goal is to maximize the expected reward   regardless of what the opponent does.

After solving the linear constraints in Table 4.3b, we get the value of the state   for the defender as   and the Nash equilibrium strategy for the defender as   and  . For a two-player zero-sum game, we can get  . Similar to the approach in Table 4.3, we can find the minimax solution of this game for the invader as  ,  , and  . Therefore, the Nash equilibrium strategy of the invader is to move down or right with probability 0.5, and the Nash equilibrium strategy of the defender is to move up or left with probability 0.5.

The implementation of the minimax Q-learning algorithm begins by initializing the Q matrix, the value function  , and the policy   for each agent. In the example shown here, we initialize   and  . We arbitrarily initialized the probability of the defender to go up as   and   and of the invader   and  . We set the discount factor as  , the learning rate to  , and the exploration probability to  . The constraint condition for the linear programming problem for the defender is

**4.12**

Similarly, for the invader we get

**4.13**

The linear programming algorithm is run separately for both the invader and the defender. The algorithm (such as the simplex method) will determine the values of  , and   at each iteration. The agents do not know a priori the rewards. The best estimate of the rewards is the state-action function  . Therefore, the minimax Q-learning algorithm updates both the expected rewards and the policy,  , simultaneously. To use MATLAB to compute the linear programming solution, we need to get the equations into the correct form. MATLAB structures the linear programming problem as

**4.14**

given the constraints

and

Notice that MATLAB formulates the problem as a minimization problem. We convert the reward maximization problem in the minimax algorithm into a minimization problem by multiplying by  . We substitute the agents' best estimate of its reward for   and   with   and   and rewrite the minimization problem for the defender and the invader. For the case of the defender, we write the minization problem as

where   and  , subject to the constraint

and

Then the matrix   becomes

The matrix   becomes  . The equivalency condition, which states that the action probabilities sum to 1, is given by

and  .

For the sake of completeness, we also write out the matrix equations for the invader as

where   and  , subject to the constraint

and

Then the matrix   becomes

The matrix   becomes  . The equivalency condition, which states that the action probabilities sum to 1, is given by

and  .

We first apply the minimax-Q algorithm to the game. To better examine the performance of the minimax-Q algorithm, we use the same parameter settings as in Reference [1]. We use the  -greedy policy as the exploration-exploitation strategy. The  -greedy policy is defined such that the player chooses an action randomly from the player's action set with a probability   and a greedy action with a probability  . The greedy parameter   is given as 0.2. The learning rate   is chosen such that the value of the learning rate will decay to 0.01 after one million iterations. The discount factor   is set to 0.9. The number of iterations represents the number of times the step   is repeated in Algorithm 4.1. After learning, we plot the players' learned strategies in Fig. 4-3.

Figure 4-3 Minimax Q-learning for the defender/invader game. Action probability for the defender.

## 4.4 Nash Q-Learning

The Nash Q-learning algorithm, first introduced in Reference [7], extends the minimax-Q algorithm [1] from zero-sum stochastic to general-sum stochastic games. In the Nash Q-learning algorithm, the Nash  -values need to be calculated at each state in order to update the action-value functions and find the equilibrium strategies. Although Nash Q-learning is applied to general-sum stochastic games, the conditions for the convergence to a Nash equilibrium do not cover a correspondingly general class of environments [8]. The corresponding class of environments are actually limited to cases where the game being learned only has coordination or adversarial equilibrium [8, 10]. The Nash Q-Learning algorithm is shown in Algorithm 4.2.

To guarantee the convergence to Nash equilibria in general-sum stochastic games, the Nash Q-learning algorithm needs to hold the following condition during learning: every stage game (or state-specific matrix game) has a global optimal point or a saddle point for all time steps and all the states [8]. Since the above strict condition is defined in terms of the stage games as perceived during learning, it cannot be evaluated in terms of the actual game being learned [8]. Similar to the minimax Q-learning, the Nash Q-learning algorithm needs to solve the appropriate search algorithm (such as the Lemke–Howson algorithm) at each iteration in order to obtain the Nash  -values, which leads to a slow learning process.

The Nash Q-learning algorithm extends the Q-learning algorithm to the noncooperative multiagent context. The learning agent maintains a Q-function overjoint actions and performs updates by assuming the existence of Nash equilibrium. This algorithm provably converges given certain constraints on stage games. Hu and Wellman [8] find that agents are more likely to reach a joint optimal path with Nash-Q than with single-agent Q-learning. Although the single-agent properties of Q-learning do not transfer to the multiagent case, the ease of application does.

Direct implementation of Q-learning to the multiagent context is affected by three issues. The environment is no longer stationary, the familiar guarantees are no longer true, and the nonstationary environment is populated by other agents which we assume to be rational. Explicitly accounting for the fact that the agent is operating with other "rational" agents improves the learning process [1, 8, 11]. The reward depends on the joint actions of the other learners. The default or baseline solution concept for general-sum games is the Nash equilibrium. In the framework of general-sum stochastic games, we define optimal  -values as those values received in Nash equilibrium and refer to them as _Nash Q-values_. The goal is to find the Nash  -values through repeated play. Agents have to learn the behavior of the other agents and then determine their own best response. In Reference [8], two grid games are proposed. In grid game 1, there are three equally valued global optimal points. Grid game 2 does not have a saddle point or a global optimal point but three sets of other Nash equilibria and in these cases the algorithm does not always converge.

As we recall from the single-agent Q-learning, the agent's objective is to find a strategy (policy)   so as to maximize the sum of discounted future rewards, given by

**4.16**

The search algorithm attempts to find the stationary point of

**4.17**

The solution to the above Bellman equation is guaranteed to be optimal. Define the optimal Q-function as

**4.18**

The term   is the total discounted reward for taking action  , in state   and then following the optimal policy thereafter. By definition, we have

**4.19**

If we know  , then the problem can be solved simply by taking the action that maximizes  . The Q-learning algorithm is a stochastic approximation algorithm, given by

**4.20**

Hu and Wellman [8] limit their work to stationary strategies and state the following theorem:

* * *

### Theorem 4.1

Theorem 4 (Fink, 1964): Every  -player discounted stochastic game possesses at least one Nash equilibrium point in stationary strategies.

* * *

The Q-learning algorithm is extended to multiagent games on the basis of the framework of stochastic games. The Nash  -value is the expected sum of future discounted rewards when all agents follow Nash equilibrium strategies from the next step onwards. This is different from the single-agent case where the future rewards are based only on the agent's own optimal strategy.

* * *

### Definition 4.1

### Hu and Wellman [8]

Agent  's Nash Q-function is defined over   as the sum of agent  's current reward plus its future rewards when all agents follow a joint Nash equilibrium strategy. That is,

**4.21**

where   is the joint Nash strategy,   is agent  's reward in state   and under joint action  , and   is agent  's total discounted reward from   given the other agents follow their Nash equilibrium strategy.

* * *

In the Nash Q-learning algorithm, the multiagent Q-learning algorithm updates with future Nash equilibrium payoffs, whereas the single-agent Q-learning updates are based on the maximum  -values in the agent's own payoff table. To know the Nash equilibrium payoffs, the agent must also know the reward received by the other agents. The agent must be able to observe these rewards in some way. We define the difference between the Nash equilibria for a stage game and for a stochastic game.

* * *

### Definition 4.2

### Hu and Wellman [8]

An  -player stage game is defined as  , where for   the term   is agent  's payoff function over the space of joint actions   and   is agent  's payoff.

* * *

The Nash Q-learning algorithm executes as follows: initialize the  -table as  . At each time  , agent   observes the current state and takes an action. Then the agent observes its reward, the rewards received by the other agents, and the new state. The agent then computes a Nash equilibrium at the new state for the stage or matrix game,  , and updates its  -values as

**4.22**

The notation for all players or agents playing their Nash equilibrium strategy is  , and the term   is the Nash equilibrium payoff for state  . Therefore, for agents to determine the Nash equilibrium, they each have to know the other agents'  -values. Thus agent   must learn the  -values for the other agents. For example, agent   may initialize the  -values for the other agents as   for all   and all  . Agent   observes the other agents' rewards and actions and then updates the other agents'  -values. The update rule is the same as above, that is

**4.23**

Therefore, only the entry in the  -table associated with the current state and action is updated. Although the Nash Q-learning algorithm can be written easily as in Algorithm 4.2, the algorithm is extremely complex. The user has to maintain multiple  -tables and then compute a Nash equilibrium that all agents agree upon. One of the difficulties in implementing the Nash Q-learning algorithm is the computation of the Nash equilibrium. Hu and Wellman [8] use the Lemke–Howson algorithm [12]. We will present a detailed description of this algorithm in Section 4.6. We will present the examples of the following two grid games that are also proposed in Reference [8] and used to evaluate several other algorithms as well. The games are illustrated in Figs. 4.4 and 4.5.

Figure 4-4 Two stochastic games [7]. (a) Grid game 1. (b) Grid game 2.

Figure 4-5 (a) Nash equilibrium of grid game 1. (b) Nash equilibrium of grid game 2. Reproduced from [8] with permission from MIT press.

The agents can move Up, Down Right and Left. If two agents move to the same cell, then they bounce back unless it is the goal cell. The game ends when an agent reaches the goal state. If both agents reach the goal state at the same time, then both get rewarded with positive payoff. Agents do not initially know their goals or their payoffs. The agents choose actions simultaneously. The grid cells are defined as starting with cell state 0 at the bottom left corner and incrementing from left to right until the top right hand corner which is cell state 8. For example the bottom right hand corner is cell state 2. The action space is   and a given state is given by   where   and   represent the locations of the first and the second agents. If an agent reaches its goal, then it gets a reward of 100. If the agents collide, both agents bounce back to their original position and get a negative reward of  , and if the agent moves to an empty cell, it receives 0 reward.

In grid game 1, the state transitions are deterministic, and in grid game 2 the transition through the barrier is 50%. For example, if agent 1 chooses action Up, and agent 2 chooses action Left, from state  ), we get the state transition probabilities as

and

Similarly, we have   and  . The Nash Q-learning algorithm assumes that the strategies are stationary. A stationary strategy assigns probability distributions over an agent's actions based on the current state, regardless of the history. This means that, if the agents are in the same state, then the action strategy would be the same for all the agents.

Assuming we have pure strategies, such as in game 1, and the strategy is based only on the location of the agents, then the strategies represent a path. The notation   refers to agent 1 being in state   and agent 2 being in _any_ state. Then we get a Nash equilibrium strategy as in Table 4.4. One of the Nash equilibrium strategies is depicted in Fig. 4-5. The value of the game for agent 1 is defined so that its accumulated reward when both agents follow their Nash equilibrium is given as

**4.24**

In grid game 1 and initial state  , this becomes, given

**4.25**

Based on the value for each state, we can derive the Nash  -values for agent 1 in state   as

**4.26**

We will evaluate the  -value for different actions for agent 1 in state (0, 2). Let us start with the action (Right, Left). If we take the action (Right, Left), then the two agents will bump into each other. This will give a penalty of  . Therefore, the  -value for taking the action (Right, Left) in state (0, 2) and then following the optimal path afterwards, from state (0, 2) (because the agents bounce back to state (0, 2)) is

**4.27**

We have already computed that  , and therefore

**Table 4.4** States and strategies.

State |    
---|---  
(0, 2) | Up  
(3, 5) | Right  
(4, 8) | Right  
(5, any) | Up

**4.28**

But, for the  -value for both agents going Up, we get

**4.29**

The Nash  -values for the agents when in state   are given in Table 4.5. For grid game 2, we can derive the Nash  -values. In this case, it is more complicated because we do not have deterministic state transitions. Let us start the agents in state (0, 1) as shown in Fig. 4-6. Then the optimal path for this position is one in which agent 2 takes two steps Up and gets the reward. Agent 1 cannot get to the goal before agent 2. Therefore, the value for agent 1 is

**4.30**

**Table 4.5** Grid game 1: Nash  -values in state (0, 2).

Action | Left | Up  
---|---|---  
Right | 95.1, 95.1 | 97, 97  
Up | 97, 97 | 97, 97

**Figure 4-6** Grid game with barriers, start position (0,1).

However, if we start in state (1, 2), then agent 1 takes two steps Up and wins, and the value for agent 1 is

**4.31**

However, if we start in state (0, 2), then we can only compute the value in expectation because if the agents choose the action Up, there is only 50% probability that they would go Up and a 50% probability that they stay in the same spot. For starting in state (0, 2), we get the  -value as

**4.32**

The next action is  . In this case, there is only a 50% chance that the agent goes Up. So we write out the  -value as

**4.33**

If the agents take actions (Right, Up), then we may end up in the position (1, 2) or (1, 5). Now, recall that if the agents are in state (1, 2), then the optimal solution from there is to take two steps Up. Similarly, the agent in state (1, 5) has the optimal solution of two steps, Up and Left. Recall, the values of  . Then we can compute

**4.34**

Now let us take the case of  . In this case, there is only 50% chance that agent 1 moves Up and 50% chance that the agent stays in the same position. Then we can compute

**4.35**

We already know that the value of  ; this is because agent 2 will take two steps Up and win. If agent 1 gets through the barrier, then it is in position (3, 1) and agent 1 then takes two steps, Up and Left, and wins at the same time as agent 2 takes two steps, Up and Up, and wins. Therefore, we get  , and we can compute the optimal  -value as

**4.36**

Finally, we compute the value for  . In this case, there are four possible outcomes for the next state. Each agent has a 50% probability of moving Up, therefore there is 25% probability for both agents to move Up at the same time. The probability of achieving state (3, 2) is 25%, state (3, 5) is 25%, state (0, 2) is 25%, and state (0, 5) is 25%. So the  -value for   is

**4.37**

We know the value of  ,  , and  . Then,

Now let us define   to be agent 1's optimal value by following a Nash equilibrium strategy starting from state (0, 2). The obvious Nash equilibrium for agent 1 of game 2 from the initial state (0, 2) is (Right, Up). Given that (Right, Up) is the Nash equilibrium then,  . Then we can derive the other values in the  -table. On the other hand, the obvious Nash equilibrium for the second agent is (Up, Left), but for agent 1  . Furthermore, there is also a mixed strategy of  . There are three sets of possible Nash equilibria for grid game 2.

### 4.4.1 The Learning Process

Let us say that learning of agent 1 begins by initializing the  -table as   for all  ,  , and  . These are agent  's internal beliefs, and have nothing to do with the other agent. We start the game from the initial state (0, 2). The agents then move simultaneously and observe the action taken by the agents and the rewards that the agents receive. The agents then update their  -tables according to the following:

**4.38**

The process is repeated in the next state until the goal state is reached. Then a new game starts and each agent is randomly assigned a new starting position except for the goal state. The training stops after 5000 episodes. Each episode takes approximately eight steps. Therefore, one experiment takes 40,000 steps. Furthermore, the learning rate is given by

**4.39**

where   is the number of times the states and actions   have been visited.

If we look at the algorithm, we see that we have to compute the Nash equilibrium of the stage game with  . There may be a choice between multiple Nash equilibria. Hu and Wellman [8] use the Lemke–Howson [12] algorithm to compute the Nash equilibrium for the two-player game. The Lemke–Howson algorithm resembles the simplex algorithm from linear programming.

#

#

## 4.5 The Simplex Algorithm

The simplex algorithm is a well-known algorithm for solving linear programming problems. These are problems of maximizing a utility function or a cost function subject to a number of linear constraints. The linear programming model is as follows: Maximize

**4.40**

subject to the set of constraints

**4.41**

The simplex algorithm searches for vertices of a polytope that defines the accessible region of the solution space. One goes from vertex to vertex to find the solution. The algorithm assumes nonnegativity. Inequalities are converted into equalities by adding slack variables. Let us take the following example. This example is taken from _Design and Planning of Engineering Systems_ [13] (Fig. 4-7). Maximize

**4.42**

subject to the constraints

**4.43**

and the nonnegativity constraint   and  . For each one of the constraints, we add a slack variable  ,  , or  . We therefore convert the inequality constraints into equality constraints, as

**4.44**

**Figure 4-7** Constraint equations plotted for the simplex method.

The slack variables represent how much room one has before one hits the constraint. One initializes the system to start with the variables set to   and  . This gives the solution to the slack variables as  . The nonzero variables are known as the _variables in the basis_. In this first step we have selected, the origin as the first vertex and the value of the reward or value function   is zero,  . We now have to move to the next extremal point. This is equivalent to moving one variable out of the basis and moving another variable into the basis. The next step is to determine which variable leaves the basis and which one enters the basis. We put into the basis the variable that causes the greatest growth in the payoff or reward function. Therefore, in this case we put   into the basis because the payoff function will grow by 13 units for every unit of   whereas it only grows by 11 units for every unit of  . Then the first constraint is reached when   and then  . The second constraint is reached when   and then  . The final constraint is reached when   and  . Therefore,   hits constraint C first when it is equal to 315. Then   enters the basis, and   leaves the basis. We then write the variables in the basis in terms of only the variables not in the basis. This is a form of Gaussian elimination. At the next vertex we get  ,  , and  . We then write the system of equations as

**4.45**

Recall that it is the   slack variable that goes to  . Therefore, we use Eq. C, to solve for  . Essentially, using Gaussian elimination we multiply Eq. C by   and add Eq. C to Eq. A and get

Then multiply Eq. C by   and add to Eq. B and we get

Similarly, divide Eq. C by 5 and we get

And, finally, multiply Eq. C by   and add it to Eq. D and we get

We see from these equations that, if   increases, then so does the payoff function  . This is because the coefficient of   in Eq. A1 is negative. So,   will enter the basis and either   or   will leave the basis. The slack variable   remains zero because we are moving along the edge defined by constraint C. Along this edge, the slack variable is zero.

Therefore, when   and   are zero,   can grow to  ; if   and   are zero, then   can grow to  ; and if   and   are zero, then   can grow to  . The limiting case is when   is zero and  . This represents the intersection of the two constraints C and D. Then we use Gaussian elimination again and write out the equations in terms of   and   only. Then we multiply Eq. D1 by   and add it to Eq. A1 and get

We can longer increase   without violating a constraint condition. Similarly, we remove   from Eq. B1 by multiplying Eq. D1 by   and add it to Eq. B1.This gives

Similarly, for Eq. C1 we multiply Eq. D1 by   and add it to Eq. C1 and get

Finally, we multiply Eq. D1 by   and get

To summarize, we can write the equations as

**4.46**

Recall that the slack variables   and   are zero at the intersection of the constraint equations C and D. Then the optimal value for the cost or payoff function is   and   and   and the slack value of the constraint given by Eq. B is  .

## 4.6 The Lemke–Howson Algorithm

This algorithm is applicable to the two-player game. Player 1 has   actions and player 2 has   actions. We label the actions of player 1 as   and the actions of player 2 as  . The payoff for the players is given by the usual payoff matrix. We have two payoff matrices, matrix   and matrix   for player 1 and player 2, respectively. If there is a mixed strategy, given by the action profile  , then the payoff for player 1 is   and the payoff for player 2 is  . The support of a vector is defined as   and represents the indices of elements of the vector that are nonzero. The term   denotes all possible mixed strategies for agent 1, and   denotes all possible mixed strategies for agent 2. We assume that   and   have all positive elements and that neither   nor   have all zero rows or columns. Let   denote the column of   corresponding to action  , and let   denote the row of   corresponding to action  . Define the two polytopes

**4.47**

and

**4.48**

The strategy is given by  . The inequalities that define   have the following meaning:

  * if   meets   with equality, for example,  , then   is not in the support of  ;
  * if   meets   with equality, then   is the best response to  .

The solution techniques to find the Nash equilibrium of general-sum games are the _Lemke–Howson algorithm_ and its extensions. For completeness, we will present the Lemke–Howson algorithm. Furthermore, these algorithms are based on methods from linear programming such as the simplex method. The Lemke–Howson algorithm is the central algorithm of the Nash Q-learning algorithm even though theseminal paper by Hu and Wellman [8] only cite the algorithm in passing.

The Lemke–Howson algorithm resembles the simplex algorithm. This algorithm is used for two-player bimatrix games. The Nash Q-learning algorithm uses this algorithm on each iteration to solve for the Nash equilibrium of the two-player game. In particular, Hu and Wellman [8] use this algorithm for their examples. Let player 1 have   actions given by the set  , and player 2   actions given by the set  . We represent the payoff matrix for the players as an   matrix. We define the payoff matrix for player 1 with the matrix   and that for player 2 as the matrix  . We think of player 1 as choosing actions that are represented by rows, and player 2 as choosing the columns. We define an  -dimensional row vector   that represents the probabilities of player 1 choosing each of the possible actions. The elements of the row vector   will sum to 1. Similarly, we define an  -dimensional column vector to represent the probabilities of player 2 choosing each action. Therefore,   is the mixed strategy for player 1, and   is a column vector representing the mixed strategy for player 2. The expected reward for player 1 can then be written as

**4.49**

and the expected reward for player 2 can be written as

**4.50**

Similar to the simplex method, we define the support of any strategy as those actions that do not have zero entries in   or  . We assume that matrix   has no all-zero columns and that   has no all-zero rows and that the entries of   and   are all nonnegative. Let   denote a column of  , and   denote a row of  . Then we define the two polytopes as follows:

**4.51**

**4.52**

The inequalities described in the polytopes defined above have the following meanings: If  , then   is not in the support or basis of  . Recall this language from the description in the simplex method. The second equality constraint is  . This means that player 2's action   is the best response to strategy   of player 1. If the sum of the elements in column   is greater than 1, then the sum of the elements of   will be less than 1, and to get the strategy we will need to normalize   as

**4.53**

Let us define labels as follows: A strategy   has label   if either   and   or   and  . We then can state the following theorem:

* * *

### Theorem 4.2

Suppose that   and   and neither   nor   is the all-zero vector. Then,   and   together have all labels from 1 to  , iff   is a Nash equilibrium.

* * *

We give a simple example to illustrate how the Lemke–Howson algorithm is implemented. Let us take the case of a two-player two-action game, where the reward matrices have the following values:

**4.54**

The polytopes   and   are defined by the limits of the constraints   and  , and both   and   as illustrated in Figs. 4.8 and 4.9. We will convert these inequalities into equality constrains by adding slack variables as we did in the simplex method. Define the slack variable   as

**4.55**

Similarly

**4.56**

Then, similar to the simplex method, we write   as

Similarly, the   constraint   becomes

We can now draw out the constraint conditions as illustrated in Fig. 4-8. Taking the slack variables as being equal to zero,  . The equality constraints for the   polytope become

Similarly, for the   polytope we have the constraints

**Figure 4-8** Polytope defined by  .

**Figure 4-9** Polytope defined by  .

We will start by arbitrarily allowing   into the basis. Then the constraint B1 limits the growth of   to  , as seen in Figs. 4.8. Along the B1 constraint, the slack variable   is zero. Then, from the complementary condition  , we bring   into the basis. From Eq. B1 we solve for   as

where   and  . Substituting for   into constraint Eq. B2, we get

This is what just happened: we arbitrarily let agent 1 choose action 1 and found that condition B1 was satisfied first when  , at   and  . This means that the best response by agent 2 to agent 1 choosing action 1 is for agent 2 to take action 3, which represents the first column of the payoff function given by matrix  . This is obvious because, if agent 1 picks action 1, then agent 2 should pick action 3, which is the first column of the   matrix and then agent 2 receives a reward of 3. If agent 2 chooses action 4, then its reward would be only 2. Given that agent 1 chooses action 1, this means that agent 2 chooses action 3, and this is equivalent to having   enter the basis. The limiting condition on   is given by the constraint A2. We then solve for   because of constraint A2 as

We then compute   as

Therefore, the best response to agent 2 taking action 3 is for agent 1 to take action 2 because  . We then pivot along the   line in the   polytope. We then add   to the basis because we have  , and solve for   from Eq. B2' as

Then we choose to take   into the basis because  , and it is clear that the best response to agent 1 taking action 2 is for agent 2 to take action 4 and get a reward of 4. We then solve for   from Eq. A2′ and get

Then  , and   would enter the basis, but it is already in the basis so the algorithm ends. We now normalize the game strategy. The current solution is given by  ,  ,  , and  . We then normalize the strategy as

Now let us check if this works. Given that   and  , the payoff to agent 1 is

We can also write this in the form before normalization, in which case we get the constraint condition as

which satisfies the constraint condition. We can also check the payoff for agent 2.

and once again we can verify the constraint conditions as

Recall the conditions   and  . This says that if agent 2 plays its best policy, and if agent 1 plays any policy, it does no better than the optimal policy  , and similarly for agent 2. Therefore, we now show that we cannot find any   that will make   greater than the optimal policy selection. We know that the optimal payoff for agent 1 is given by  . Can we find a policy   such that  ? We have

**4.57**

Similarly, for agent 2 we have  , but we know that   and that  . Therefore, if agent 2 picks its optimal policy  , then agent 1 will always get the payoff 4.5, regardless of what strategy it uses; similarly, if agent 1 picks its optimal strategy  , then agent 2 gets its optimal payoff off 2.5 regardless of what strategy it picks. We now see the importance of setting the constraint conditions for agent 1 to ensure that   and for agent 2  . Then for condition  , this means that the payoff to agent 2 is limited by the strategy of agent 1, and similarly the condition   means that the payoff to agent 1 is limited by the strategy of agent 2, yielding the maximum payoff for each constrained by the other.

## 4.7 Nash-Q Implementation

Our goal with the Nash-Q algorithm is to reproduce the results obtained by Hu and Wellman. The results were very conclusive in grid games 1 and 2. We wanted to recreate the situation when both agents were Nash-Q learners. Hu and Wellman's observations showed that both agents learned a Nash equilibrium strategy 100% of the time. The high percentage is a very good indicator that the algorithm works very well in that particular situation.

The Lemke–Howson algorithm was used to find the Nash equilibrium of bimatrix games. We used the original version from Hu and Wellman and adapted it for our environment in MATLAB. The algorithm is designed to find more than one Nash equilibrium when they exist. It is based on the work from Reference [14]. The inputs are the two payoff matrices for both players, and the outputs are the Nash equilibria. In our multiple implementations, we kept the parameters from Reference [8]. The author had their agents play for 5000 games. The number of games necessary to reach convergence is affected by the variation of the learning rate  . Where   is inversely proportional to the number of times each state tuples   are visited. We considered 5000 a reasonable number of games because after some testing we calculated that each state would be visited on average 93 times.

We started the implementation with a more general approach to the learning technique than in Reference [8]. In our first implementation, our agents were always able to choose any of the four actions. This meant that if the agent chooses to go into a wall, it would be bounced back and would receive either a negative reward or no reward. Also, our Lemke–Howson algorithm would use the Nash  -values of all four actions for each state. It meant that the algorithm was calculating more than it needed. The results obtained were not conclusive. In our second implementation, we changed the code so that the agents would not be able to choose an action that would lead out of bounds. The fact that Nash-Q is an offline learner helped us to create the boundaries when choosing randomly the next step. This change positively affected the results, and we got a success rate of about 25%. This was still far from the success rate noted in the literature. In our last implementation, the Lemke–Howson algorithm was used only on the possible actions. This means that the agent would calculate the Nash equilibrium strategy of the next state with only the actions that are allowed in that state. We were able to achieve 100% success in getting a Nash equilibrium strategy for two Nash-Q learners. Table 4.6 shows the value of the Nash  -values in the starting state (1,3).

**Table 4.6** Grid game 1. Nash  -values in state (1,3).

| Up | Left  
---|---|---  
Up | 96,95 | 92,92  
Right | 85,85 | 89,85

We decided to use the same method of Hu and Wellman to confirm their results. This means that the agent will choose a random action in every state. The starting positions of the players change in every game. They start in a random position except for their goal cell. This ensures that each state is visited often enough. According to Reference [8], the learning rate depends on the number of times each state-action tuple has been visited. The value of   is  , where   is the number of times the game was in the state-action tuple   [8]. This allows the learning rate to decay until the state-action tuple is visited often enough. We found that if we remove the states where both players occupied the same cell, the states where one or both of the players are in their goal cell, and the inaccessible actions (the players cannot try to move into the wall), we would get 424 different state-action tuples of the form   [8]. The learning rate would be negligible after 500 visits with a value of  .

We also implemented an online version of the algorithm. In this version, the agents start each episode from the state  , which is the original starting position. The main difference is that the agent now uses an exploit-explore learning technique where the agent choose a random action with a probability of   and the Nash equilibrium strategy with a probability of  . The value of   varies during learning as  , where   is the number of times the game was in the state   [8]. This means that the chance that the agent will choose a random action increases with time. This is not desirable for an online learning agent, because it would cause the average reward to decrease with time. It is necessary for the Nash-Q agent to visit as many different states as possible to ensure convergence to a Nash equilibrium strategy.

Our final results correspond perfectly with those in the literature when looking at two Nash-Q learners playing grid games 1 and 2. We tested each grid game 20 times, and the agents found the Nash equilibrium strategy 100% of the time. We also kept track of the performance of each agent. The performance was calculated by the average reward per step the agent was able to accumulate. The performance of an agent is important because it tells us how well the agent can optimize their policy. To ensure that the values reflect not only the results of one game, we took the average of the value over five games. It also gave us a smoother curve on the graphs which made it easier to read. In Figs. 4.10–4.12, we illustrate the performance of the algorithm in grid game 1 when both agents are Nash-Q learners. It shows the average rewards per step when the two agents use the three learning technique: exploit-explore, explore only, and exploit only.

**Figure 4-10** Nash-Q learner with exploit-explore. Reproduced from [15], © P. De Beck-Courcelle.

Figure 4-11 Nash-Q learner with explore only. Reproduced from [15], © P. De Beck-Courcelle.

**Figure 4-12** Nash-Q learning with exploit only. Reproduced from [15], © P. De Beck-Courcelle.

The Nash-Q algorithm converges to a Nash equilibrium strategy only when all the assumptions and conditions are met. The algorithm is also very demanding on computation time. Its needs to keep track of all the players' actions and rewards in a separate  -table. It also needs to evaluate the Nash equilibrium at every step to update its  -values. The Lemke–Howson algorithm is equivalent to the simplex algorithm in terms of computation. Both these actions require a large amount of processing power and consume a lot of time.

## 4.8 Friend-or-Foe Q-Learning

For a two-player zero-sum stochastic game, the minimax-Q algorithm [1] is well suited for the players to learn a Nash equilibrium in the game. For general-sum stochastic games, Littman proposed a friend-or-foe Q-learning (FFQ) algorithm such that a learner is told to treat the other players as either a "friend" or a "foe" [10]. The FFQ algorithm assumes that the players in a general-sum stochastic game can be grouped into two types: player  's friends and player  's foes. Player  's friends are assumed to work together to maximize player  's value, while player  's foes work together to minimize the value [10]. Thus, an  -player general-sum stochastic game can be treated as a two-player zero-sum game with an extended action set [10].

The FFQ algorithm for player   is given in Algorithm 4.3. Note that the FFQ algorithm is different from the minimax-Q algorithm for a two-team zero-sum stochastic game. In a two-team zero-sum stochastic game, a team leader controls the team players' actions and maintains the value of the state for the whole team. The received reward is also the whole team's reward. For the FFQ algorithm, there is no team leader to send commands to control the team players' actions. The FFQ player chooses its own action and maintains its own state-value function and equilibrium strategy. In order to update the action-value function  , the FFQ player needs to observe its friends and opponents' actions at each time step.

Littman's FFQ algorithm can guarantee the convergence to a Nash equilibrium if all states and actions are visited infinitely often. The proof of convergence for the FFQ algorithm can be found in Reference [10]. Similar to the minimax Q- and Nash Q-learning algorithms, the learning speed is low because of the execution of linear programming at each iteration in Algorithm 4.3.

## 4.9 Infinite Gradient Ascent

It is known in the game theory literature that the strategies need not converge when they are computed by the gradient ascent in two-person iterated games. Singh et al. proved that the average payoffs of two players will always converge to the expected payoffs of some Nash equilibrium even if their strategies do not converge. Let a two-player two-action general-sum game be defined by the following matrices:

where _R_ is the payoffs of the row player (player 1) and _C_ is the payoffs of the column player (player 2). Assume that player 1 plays action _i_ and player 2 plays action _j_. Thus, the payoffs that player 1 and player 2 get are   and  , respectively.

Player 1 and player 2 are said to follow a mixed strategy as they can choose their actions stochastically. Let us assume that     [0,1] is the probability of player 1 to choose action 1 and   is the probability of player 1 to choose action 2. Let us also assume that     [0,1] is the probability of player 2 to choose action 1 and   is the probability of player 2 to choose action 2. Thus, player 1's expected payoff to the strategy pair   is

**4.59**

and player 2's expected payoff to the strategy pair   is

**4.60**

The effect of changing a player's strategy is estimated by calculating the partial derivative of its expected payoff with respect to its mixed strategy as follows:

**4.61**

**4.62**

where   and  .

In the gradient ascent algorithm, at each time step the current strategy of each player is adjusted in the direction of its current gradient with some step size   so as to maximize its expected payoff:

**4.63**

**4.64**

The step size   is usually in the range  . It is clear that each player assumes that the opponent's strategy is known. Singh et al. proved that the agents, their average payoffs, or both of them will converge to a Nash equilibrium in case of the infinitesimal step size  . However, the IGA (infinite gradient ascent) algorithm is not practical because it cannot be applied to a large number of real problems because of the following two reasons:

  1. The opponent's strategy is assumed to be totally known by the player;
  2. The IGA algorithm is designed for two-player two-action iterated general-sum games; for many-player many-action general-sum games, the extension will not be straightforward.

## 4.10 Policy Hill Climbing

Policy hill climbing (PHC) is a simple practical algorithm that can play mixed strategies. This algorithm was first proposed by Bowling and Veloso (2002). The PHC does not require much information as neither the player's recently executed actions nor its opponent's current strategy is required to be known. The PHC is a simple modification of the single-agent Q-learning algorithm. A hill climbing is performed by the PHC algorithm in the space of the mixed strategies. The PHC algorithm is composed of two parts. The reinforcement learning is the first part, as the Q-learning algorithm maintains the values of the particular actions in the states. The game-theoretic part is the second part in which the current strategy in each system's state is maintained.

The probability that selects the highest valued actions is increased by a small learning rate     (0,1] so that the policy is improved. The algorithm is equivalent to Q-learning when  , as the policy moves to the greedy policy with probability 1 while executing the highest valued action. The PHC algorithm is rational and converges to the optimal solution when a fixed (stationary) strategy is followed by the other players. However, the PHC algorithm may not converge to a stationary policy if the other players are learning although its average reward will converge to the reward of a Nash equilibrium. The PHC algorithm is illustrated in Algorithm 4.4.

## 4.11 WoLF-PHC Algorithm

The WoLF-PHC (win-or-learn-fast policy hill climbing) algorithm is an extension of the PHC algorithm [2]. This algorithm uses the mechanism of WoLF so that the PHC algorithm converges to a Nash equilibrium in self-play. The algorithm has two different learning rates:   when the algorithm is winning, and   when it is losing. The difference between the average strategy and the current strategy is used as a criterion to decide when the algorithm wins or loses. The learning rate   is larger than the learning rate  . As such, when an agent is losing, it learns faster than when it is winning. This causes the agent to adapt quickly to the changes in the strategies of the other agents when it is doing more poorly than expected, and learns cautiously when it is doing better than expected. This also gives the other agents the time to adapt to the agent's strategy changes. The WoLF-PHC algorithm exhibits the property of convergence as it makes the agent converge to one of its Nash equilibria. This algorithm is also a rational learning algorithm as it makes the agent converge to its optimal strategy when its opponent plays a stationary strategy. These properties permit the WoLF-PHC algorithm to be widely applied to a variety of stochastic games [2, 16–18]. The recursive Q-learning of a learning agent   is given as

**4.69**

Algorithm 4.5 describes the WoLF-PHC algorithm for a learning agent  , and the algorithm updates the strategy of agent   by the following equation:

**4.70**

where

The WoLF-PHC algorithm for player   is provided in Algorithm 4.5.

Different from the previously mentioned learning algorithms, the WoLF-PHC algorithm does not need to observe the other players' strategies and actions. Therefore, compared to the other three learning algorithms, the WoLF-PHC algorithm needs less information from the environment. Since the WoLF-PHC algorithm is based on the PHC method, neither linear programming nor quadratic programming is required in this algorithm. Since the WoLF-PHC algorithm is a practical algorithm, there was no proof of convergence provided in Reference [2]. Instead, simulation results in Reference [2] illustrated the convergence of players' strategies by carefully choosing the learning rate according to different examples in matrix games and stochastic games.

## 4.12 Guarding a Territory Problem in a Grid World

The game of guarding a territory was first introduced by Isaacs [3]. In the game, the invader tries to move to the territory as close as possible while the defender tries to intercept and keep the invader away from the territory as far as possible. The practical application of this game can be found in surveillance and security missions for autonomous mobile robots. There are a few published works in this field since the game was introduced [19, 20]. In these works, the defender tries to use a fuzzy controller to locate the invader's position [19] or applies a fuzzy reasoning strategy to capture the invader [20]. However, all these works assume that the defender knows its optimal policy and the invader's policy. There is no learning technique applied to the players in their works. In our work, we assume that the defender or the invader has no prior knowledge of his optimal policy and the opponent's policy. We apply learning algorithms to the players and let the defender or the invader obtain its own optimal behavior after learning.

The problem of guarding a territory in Reference [3] is a differential game problem where the dynamic equations of the players are typically differential equations. In our work, we will investigate how the players learn to behave with no knowledge of the optimal strategies. Therefore, the above problem becomes a multiagent learning problem in a multiagent system. In the literature, there are a number of papers on multiagent systems [21, 22]. Among the multiagent learning applications, the predator–prey or the pursuit problem in a grid world has been well studied [22, 23]. To better understand the learning process of the two players in the game, we create a grid game of guarding a territory, which has not been studied so far.

Most multiagent learning algorithms are based on MARL methods [22]. According to the definition of the game in Reference [3], the grid game we established is a two-player zero-sum stochastic game. The minimax-Q algorithm [1] is well suited to solve our problem. However, if the player does not always take the action that is most damaging to the opponent, the opponent might have better performance using a rational learning algorithm than the minimax-Q [21]. The rational learning algorithm we use here is the WoLF-PHC learning algorithm. In this section, we run simulations and compare the learning performance of the minimax-Q and WoLF-PHC algorithms.

The problem of guarding a territory in this section is the grid version of the guarding a territory game in Reference [3]. The game is defined as follows:

  * We take a   grid as the playing field, as shown in Fig. 4-13. The invader starts from the upper-left corner and tries to reach the territory before the capture. The territory is represented by a cell named T in Fig. 4-13. The defender starts from the bottom and tries to intercept the invader. The initial positions of the players are not fixed and can be chosen randomly.
  * Both players can move up, down, left, or right. At each time step, both players take their actions simultaneously and move to their adjacent cells. If the chosen action will take the player off the playing field, the player will stay at the current position.
  * The nine gray cells centered around the defender, shown in Fig. 4-13b, is the region where the invader will be captured. A successful invasion by the invader is defined as the situation where the invader reaches the territory before the capture or the capture happens at the territory. The game ends when the defender captures the invader or a successful invasion by the invader happens. Then the game restarts with random initial positions of the players.
  * The goal of the invader is to reach the territory without interception, or move to the territory as close as possible if the capture must happen. On the contrary, the aim of the defender is to intercept the invader at a location as far away as possible from the territory.

**Figure 4-13** Guarding a territory in a grid world. (a) Initial positions of the players when the game starts. (b) Terminal positions of the players when the game ends. Reproduced from [5], © X. Lu.

The terminal time is defined as the time when the invader reaches the territory or is intercepted by the defender. We define the payoff as the distance between the invader and the territory at the terminal time.

**4.77**

where   is the invader's position at the terminal time   and   is the territory's position. Based on the definition of the game, the invader tries to minimize the payoff while the defender tries to maximize the payoff.

### 4.12.1 Simulation and Results

We use the minimax-Q and WoLF-PHC algorithms introduced in Sections 4.3 and 4.11 to simulate the grid game of guarding a territory. We first present a simple   grid game to explore the issues of mixed strategy, rationality, and convergence. Next, we enlarge the playing field to a   grid and examine the performance of the learning algorithms based on this large grid.

We set up two simulations for each grid game. In the first simulation, the players in the game use the same learning algorithm to play against each other. We examine whether the algorithm satisfies the convergence property Fig. 4-14. In the second simulation, we will freeze one player's strategy and let the other player learn the optimal strategy against its opponent. We use the minimax-Q and WoLF-PHC algorithms to train the learner individually and compare the performance of the minimax-Q-trained player and the WoLF-PHC-trained player. According to the rationality property shown in Table 4.7, we expect the WoLF-PHC-trained defender has better performance than the minimax-Q-trained defender in the second simulation.

**Figure 4-14** Players' strategies at state   using the minimax-Q algorithm in the first simulation for the   grid game. (a) Defender's strategy   (solid line) and   (dash line). (b) Invader's strategy   (solid line) and   (dash line). Reproduced from [5], © X. Lu.

**Table 4.7** Comparison of multiagent reinforcement learning algorithms.

Algorithms | Applicability | Rationality | Convergence  
---|---|---|---  
Minimax-Q | Zero-sum SGs | No | Yes  
Nash-Q learning | Specific general-sum SGs | No | Yes  
Friend-or-foe Q learning | Specific general-sum SGs | No | Yes  
WoLF-PHC | General-sum SGs | Yes | No

We now apply the WoLF-PHC algorithm to the   grid game. According to the parameter settings in Reference [2], we set the learning rate   as  ,   as  , and   as  , where   is the number of the current iteration. The number of iterations denotes the number of times the step   is repeated in Algorithm 4.5. The result in Fig. 4-15 shows that the players' strategies converge close to the Nash equilibrium after 15,000 iterations.

**Figure 4-15** Players' strategies at state   using the WoLF-PHC algorithm in the first simulation for the   grid game. (a) Defender's strategy   (solid line) and   (dash line). (b) Invader's strategy   (solid line) and   (dash line). Reproduced from [5], © X. Lu.

In the second simulation, the invader plays a stationary strategy against the defender at state  , as shown in Fig. 4-2a. The invader's fixed strategy is to move right with probability 0.8 and move down with probability 0.2. Then the optimal strategy for the defender against this invader is to move up all the time. We apply both algorithms to the game and examine the learning performance for the defender. Figure 4-16a shows that, using the minimax-Q algorithm, the defender's strategy fails to converge to its optimal strategy, whereas Fig. 4-16b shows that the WoLF-PHC algorithm guarantees the convergence to the defender's optimal strategy against the invader.

**Figure 4-16** Defender's strategy at state   in the second simulation for the   grid game. (a) Minimax-Q-learned strategy of the defender at state   against the invader using a fixed strategy. Solid line: probability of defender moving up; Dashed line: probability of defender moving left. (b) WoLF-PHC learned strategy of the defender at state   against the invader using a fixed strategy. Solid line: probability of defender moving up; Dashed line: probability of defender moving left. Reproduced from [5], © X. Lu.

In the   grid game, the first simulation verified the convergence property of the minimax-Q and WoLF-PHC algorithms. According to Table 4.7, there is no proof of convergence for the WoLF-PHC algorithm. But simulation result in Fig. 4-15 shows that the players' strategies converged to the Nash equilibrium when both players used the WoLF-PHC algorithm. Under the rationality criterion, the minimax-Q algorithm failed to converge to the defender's optimal strategy in Fig. 4-16a, while the WoLF-PHC algorithm showed the convergence to the defender's optimal strategy after learning.

We now change the   grid game to a   grid game. The territory to be guarded is represented by a cell located at   in Fig. 4-17. The position of the territory will not be changed during the simulation. The initial positions of the invader and defender are shown in Fig. 4-17a. The number of actions for each player has been changed from 2 in the   grid game to 4 in the   grid game. Both players can move up, down, left, or right. The gray cells in Fig. 4-17a is the area where the defender can reach before the invader. Therefore, if both players play their equilibrium strategies, the invader can move to the territory as close as possible with the distance of two cells shown in Fig. 4-17b. Different from the previous   grid game where we showed the convergence of the players' strategies during the learning, in this game we want to show the average leaning performance of the players during the learning. We add a testing phase to evaluate the learned strategies after every 100 iterations. The number of iterations denotes the number of times step   is repeated in Algorithms 4.1 or 4.5. A testing phase includes 1000 runs of the game. In each run, the learned players start from their initial positions shown in Fig. 4-17a and end at the terminal time. For each run, we find the final distance between the invader and the territory at the terminal time. Then we calculate the average of the final distance over 1000 runs. The result of a testing phase, which is the average final distance over 1000 runs, is collected after every 100 iterations.

**Figure 4-17** A   grid game. (a) Initial positions of the players. (b) One of the terminal positions of the players. Reproduced from [5], © X. Lu.

We use the same parameter settings as in the   grid game for the minimax-Q algorithm. In the first simulation, we test the convergence property by using the same learning algorithm for both players. Figure 4-18a shows the learning performance when both players used the minimax-Q algorithm. In Fig. 4-18a, the  -axis denotes the number of iterations and the  -axis denotes the result of the testing phase (the average of the final distance over 1000 runs) for every 100 iterations. From the result in Fig. 4-18a, the average final distance between the invader and the territory converges to 2 after 50,000 iterations. As shown in Fig. 4-17b, distance   is the final distance between the invader and the territory when both players play their Nash equilibrium strategies. Therefore, Fig. 4-18a indicates that both players' learned strategies converge close to their Nash equilibrium strategies. Then we use the WoLF-PHC algorithm to simulate again. We set the learning rate   as  ,   as  , and   as  . We run simulation for 200,000 iterations. The result in Fig. 4-18b shows that the average final distance converges close to the distance of 2 after the learning.

**Figure 4-18** Results in the first simulation for the   grid game. (a) Result of the minimax-Q learned strategy of the defender against the minimax-Q-learned strategy of the invader. (b) Result of the WoLF-PHC learned strategy of the defender against the WoLF-PHC-learned strategy of the invader. Reproduced from [5], © X. Lu.

In the second simulation, we fix the invader's strategy to a random-walk strategy, which means that the invader can move up, down, left, or right with equal probability. Similar to the first simulation, the learning performance of the algorithms is tested on the basis of the result of a testing phase after every 100 iterations. In the testing phase, we play the game 1000 times and average the final distance between the invader and the territory at the terminal time for each run over 1000 runs.

We test the learning performance of both algorithms for the defender in the game and compare them. The results are shown in Fig. 4-19a and b. Using the WoLF-PHC algorithm, the defender can intercept the invader further away from the territory (distance of 6.6) than using the minimax-Q algorithm (distance of 5.9). Therefore, on the basis of the rationality criterion in Table 4.7, the WoLF-PHC-learned defender can achieve better performance than the minimax-Q-learned defender when playing against a random-walk invader.

**Figure 4-19** Results in the second simulation for the   grid game. (a) Result of the minimax-Q-learned strategy of the defender against the invader using a fixed strategy. (b) Result of the WoLF-PHC-learned strategy of the defender against the invader using a fixed strategy. Reproduced from [5], © X. Lu.

## 4.13 Extension of   Lagging Anchor Algorithm to Stochastic Games

The proposed   lagging anchor algorithm is designed on the basis of matrix games. In this section, we extend the algorithm to the more general stochastic games. Inspired by the WoLF-PHC algorithm in Reference [2], we design a practical decentralized learning algorithm for stochastic games based on the   lagging anchor approach in (3.59). The practical algorithm is shown in Algorithm 4.6.

We now apply Algorithm 4.6 to a stochastic game to test its performance. The stochastic game we simulate is a general-sum grid game introduced by Hu and Wellman [8] and that we have already reviewed in section 4.4. Recall that. The game runs under a   grid field as shown in Fig. 4-20a. We have two players whose initial positions are located at the bottom left corner for player   and the bottom right corner for player  . Both players try to reach the goal denoted as "G" in Fig. 4-20a. Each player has four possible moves which are moving up, down, left, or right unless the player is on the sides of the grid. In Hu and Wellman's game, the movement that will take the player to a wall is ignored. Since we use exactly the same game as Hu and Wellman, the possible actions of hitting a wall have been removed from the players' action sets. For example, if the player is at the bottom-left corner, its available moves are moving up or right. If both players move to the same cell at

**Figure 4-20** Hu and Wellman's grid game. (a) Grid game. (b) Nash equilibrium path 1. (c) Nash equilibrium path 2. Reproduced from [24] © M. Awheda and Schwartz, H. M.

the same time, they will bounce back to their original positions. The two thick lines in Fig. 4-20a represent two barriers such that the player can pass through the barrier with a probability of 0.5. For example, if player   tries to move up from the bottom-left corner, it will stay still or move to the upper cell with a probability of 0.5. The game ends when either of the players reaches the goal. To reach the goal in the minimum number of steps, the player needs to avoid the barrier and first move to the bottom center cell. Since both players cannot move to the bottom center cell simultaneously, the players need to cooperate such that one of the players has to take the risk and move up. The reward function for player     in this game is defined as

**4.78**

According to Reference [8], this grid game has two Nash equilibrium paths as shown in Fig. 4-20b and c. Starting from the initial state, the Nash equilibrium strategies of the players are player   moving up and player   moving left, or player   moving right and player   moving up.

We set the step size as  , the learning rate as  , and the discount factor as  . The mixed exploration-exploitation strategy is chosen such that the player chooses a random action with probability   and the greedy action with probability  . We run the simulation for 10,000 episodes. An episode is when the game starts with the players' initial positions and ends when either of the players reaches the goal. Figure 4-21 shows the result of two players' learning trajectories. We define   as player  's probability of moving up and   as player  's probability of moving up from their initial positions. The result in Fig. 4-21 shows that the two players' strategies at the initial state converge to one of the two Nash equilibrium strategies (player   moving right and player   moving up). Therefore, the proposed practical   lagging anchor algorithm may be applicable to general-sum stochastic games.

**Figure 4-21** Learning trajectories of players' strategies at the initial state in the grid game. Reproduced from [5] © X. Lu.

## 4.14 The Exponential Moving-Average Q-Learning (EMA Q-Learning) Algorithm

The exponential moving-average (EMA) approach is a model-free strategy estimation approach. It is a family of statistical approaches used to analyze time series data in finance and technical analysis. Typically, EMA gives the recent observations more weight than the older ones [25]. The EMA estimation approach is used in Reference [26] by the hyper Q-learning algorithm to estimate the opponent's strategy. It is also used in Reference [25] by the IGA agent to estimate its opponent's strategy. The EMA estimator used to estimate the strategy of the agent's opponent(s) can be described by the following equation [25, 26]:

**4.79**

where   is the opponent's strategy,   is a small constant step size ( ), and   is a unit vector representation of the action   chosen by the opponent ( ) at the state  . The unit vector   contains the same number of elements as  . The elements in the unit vector   are all equal to zero except for the element corresponding to the action   which is equal to 1.

In this work, we are proposing a simple algorithm that uses the EMA approach. This algorithm is called the _EMA Q-learning algorithm_. The proposed algorithm uses the EMA mechanism as a basis to update the strategy of the agent itself. Furthermore, it uses two different variable learning rates   and   when updating the agent's strategy instead of only one constant learning rate   used in References [25, 26]. The values of these variable learning rates are inversely proportional to the number of iterations. The recursive Q-learning algorithm for a learning agent   is given by the following equation:

**4.80**

The EMA Q-learning algorithm updates the strategy of the agent   by Eq. (4.81), whereas Algorithm 4.7 lists the procedure of the EMA Q-learning algorithm for a learning agent  .

**4.81**

where

  is a unit vector representation of the action   with zero elements except for the element corresponding to the action   which is equal to  . This is to make the EMA Q-learning learn fast when the chosen action of agent   is equal to the greedy action obtained from the agent's  -table. On the other hand,  . This is to make the EMA Q-learning learn cautiously and increase the opportunity of exploring the other agent's actions when the chosen action of agent   and the greedy action obtained from the agent's  -table are different.

## 4.15 Simulation and Results Comparing EMA Q-Learning to Other Methods

We have evaluated the EMA Q-learning, WoLF-PHC [2], GIGA-WoLF [27], weighted policy learning (WPL) [28], and policy gradient ascent with approximate policy prediction (PGA-APP) [29] algorithms on a variety of matrix and stochastic games. We only show the EMA Q-learning, the PGA-APP, and the WPL algorithms. The results of applying the WPL, PGA-APP, and EMA Q-learning algorithms to different matrix and stochastic games are presented in this section. A comparison among the three algorithms in terms of the convergence to Nash equilibrium is provided. We use the same learning and exploration rates for all algorithms when they are applied to the same game. In some cases, these rates are chosen to be close to those used in Reference [29]. In other cases, the values of these rates are chosen on a trial-and-error basis to achieve the best performance of all algorithms.

### 4.15.1 Matrix Games

We revisit matrix games to illustrate the improved performance of the EMA Q-learning algorithm. The EMA Q-learning, PGA-APP, and WPL algorithms are applied to the matrix games. They are also applied to the three-player matching pennies game. Figure 4-22 shows the probability distributions of the second actions for both players in the dilemma game. The EMA Q-learning, PGA-APP, and WPL algorithms are shown. In this game, the parameters of the EMA Q-learning algorithm are set as follows:  ,  ,  ,  , and   with an exploration rate  . The parameter   is set as   in the PGA-APP algorithm and the learning rate   is decayed with a slower rate in the WPL algorithm and is set as  . Figure 4-23 shows the probability distributions of the first actions for the three players in the three-player matching pennies game while learning with the EMA Q-learning, PGA-APP, and WPL algorithms. In this game, the

**Figure 4-22** Probability distributions of the second actions for both players in the dilemma game. (a) The EMA Q-learning, (b) PGA-APP, and (c) WPL algorithms are shown. Reproduced from [24] © M. Awheda and Schwartz, H. M.

**Figure 4-23** Probability distributions of the first actions for the three players in the three-player matching pennies game. (a) The EMA Q-learning, (b) PGA-APP, and (c) WPL algorithms are shown. Reproduced from [24] © M. Awheda and Schwartz, H. M.

parameters of the EMA Q-learning algorithm are set as follows:  ,  ,  ,  , and   with an exploration rate  . The value of   is set to   in the PGA-APP algorithm and the learning rate   is decayed slowly in the WPL algorithm and is set as   as  . Figure 4-24 shows the probability distributions of player 1's actions in the Shapley's game while learning with the EMA Q-learning, PGA-APP, and WPL algorithms. In this game, the parameters of the EMA Q-learning algorithm are set as follows:  ,  ,  ,  , and   with an exploration rate  . The learning rate   and the parameter   in the PGA-APP algorithm are set as follows:   and  . On the other hand, in the WPL algorithm, thelearning rate   is decayed slowly and is set as  . Figure 4-25 shows the probability distributions of the first actions for both players in the biased game while learning with the EMA Q-learning, PGA-APP, and WPL algorithms. In this game, the parameters of the EMA Q-learning algorithm are set as follows:  ,  ,  ,  , and   with an exploration rate  . In the PGA-APP algorithm, the values of   and   are set as follows:   and  . In the WPL algorithm, the parameter   is set as   and the learning rate   is decayed with a slower rate and is set as  . As shown in Figs. 4.22–4.24, the players' strategies successfully converge to Nash equilibria in all games when learning with the EMA Q-learning, PGA-APP, and WPL algorithms. It is important to mention here that the WPL algorithm successfully converges to Nash equilibrium in the three-player matching pennies game although it was presented to diverge in this game in Reference [29]. On the other hand, Fig. 4-26 shows that both PGA-APP and WPL algorithms fail to converge to a Nash equilibrium in the biased game; only the EMA Q-learning algorithm succeeds to converge to a Nash equilibrium in the biased game.

**Figure 4-24** Probability distributions of player 1's actions in the Shapley's game. (a) The EMA Q-learning, (b) PGA-APP, and (c) WPL algorithms are shown. Reproduced from [24] © M. Awheda and Schwartz, H. M.

**Figure 4-25** Probability distributions of the first actions for both players in the biased game. (a) The EMA Q-learning, (b) PGA-APP, and (c) WPL algorithms are shown. Reproduced from [24] © M. Awheda and Schwartz, H. M.

**Figure 4-26** Grid game 1. (a) Probability of action North of player 1 when learning with the EMA Q-learning algorithm with different values of the constant gain  . Plots (b) and (c) illustrate the probability of action North of player 1 and player 2, respectively, when learning with the EMA Q-learning, PGA-APP, and WPL algorithms. Reproduced from [24] © M. Awheda and Schwartz, H. M.

### 4.15.2 Stochastic Games

It is important to mention here that we are only concerned about the first movement of both players from the initial state. Therefore, the figures that will be shown in this section will represent the probabilities of players' actions at the initial state.

#### 4.15.2.1 Grid Game 1

The EMA Q-learning, PGA-APP, and WPL algorithms are used to learn grid game 1 depicted again in Fig. 4-27a. Grid game 1 has 10 different Nash equilibria [8]. One of these Nash equilibria is shown in Fig. 4-28a. Figure 4-28a

**Figure 4-27** Two stochastic games [8]. (a) Grid game 1. (b) Grid game 2. Reproduced from [24] © M. Awheda and Schwartz, H. M.

**Figure 4-28** (a) Nash equilibrium of grid game 1. (b) Nash equilibrium of grid game 2 [8] with permission from MIT press. Reproduced from [24] © M. Awheda and Schwartz, H. M.

shows that the action North is the optimal action for both players when they are at the initial state. The learning and exploration rates used by all algorithms are the same. The parameters of the EMA Q-learning algorithm are set as follows:  ,  ,  ,  , and   with an exploration rate  , where   is the current number of episodes. The values of the parameters of the PGA-APP algorithm are the same as those of the EMA Q-learning algorithm except that   and   has a very slow decaying rate,  . The WPL algorithm also has the same parameters as the EMA Q-learning algorithm except that the learning rate   has a very slow decaying rate of  .

Figure 4-26a shows the probability of selecting action North by player 1 at the initial state when learning with the EMA Q-learning algorithm with different values of the constant gain  . Player 2 has similar probability distributions when learning with the EMA Q-learning algorithm with different values of the constant gain  . Figure 4-26a shows that player 1's speed of convergence to the optimal action (North) increases as the value of the constant gain   increases. Figure 4-26a shows that the probability of selecting the optimal action North by player 1 requires almost 80 episodes to converge to   when  =5 and 320 episodes when  =3. However, when  , many more episodes are still required for the probability of selecting the action North to converge to  . Figure 4-26b and c shows the probabilities of taking action North at the initial state by both players when learning with the EMA Q-learning, PGA-APP, and WPL algorithms. This figure shows that the probabilities of taking action North by both players converge to the Nash equilibria (converge to  ) when learning with the EMA Q-learning algorithm. However, the PGA-APP and WPL algorithms fail to make the players' strategies converge to the Nash equilibria. Figure 4-26 shows that the EMA Q-learning algorithm outperforms the PGA-APP and WPL algorithms in terms of the convergence to Nash equilibria. It also shows that the EMA Q-learning algorithm can converge to Nash equilibria with a small number of episodes by adjusting the value of the constant gain  . This will give the EMA Q-learning algorithm an empirical advantage over the PGA-APP and WPL algorithms.

#### 4.15.2.2 Grid Game 2

The EMA Q-learning, PGA-APP, and WPL algorithms are also used to learn grid game 2 as depicted in Fig. 4-27b. Grid game 2 has two Nash equilibria [8]. Figure 4-28b shows one of these Nash equilibria. It is apparent from this particular Nash equilibrium that the action North is the optimal action for player 1 at the initial state, whereas the action West is the optimal action for player 2. Thus, for the algorithms to converge to this particular Nash equilibrium, the probability of selecting the action North by player 1 should converge to  . The probability of selecting the action West by player 2, on the other hand, should also converge to  . The learning and exploration rates used by all algorithms are the same. The parameters of the EMA Q-learning algorithm are set as follows:  ,  ,  ,  , and   with an exploration rate  , where   is the current number of episodes. The values of the parameters of the PGA-APP algorithm are the same as those of the EMA Q-learning algorithm except that  ,  , and   has a very slow decaying rate of  . The WPL algorithm also has the same parameters as the EMA Q-learning algorithm except that   and   has a very slow decaying rate of  .

Figure 4-29a shows the probability of selecting action North by player 1 when learning with the EMA Q-learning, PGA-APP, and WPL algorithms. Figure 4-29a illustrates that the probability of selecting the action North by player 1 successfully converges to   (Nash equilibrium) when player 1 learns with the EMA Q-learning algorithm. However, the PGA-APP and WPL algorithms fail to make player 1 choose action North with a probability of  . Figure 4-29b shows the probability of selecting action West by player 2 when learning with the EMA Q-learning, PGA-APP, and WPL algorithms. As can be seen from Fig. 4-29b, the probability of selecting action West by player 2 successfully converges to   (Nash equilibrium) when player 2 learns with the EMA Q-learning algorithm. The PGA-APP and WPL algorithms, on the other hand, fail to make player 2 choose action West with a probability of  . Figure 4-29 shows that the EMA Q-learning algorithm outperforms the PGA-APP and WPL algorithms in terms of the convergence to Nash equilibria. This will give the EMA Q-learning algorithm an empirical advantage over the PGA-APP and WPL algorithms.

**Figure 4-29** Grid game 2. (a) Probability of selecting action North by player 1 when learning with the EMA Q-learning, PGA-APP, and WPL algorithms. (b) Probability of selecting action West by player 2 when learning with the EMA Q-learning, PGA-APP, and WPL algorithms. Reproduced from [24] © M. Awheda and Schwartz, H. M.

## References

  1. [1] M. L. Littman, "Markov games as a framework for multi-agent reinforcement learning," in _11th International Conference on Machine Learning_ , (New Brunswick, United States), July 1994, pp. 157–163, 1994.
  2. [2] M. Bowling and M. Veloso, "Multiagent learning using a variable learning rate," _Artificial Intelligence_ , vol. **136** , no. 2, pp. 215–250, 2002.
  3. [3] R. Isaacs, _Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization_. New York, New York: John Wiley and Sons, Inc., 1965.
  4. [4] M. Bowling, Multiagent Learning in the Presence of Agents with Limitations. PhD thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, May 2003.
  5. [5] X. Lu, "On Multi-Agent Reinforcement Learning in Games," Ph.D. Thesis Carleton University, Ottawa, ON, Canada, 2012.
  6. [6] M. L. Littman and C. Szepesvári, "A generalized reinforcement-learning model: Convergence and applications," in Proceedings of the 13th International Conference on Machine Learning, (Bari, Italy), July 1996, pp. 310–318, 1996.
  7. [7] J. Hu and M. P. Wellman, "Multiagent reinforcement learning: theoretical framework and an algorithm," in Proceedings of the Fifteenth International Conference on Machine Learning (ICML 1998), Madison, Wisconsin, USA, July 24-27, 1998, pp. 242–250, 1998.
  8. [8] J. Hu and M. P. Wellman, "Nash q-learning for general-sum stochastic games," _Journal of Machine Learning Research_ , vol. **4** , pp. 1039–1069, 2003.
  9. [9] S. Abdallah, "Equilibrium in a stochastic n-person game," _Journal of Science in Hiroshima University, Series A-I,_ **28** : 89–93, 1964.
  10. [10] M. L. Littman, "Friend-or-foe q-learning in general-sum games," in Proceedings of the 18th International Conference on Machine Learning, (Williams College, MA), pp. 322–328, 2001.
  11. [11] C. Claus and C. Boutilier, "The dynamics of reinforcement learning in cooperative multiagent systems," in Proceedings of National Conference on Artificial Intelligence (AAAI-98), pp. 746–752, 1998.
  12. [12] C. E. Lemke and J. J. T. Howson, "Equilibrium points of bimatrix games," _SIAM Journal on Applied Mathematics_ , vol. **12** , no. 2, pp. 413–423, 1964.
  13. [13] D. D. Meredith, K. W. Wong, R. W. Woodhead, and R. H. Wortman, _Design and Planning of Engineering Systems_. Englewood Cliffs, New Jersey: Prentice-Hall, 1973.
  14. [14] R. W. Cottle, J.-S. Pang, and R. E. Stone, "The linear complimentary problem," _Computer Science and Scientific Computing_ , San Diego, California: Academic Press, Inc., 1992.
  15. [15] P. De Beck-Courcelle, "Study of Multiple Multiagent Reinforcement Learning Algorithms in Grid Games", Master's thesis, Carleton University, Ottawa, ON, Canada, 2013.
  16. [16] E. Yang and D. Gu, "A survey on multiagent reinforcement learning towards multi-robot systems," in _Proceedings of IEEE Symposium on Computational Intelligence and Games_ , 2005.
  17. [17] L. Bu oniu, R. Babuška, and B. D. Schutter, "Multiagent reinforcement learning: a survey," in _9th International Conference on Control, Automation, Robotics and Vision (ICARCV)_ , pp. 1–6, 2006.
  18. [18] X. Lu and H. M. Schwartz, "An investigation of guarding a territory problem in a grid world," in American Control Conference, pp. 3204–3210, 2010.
  19. [19] K. H. Hsia and J. G. Hsieh, "A first approach to fuzzy differential game problem: guarding a territory," _Fuzzy Sets and Systems_ , vol. **55** , pp. 157–167, 1993.
  20. [20] Y. S. Lee, K. H. Hsia, and J. G. Hsieh, "A strategy for a payoff-switching differential game based on fuzzy reasoning," _Fuzzy Sets and Systems_ , vol. **130** , no. 2, pp. 237–251, 2002.
  21. [21] L. Bu oniu, R. Babuška, and B. D. Schutter, "A comprehensive survey of multiagent reinforcement learning," _IEEE Transactions on Systems, Man, and Cybernetics Part C_ , vol. **38** , no. 2, pp. 156–172, 2008.
  22. [22] P. Stone and M. Veloso, "Multiagent systems: a survey from a machine learning perspective," _Autonomous Robots_ , vol. **8** , no. 3, pp. 345–383, 2000.
  23. [23] J. W. Sheppard, "Colearning in differential games," _Machine Learning_ , vol. **33** , pp. 201–233, 1998.
  24. [24] M. Awheda, and Schwartz, H.M., "Exponential Moving Average Q-Learning Algorithm", Proceedings of the IEEE Symposium Series on Computational Intelligence, Singapore, April 15–19, 2013.
  25. [25] A. Burkov and B. Chaib-draa, "Effective learning in the presence of adaptive counterparts," _Journal of Algorithms_ , vol. **64** , no. 4, pp. 127–138, 2009.
  26. [26] G. Tesauro, "Extending q-learning to general adaptive multi-agent systems," in _Advances in Neural Information Processing Systems 16_ (S. Thrun, L. K. Saul and B. Schölkopf, eds.), (Cambridge, Massachusetts), pp. 215–250, MIT Press, 2004.
  27. [27] M. Bowling, "Convergence and no-regret in multiagent learning," in _Advances in Neural Information Processing Systems 17_ (L. K. Saul, Y. Weiss and L. Bottou, eds.), (Cambridge, Massachusetts), pp. 209–216, MIT Press, 2005.
  28. [28] S. Abdallah and V. Lesser, "A multiagent reinforcement learning algorithm with non-linear dynamics," _Journal of Artificial Intelligence Research_ , vol. **33** , pp. 521–549, 2008.
  29. [29] C. Zhang and V. Lesser, "Multi-agent learning with policy prediction," in Proceedings of the 24th National Conference on Artificial Intelligence (AAAI'10), Atlanta, GA, USA, pp. 746–752, 2010.

# Chapter 5  
Differential Games

## 5.1 Introduction

In the not too distant future, teams of robots will work together to accomplish a multitude of tasks. At the time of writing this book, we have seen the extensive use of aerial drones in surveillance, mapping, and other more unsavory tasks. We are also witnessing the beginning of truly autonomous vehicles for transportation. How long will it be before cars routinely drive themselves? We are currently on the verge of having multiple autonomous vehicles working together as some type of swarm. These groups of robots or autonomous vehicles will be a combination of aerial-, land-, and sea-based vehicles. These vehicles will have different configurations and capabilities. Unlike in the previous chapters, these vehicles will not be constrained to a grid, but, instead, they will be operating in a continuous and dynamically changing environment. The actions of these vehicles will be mathematically described by differential equations. The actions that the autonomous vehicles take will essentially and ultimately be control actions. These actions may be the setting of voltages on various actuators. We will refer to these types of systems as differential games (DGs).

The goal of these types of agents is to learn how to work together and how to adapt to changes in their own or other robots' capabilities. For example, if one or more of the other robots are disabled or destroyed, the remaining autonomous vehicles would have to adapt in real time to such a situation. Furthermore, the autonomous vehicles do not initially know the capabilities of the other robots, and each vehicle has to learn how to work with others.

In this chapter, we will use two well-known games to evaluate various methods of multiagent learning in these DGs. One of the games that we will examine is the "evader–pursuer" game and the other game is the "guarding a territory" game.

Future security applications will involve robots protecting critical infrastructure [1]. The robots will work together to prevent intruders from crossing a secured area. They will have to adapt to an unpredictable and continuously changing environment. Their goal is to learn what actions to take in order to get optimum performance in security tasks. We model this application as the "guarding a territory" game. The DG of guarding a territory was first introduced by Isaacs [2]. In this game, the invader tries to get as close as possible to the territory, while the defender tries to intercept and keep the invader as far away as possible from the territory. The Isaacs' guarding a territory game is a DG where the dynamic equations of the players are differential equations. In the pursuer–evader game, the pursuer tries to capture the evader, while the evader tries to escape from capture. The practical application of this game can be found in surveillance and security missions for autonomous mobile robots.

A player in a DG needs to learn what actions to take if there is no prior knowledge of its optimal strategy. Learning in DGs has attracted attention in References [3–6]. In these articles, reinforcement learning algorithms are applied to the players in the pursuer–evader game. Early work on the guarding a territory game can be found in References [7, 8], but there is no investigation on how the players can learn their optimal strategies by playing the game. We assume the defender has no prior knowledge of its optimal strategy or the invader's strategy. We investigate how reinforcement learning algorithms can be applied to the DG of guarding a territory.

Traditional reinforcement learning algorithms such as Q-learning may lead to the curse of dimensionality problem because of the intractable, continuous state space and action space. To avoid this problem, one may use fuzzy systems to represent the continuous space [9]. Fuzzy reinforcement learning methods have been applied to the pursuer–evader DG in References [4–6]. In Reference [5], we applied a fuzzy actor–critic learning (FACL) algorithm to the pursuit evasion game.

## 5.2 A Brief Tutorial on Fuzzy Systems

Fuzzy systems have been used in a wide variety of applications in engineering, science, business, medicine, psychology, and other fields [10]. In engineering for example, some potential application areas include [10] the following:

  * Aircraft/spacecraft: flight control, engine control, avionic systems, failure diagnosis, navigation, and satellite attitude control;
  * Robotics: position control and path planning;
  * Autonomous vehicles: ground and underwater;
  * Automated highway systems: automatic steering, braking, and throttle control for vehicles.

In this chapter, we make use of fuzzy inference systems (FISs) for the control of both the robots and the critic. The critic is an FIS that approximates the continuous Q-function over the continuous state and action spaces. Therefore, we provide a short tutorial of fuzzy systems in the following section.

### 5.2.1 Fuzzy Sets and Fuzzy Rules

_Fuzzy sets_ use linguistic labels arranged by membership functions (MFs) to perform numerical computation [11]. Fuzzy set theory provides a way of dealing with information linguistically as an alternative to calculus.

The universe of discourse   is defined as a collection of elements   that have the same characteristics. A fuzzy set   in   can be denoted by Reference [11]

**5.1**

where   is the MF for the fuzzy set  . The MFs can have values between 0 and 1. The MF maps the elements of the universe of discourse to membership degrees between 0 and 1. If   has values of 0 or 1, the fuzzy set   is called a _crisp_ or a _classical_ set.

The interpretations of set operations, such as union and intersection, are complicated in fuzzy set theory because of the graded property of MFs. Zadeh [12] proposed the following definitions for union and intersection operations:

  1. **Union**  
  2. **Intersection**

where   and   are fuzzy sets.

MFs are normally described using graphics. Figure 5-1 shows various types of MFs commonly used in fuzzy set theory. The Gaussian MF, for example, in Fig. 5-1b is given as

**5.2**

where the Gaussian MF parameters are the mean   and the standard deviation  .

**Figure 5-1** Examples of membership functions.

Reproduced from [13], © B, Al Faiya.

The trapezoidal MF has four parameters, as shown in Fig. 5-1f. The trapezoidal MF is defined as

**5.3**

_Fuzzy IF-THEN rules_ can effectively model human expertise in an environment of uncertainty and imprecision [11]. Fuzzy IF-THEN rules are defined as

**5.4**

where  ,   are called _fuzzy_ or _linguistic_ variables. The sets   and   are fuzzy sets defined in  ,  . "  is  " is called the _antecedent_ or _premise_ , "  is  " is called the _consequence_ or _conclusion_.

The fuzzy IF-THEN rules used in a Takagi–Sugeno (TS) fuzzy system give a mapping from the input fuzzy sets to a linear function in the output [14, 15]. The rules have the following form:

**5.5**

where   is the output function of rule   and   is the consequent parameter.

When   is a constant, then we have a zero-order TS fuzzy model [11]. Let   be the constant for the output  . The number of rules is determined by the number of inputs and their corresponding MFs. Given two inputs and three MFs for each input, we need to construct nine ( ) rules. The rules are given as follows:

Another format for constructing the fuzzy rules is the tabular format, as shown in Table 5.1.

**Table 5.1** Tabular format.

---

### 5.2.2 Fuzzy Inference Engine

A fuzzy inference engine is used to combine fuzzy IF-THEN rules in the fuzzy rule base into a mapping from a fuzzy set   in   to a fuzzy set   in  . One of the commonly used fuzzy inference engines is called the _product inference engine_. In this section, the structure of the product inference engine is presented and explained.

We first provide the two operations on fuzzy sets: intersection and union. Assume we have two fuzzy sets   and   defined in the same universe of discourse  ; the intersection of these two fuzzy sets is a fuzzy set whose MF is

**5.6**

where   is defined as a  -norm operator. Two commonly used  -norm operators are the following:

**5.7**

**5.8**

The union of two fuzzy sets   and   is a fuzzy set whose MF is given by

**5.9**

where   is denoted as an  -norm operator. Two commonly used  -norm operators are as follows:

**5.10**

**5.11**

In the product inference engine, the algebraic product is used for all the  -norm operators and max is used for all the  -norm operators.

To interpret the IF-THEN operation, one can use Mamdani implication. In the Mamdani implication, a fuzzy IF-THEN rule can be considered as a binary fuzzy relation, given by

**5.12**

where   is used to interpret the fuzzy relation. If (5.8) is used as the  -norm operator   in (5.12), then the latter is called the _Mamdani's product implication_. In fuzzy logic, the generalized modus ponens is defined as

Based on the generalized modus ponens, the fuzzy set   is inferred as

**5.13**

where   denotes the  -norm operator and   denotes the greatest element in the set.

In the individual rule-based inference, each fuzzy IF-THEN rule generates an individual output fuzzy set, and the whole output of the fuzzy inference engine is the combination of all the individual output fuzzy sets. In the product inference engine, we combine the individual output fuzzy sets by union.

Overall, the product inference engine includes the following three parts:

  1. algebraic product for all the  -norm operators and max for all the  -norm operators;
  2. Mamdani's product implication;
  3. individual-rule-based inference with union combination.

Based on the above structure of the product inference engine, (5.13) becomes

**5.14**

We take an example here. Assume that we have two fuzzy IF-THEN rules with two antecedents for each rule such that

**5.15**

Then the output of the product inference engine for (5.15) becomes

**5.16**

### 5.2.3 Fuzzifier and Defuzzifier

Figure 5-2 shows the fuzzy system structure. The first block in the fuzzy system is the fuzzifier. The fuzzifier converts each input, which is a precise quantity, to degrees of membership in an MF [16]. The fuzzification block matches the input values with the conditions of the rules. The fuzzification determines how well the condition of each rule matches that particular input. There is a degree of membership for each linguistic term that applies to that input variable.

**Figure 5-2** Fuzzy system components.

Reproduced from [13], © B, Al Faiya.

Defuzzification is the conversion of a fuzzy quantity into a precise quantity. The weighted average defuzzification method is frequently used in fuzzy applications since it is one of the most computationally efficient methods [17]. The weighted average defuzzification method is expressed as

**5.17**

where   is number of inputs and   is number of rules.

### 5.2.4 Fuzzy Systems and Examples

Fuzzy systems are also known as _FISs_ , or _fuzzy controllers_ when used as controllers. TS fuzzy systems and Mamdani fuzzy systems are commonly used in fuzzy applications. We want to investigate how well fuzzy systems can approximate a given system. The following theorem from Reference [15] is known as the "Universal Approximation Theorem." We will then give an example to show the capability of fuzzy systems.

* * *

### Theorem 5.1

For any given real continuous function   on a compact set   and arbitrary   with Gaussian MFs, there exists a fuzzy logic system   in the form of (5.17) such that

**5.18**

* * *

The proof is given in Reference [15] [pp. 124–126].

The next example introduced in Reference [18] shows the capability of fuzzy systems. It shows that fuzzy systems are good approximators of a given nonlinear system. The objective of the following example is to introduce the reader to FISs and to show how adding MFs can improve the approximation of nonlinear system by using an FIS.

* * *

### Example 5.1

Consider a first-order nonlinear system. The dynamic equation of the system is given by Reference [15]

**5.19**

* * *

We define five fuzzy sets over the interval  : negative medium (NM), negative small (NS), zero (ZE), positive small (PS), and positive medium (PM). The MFs are given by

**5.20**

Figure 5-3a shows the five MFs.

**Figure 5-3** Membership functions. (a) Membership functions of five fuzzy sets. (b) Membership functions of seven fuzzy sets.

Reproduced from [13], © B, Al Faiya.

To estimate the dynamics of the system, the following linguistic descriptions (fuzzy IF-THEN rules) are given to the designer:

**5.21**

We set the conclusions  ,  ,  ,  , and   as in (5.4). Since there is only one antecedent for every fuzzy IF-THEN rule, we rewrite (5.17) as

**5.22**

To improve the performance of the fuzzy system, we need more specific MFs and linguistic descriptions in the fuzzy system. Therefore, we define seven fuzzy sets over the interval  : negative big (NB), negative medium (NM), negative small (NS), zero (ZE), positive small (PS), positive medium (PM), and positive big (PB). The MFs of the fuzzy sets NB and PB are defined as  ,  . The MFs of fuzzy sets NM, NS, ZE, PS, and PM are the same as in (5.20). Figure 5-3b illustrates the MFs of the seven fuzzy sets. The fuzzy IF-THEN rules are given as follows:

**5.23**

where  ,  ,  ,  ,  ,  , and  , are the conclusions in (5.4).

Then the fuzzy system becomes

**5.24**

Figure 5-4 shows the estimation   (dashed line). Figure 5-5 shows the estimation error (solid line)   over the interval  .

**Figure 5-4** Nonlinear function   and the estimation   with five rules and seven rules.

Reproduced from [13], © B, Al Faiya.

**Figure 5-5** Estimation error   with five rules and seven rules.

Reproduced from [13], © B, Al Faiya.

## 5.3 Fuzzy Q-Learning

The value of the game is based on the assumption that both players play their Nash equilibrium strategies. In practical applications, one player may not know its own Nash equilibrium strategy or its opponent's strategy. Therefore, learning algorithms are needed to help the player learn its equilibrium strategy. Most of the learning algorithms applied to DGs, especially to the pursuer–evader game, are based on reinforcement learning algorithms [4–6].

A typical reinforcement learning approach such as Q-learning needs to discretize the action space and the state space. However, when the continuous state space or action space is large, the discrete representation of the state or action is computationally intractable [19]. Wang [20] proved that an FIS is a universal approximator which can approximate any nonlinear function to any degree of precision. Therefore, one can use fuzzy systems to generate continuous actions of the players or represent the continuous state space.

The fuzzy system in this chapter, as shown in Fig. 5-6, is implemented by TS rules with constant consequents [21]. We structure the FIS for the use as part of a reinforcement learning system in the following way. It consists of   rules with   fuzzy variables as inputs and one constant number as the consequent. Each rule   is of the form

**5.25**

where   are the inputs passed to the fuzzy controller,   is the fuzzy set related to the corresponding fuzzy variable,   is the rule's output, and   is a constant that describes the center of a fuzzy set. If we use the product inference for fuzzy implication [20], _t_ -norm, singleton fuzzifier, and center-average defuzzifier, the output of the system becomes

**5.26**

where   is the membership degree of the fuzzy set   and

**5.27**

**Figure 5-6** Basic configuration of fuzzy systems.

Reproduced from [13], with permission of Carleton University.

Among fuzzy reinforcement learning algorithms, one may use a fuzzy Q-learning (FQL) algorithm to generate a global continuous action for the player based on a predefined discrete action set. We assume that the player has   possible actions from an action set  . To generate the player's global continuous action, we use the following form of fuzzy IF-THEN rules:

**5.28**

where   is the chosen action from the player's discrete action set   for rule  . The action   is chosen on the basis of an exploration-exploitation strategy [23]. In this chapter, we use the  -greedy policy as the exploration-exploitation strategy. The  -greedy policy is defined such that the player chooses a random action from the player's discrete action set   with a probability   and a greedy action with a probability  . The greedy action is the action that gives the maximum value in an associated  -function. Then we have

**5.29**

where   is the associated  -function given the rule   and the player's action  . Based on (5.26), the global continuous action at time   becomes

**5.30**

where   are the inputs,   is the number of fuzzy IF-THEN rules, and   is the chosen action in (5.29) for rule   at time  .

Similar to (5.30), we can generate the global Q-function by replacing   in (5.26) with   and get

**5.31**

We can also define   as the global Q-function with the maximum  -value for each rule. Then (5.31) becomes

**5.32**

where   denotes the maximum value of   for all   in rule  .

Given (5.31) and (5.32), we define the temporal difference (TD) error as

**5.33**

where   is the discount factor and   is the received reward at time  . Then the update law for the  -function is given as

**5.34**

where   is the learning rate.

The FQL learning algorithm is summarized in Algorithm 5.1.

## 5.4 Fuzzy Actor–Critic Learning

In FQL, one has to define the player's action set   based on the knowledge of the player's continuous action space. Suppose we do not know how large the action space is or the exact region the action space is in, the determination of the action set becomes difficult. Moreover, the number of elements in the action set will be prohibitively large when the action space is large. Correspondingly, the dimension of the   function in (5.34) will be intractably large. To avoid this, we present in this section an FACL method.

The actor–critic learning system contains two parts: one is to choose the optimal action for each state called the _actor_ , and the other is to estimate the future system performance called the _critic_. Figure 5-7 shows the architecture of the actor–critic learning system. The actor is represented by an adaptive fuzzy controller which is implemented as an FIS. We also propose to implement the critic as an FIS. We have implemented the adaptive fuzzy critic in References [6, 24]. We showed that the adaptive fuzzy critic in Reference [6] performed better than the neural network proposed in Reference [19]. In the implementation proposed in this chapter, we only adapt the output parameters of the fuzzy system, whereas in Reference [6] the input and output parameters of the fuzzy system are adapted, which is a more complex adaptive algorithm. The reinforcement signal   is used to update the output parameters of the adaptive controller and the adaptive fuzzy critic, as shown in Fig. 5-7.

**Figure 5-7** Architecture of the actor–critic learning system.

Reproduced from [13], with permission from MIT Press.

The actor is represented by an adaptive fuzzy controller which is implemented by TS rules with constant consequents. Then the output of the fuzzy controller becomes

**5.35**

where   is the output parameter of the actor.

In order to promote exploration of the action space, a random white noise   is added to the generated control signal  . The output parameter of the actor   is adapted as

**5.36**

where   is the learning rate for the actor.

In order to avoid large adaptation steps in the wrong direction [25], we use only the sign of the prediction error   and the exploration part   in (5.36). Then, Eq. (5.36) becomes

**5.37**

where

**5.38**

The task of the critic is to estimate the value function over a continuous state space. The value function is the expected sum of discounted rewards defined as

**5.39**

where   is the current time step,   is the received immediate reward at the time step  , and   is a discount factor. Equation (5.39) can be also rewritten recursively as

**5.40**

After each action selection from the actor, the critic evaluates the new state to determine whether things have gone better or worse than expected. For the critic in Fig. 5-7, we assume TS rules with constant consequents [25]. The output of the critic   is an approximation to  , given by

**5.41**

where   denotes a discrete time step,   is the output parameter of the critic defined as   in (5.25), and   is defined in (5.27).

Based on (5.40) and the above approximation  , we can generate a prediction error   as

**5.42**

This prediction error is then used to train the critic. Supposing it has the parameter   to be adapted, the adaptation law would then be

**5.43**

where   is the learning rate for the critic. We set  , where   is given in (5.36), so that the actor will converge more slowly than the critic to prevent instability in the actor [24]. Also the partial derivative is easily calculated to be

**5.44**

The FACL algorithm is summarized in Algorithm 5.2.

## 5.5 Homicidal Chauffeur Differential Game

DGs [2] are a family of dynamic, continuous-time games. The homicidal chauffeur DG is one type of DG. It was originally presented by Isaacs in 1954. A pursuer or a group of pursuers attempt to capture one or a group of evaders in minimal time, while the evaders try to avoid being captured.

The game terminates when the evader is within the lethal range of the pursuer (capture or termination time), or when the time exceeds 1 min (escape). Players evaluate the current state and then select their next actions. The players' strategies are not shared, and therefore each player has no knowledge of the other player's next selected action. We assume that the environment is obstacle-free.

The existence of optimal strategies in the pursuit–evasion DG is determined by Isaacs' condition [26–28]. The formal results concerning optimal strategies for pursuit–evasion DGs are given in References [26, 29]. The homicidal chauffeur game and Isaacs condition for the game are discussed below.

In our model, a homicidal chauffeur game is played by autonomous robots. The chauffeur (the pursuer  ) is a car-like mobile robot, and the pedestrian (the evader  ) is a point that can move in any direction instantaneously. In Isaacs' homicidal chauffeur DG, a pursuer aims to minimize the capture time of an evader. The evader's objective is to maximize the capture time and avoid capture.

We assume that the players move at a constant forward speed  . The pursuer's speed is greater than the evader's speed, but the evader can move in any direction. The steering angle of the pursuer is given as      , where   is the maximum steering angle. The maximum steering angle results in a minimum turning radius   defined by

**5.45**

where   is the pursuer's wheelbase.

The dynamic equations for the pursuer   and the evader   are [26]

**5.46**

where  ,  , and   denote the position, the velocity, and the orientation, respectively, as shown in Fig. 5-8. The angle difference   between the pursuer and the evader is given as

**5.47**

**Figure 5-8** Homicidal chauffeur problem model.

Reproduced from [13], © B, Al Faiya.

The relative distance between pursuer and evader is found as

**5.48**

The capture occurs when the distance  .

In Reference ([[26]], pp. 232–237), Isaacs presented a condition for the pursuer to succeed in capturing the evader. Assuming that the pursuer's speed is greater than the evader's, the capture condition is given as

**5.49**

where   is the ratio of the radius of capture to the minimum turning radius of the pursuer, and   is the ratio of the evader's speed to the pursuer's speed. If the inequality (5.49) is reversed,   escapes from   indefinitely.

Based on the capture condition in (5.49) and Isaacs' solution of the problem, the evader's optimal strategy can be obtained by solving the following two problems [26, 29, 30]:

  1. When the evader is far enough from the pursuer, the evader's control strategy is to maximize the distance between the evader and the pursuer as follows:

**5.50**

  2. When the distance between the pursuer and evader becomes such that  , the evader adopts a second control strategy to avoid capture. The pursuer cannot turn more than a minimum turning radius  . The evader will make a sharp turn, normal to its direction, and enter the pursuer's non-holonomic constraint region. As shown in Fig. 5-9, a non-holonomic player is constrained to move along paths of bounded curvature such as the pursuer's minimum turning radius   given in Eq. (5.45). The evader's second control strategy is given as

**5.51**

**Figure 5-9** The vehicle cannot turn into the circular region defined by its minimum turning radius  .

Reproduced from [13], © B, Al Faiya.

The pursuer's optimal control strategy is to minimize the distance and capture the evader in minimum time. The pursuer controls its steering angle as follows [28, 29, 31]:

**5.52**  

#

#

## 5.6 Fuzzy Controller Structure

We use two inputs (fuzzy variables) to the fuzzy controller and generate one output from the fuzzy controller. The inputs for the pursuer are the angle difference   and its rate of change  . The inputs for the evader are the angle difference   and the distance  . We add the distance as an input to the fuzzy controller for the evader. The reason is that the evader has higher maneuverability than the pursuer and the distance between the evader and the pursuer is critical for the evader to decide if it needs to make a sharp turn.

For simplicity and to avoid the curse of dimensionality, we use two inputs and three fuzzy sets for each input to construct the controller. The pursuer's fuzzy sets are negative (N), zero (Z), and positive (P) for the angle difference   and its derivative  . The evader's fuzzy sets are negative (N), zero (Z), and positive (P) for the angle, and far (F), close (C), and very close (V) for the distance.

We apply a zero-order TS FIS [11]. TS FIS consists of fuzzy IF-THEN rules and a fuzzy inference engine. Given the fuzzy variables   and the corresponding fuzzy sets   and  , the fuzzy IF-THEN rules are

**5.52**

where   represents   and   for the pursuer,   and   for the evader.   is the output function of rule   and   is the parameter for the consequence part of the fuzzy rules.

Three MFs are used for each input, which results in constructing   rules. The Gaussian MFs are given as

**5.53**

The Gaussian MF parameters are the mean   and the standard deviation  . We use reinforcement learning to learn the MF parameters. Figure 5-10a and b show the initial MF's before tuning.

**Figure 5-10** Membership functions before training. (a) Pursuer membership functions before training. (b) Evader membership functions before training.

Reproduced from [13], © B, Al Faiya.

The steering angle   is the output formed by the weighted average defuzzifier, and expressed as

**5.54**

The fuzzy rules are illustrated using the tabular format. Tables 5.2 and 5.3 show the fuzzy decision table and the output constant   for the pursuer and the evader, respectively, before learning.

**Table 5.2** Pursuer's fuzzy decision table before learning.

---

**Table 5.3** Evader's fuzzy decision table before learning.

---

## 5.7 Q( )-Learning Fuzzy Inference System

A learning agent in a reinforcement learning problem interacts with the environment and receives a reward   at each time step  . The agent's goal is to

maximize the long-run discounted return   [23]

**5.55**

where   is the discount factor,   is the current time step, and   is the episode terminal time.

One common type of reinforcement learning is Q-learning. Q-learning estimates the action-value function   to achieve the best expected return. The action-value function is given as

**5.56**

Desouky and Schwartz [31] proposed the Q( )-learning fuzzy inference system (QLFIS) technique. In Reference [31], QLFIS was successfully applied to train the pursuer to capture the evader in minimum time. We apply Desouky's QLFIS algorithms for our model to train both the evader and the pursuer. The construction of the learning system is shown in Fig. 5-11. Q( )-learning is used to tune the input and the output parameters of the fuzzy logic controller (FLC) and the function approximator which is implemented by an FIS. In Reference [31], Desouky derived and presented the update rules of the learning process.

Figure 5-11 Construction of the learning system where the white Gaussian noise   is added as an exploration mechanism.

Reproduced from [13], © B, Al Faiya.

As shown in Fig. 5-11, the TD error   is given as

**5.57**

We apply the eligibility traces   to Eq. (5.56). The Q( )-learning action-value function in is updated by

**5.58**

where   is the learning rate, and the replacing eligibility traces is represented as

**5.59**

Given the parameters   to be tuned in the fuzzy systems, the update rules for the FIS are defined by Reference [31]

**5.60**

and the update rules for the FLC are defined by

**5.61**

where

**5.62**

**5.63**

with the learning rate   for the FIS and   for the FLC. The firing strength   and the normalized firing strength   of the rule   are defined as follows [31]:

**5.64**

**5.65**

The learning algorithm used in our simulation is shown in Algorithm 5.3, where M is the number of episodes (games) and N is the number of steps (plays).

## 5.8 Simulation Results for the Homicidal Chauffeur

We simulate the system for different numbers of episodes. The number of steps is 600, and the sampling time is   s.

The pursuer is twice as fast as the evader such that   m/s and   m/s. The pursuers wheelbase is   m. At each episode, the position of the evader is initialized randomly. The initial position of the pursuer is at the origin  , and the initial orientation of the pursuer is   rad. We consider the kinematic equations of the pursuer and the evader given in Eq. (5.45).

The game terminates when the pursuer captures the evader, or when the time exceeds 60 s (escape). The capture radius is   m which is half the wheelbase of the pursuer  . The maximum steering angle of the pursuer is   rad with   m. Given the stated parameters of the system and using Isaacs' capture condition, there exists a strategy for the evader to avoid capture.

We now use the learning algorithm presented in Algorithm 5.3 to simulate the game. The initial conditions of the learning system are given in steps 1–5 of Algorithm 5.3. To evaluate the learning technique efficiency of the evader, the pursuer's parameters are initialized such that the pursuer can capture the evader with their initial strategies before learning. We apply the same learning algorithm QLFIS to both players.

At the beginning of the learning, the pursuer always captured the evader, as shown in Fig. 5-12. After 500 episodes, in Fig. 5-13, the evader increased the capture time and made successful maneuvers. Figure 5-14 and Table 5.4 show that the evader learned to escape from the pursuer after 1000 episodes. The evader makes sharp turns when the distance  . The evader avoids capture by changing its direction and entering into the pursuer's turning radius constraint. The learners' fuzzy consequence parameters   after 1000 episodes are shown in Tables 5.5 and 5.6.

**Figure 5-12** The pursuer captures the evader with 100 learning episodes.

Reproduced from [13], © B, Al Faiya.

**Figure 5-13** The evader increases the capture time after 500 learning episodes.

Reproduced from [13], © B, Al Faiya.

**Figure 5-14** The evader learns to escape after 1000 learning episodes.

Reproduced from [13], © B, Al Faiya.

**Table 5.4** Capture time (s) for different numbers of learning episodes.

Game | No. of episodes | Capture time (s)  
---|---|---  
Theoretical | — |  60 (escape)  
| 100 | 12.90  
After learning using QLFIS | 500 | 25.10  
| 1000 |  60 (escape)

**Table 5.5** The evader's fuzzy decision table after 1000 learning episodes.

---

**Table 5.6** The pursuer's fuzzy decision table after 1000 learning episodes.

---

For comparison, we show the results of the theoretical solution described in Section 5.5. Given the stated parameters of the system and using Isaacs capture condition, there exists a strategy for the evader to avoid capture when   rad. Figure 5-15 shows that the evader can escape from the pursuer by making sharp turns. We then increase the maximum steering angle of the pursuer to   rad. In this case, the capture condition is satisfied. The pursuer can capture the evader as shown in Fig. 5-16 with capture time   s.

Figure 5-15 The evader avoids capture when   rad.

Reproduced from [13], © B, Al Faiya.

Figure 5-16 The pursuer can capture the evader when   rad.

Reproduced from [13], © B, Al Faiya.

## 5.9 Learning in the Evader–Pursuer Game with Two Cars

The pursuit–evasion model is shown in Fig. 5-17. Equations of motion for the pursuer/evader robot are [29]

**5.66**

where " " is " " for the pursuer and is " " for the evader,   is the position of the robot,   is the orientation,   is the robot wheelbase,   is the steering angle,  , and   is the velocity of the robot which is governed by the steering angle, to avoid slips, such that

**5.67**

where   is the maximum velocity of the robot. Our scenario is to make the pursuer faster than the evader, that is,  , but at the same time to make the pursuer less maneuverable than the evader, that is,  . The control strategy for the pursuer is to drive the angle difference between the pursuer and the evader,  , to be zero where the error in angle,  , is calculated as

**5.68**

The control strategy for the evader is to maximize the distance between them in two ways [29, 32]:

  1. If the distance between the pursuer and the evader is greater than a certain value  , then the control strategy for the evader is

**5.69**

  2. If the distance between the pursuer and the evader is smaller than  , then the evader exploits its higher maneuverability. Therefore, the control strategy for the evader will be

**5.70**

Figure 5-17 The game of two cars.

Reproduced from [13], © B, Al Faiya.

This strategy will increase the maneuverability of the evader and make it more difficult (but not impossible) for the pursuer to catch the evader. We choose this strategy to show the effect of our proposed techniques on the system. The classical control strategy of the pursuer that we compare our results with is defined by

**5.71**

where   is defined by (5.68).

The capture occurs when the distance between the pursuer and the evader is less than a certain value,  . We call this the capture radius, which is defined as

**5.72**

## 5.10 Simulation of the Game of Two Cars

The initial position of the pursuer is at the origin  , and the position of the evader is initialized randomly at each episode. The initial orientation of the pursuer and the initial positions are the same as in the homicidal chauffeur game. The initial orientation of the evader is   rad. We use the kinematic equations of the pursuer and the evader given in (5.66).

Similarly, the game is initialized such that the pursuer can capture the evader as shown in Fig. 5-18. After 500 episodes, in Fig. 5-19, the evader increased the capture time and made a successful maneuver. Figure 5-20 and Table 5.7 show that the evader learned to escape from the pursuer after approximately 1300 episodes. The evader makes sharp turns to enter into the pursuer's turning radius constraint when the distance  .

Figure 5-18 The pursuer captures the evader with 100 learning episodes.

Reproduced from [13], © B, Al Faiya.

Figure 5-19 The evader increases the capture time after 500 learning episodes.

Reproduced from [13], © B, Al Faiya.

Figure 5-20 The evader learns to escape after 1300 learning episodes. (a) The evader learns to escape after 1300 learning episodes. (b) Zoomed version of (a).

Reproduced from [13], © B, Al Faiya.

**Table 5.7** Summary of the time of capture for different numbers of learning episodes in the game of two cars.

Game | No. of episodes | Capture time _T c_ (sec)  
---|---|---  
Theoretical | — |  60 (escape)  
| 100 | 13.70  
After learning using QLFIS | 500 | 27.50  
| 1300 |  60 (escape)

Figures 5.21 and 5.22 show the MFs of the evader and the pursuer after learning. The consequence parameters   after training are shown in Tables 5.8 and 5.9.

**Figure 5-21** The pursuer's membership functions after training. (a) The angle difference φ. (b) The rate of change of the angle difference  .

Reproduced from [13], © B, Al Faiya.

**Figure 5-22** The evader's membership functions after training. (a) The angle difference φ. (b) The distance between the pursuer and the evader _d_.

Reproduced from [13], © B, Al Faiya.

**Table 5.8** The evader's fuzzy decision table and the output constant   after learning.

---

**Table 5.9** The pursuer's fuzzy decision table and the output constant   after learning.

---

_Without Eligibility Traces._ We now apply Q-learning without the use of eligibility traces. In each episode, we record the time of capture and plot the time versus 500 episodes. Then we run 10 simulations and average the result. The solid line in Fig. 5-23 is the result from using  -learning. The dashed line is the result from using Q-learning. Compared to Q-learning, the learning speed is similar to that with the eligibility traces. The convergence speed of the player's learning process has not improved significantly when using Q( )-learning.

**Figure 5-23** The time of capture with the use of eligibility traces in the game of two cars.

Reproduced from [13], © B, Al Faiya.

This section presented the applications of fuzzy Q( )-learning and fuzzy Q-learning to pursuit–evasion DGs. The fuzzy controller, the convergence of the learning process, and the learning speed were investigated. The QLFIS technique was then used to train both the evader and the pursuer simultaneously. The trained evader learned to make sharp turns (extreme strategy) to maximize the time of capture and, if possible, avoid being captured. Simulation results of the homicidal chauffeur game and the game of two cars showed that the evader successfully learned to escape from the pursuer. The use of eligibility traces did not significantly improve the learning speed when used in Q( )-learning. Moreover, eligibility traces required more computations per episode.

## 5.11 Differential Game of Guarding a Territory

In this section, we apply fuzzy reinforcement learning algorithms to the DG of guarding a territory and let the defender learn its Nash equilibrium strategy by playing against the invader. To speed up the defender's learning process, we design a shaping reward function for the defender in the game. Moreover, we apply the same FACL algorithm and shaping reward function to a three-player DG of guarding a territory including two defenders and one invader. We run simulations to test the learning performance of the defenders in both cases.

In reinforcement learning, a reinforcement learner may suffer from the temporal credit assignment problem where a player's reward is delayed or only received at the end of an episodic game. When a task has a very large state space or continuous state space, the delayed reward will slow down the learning dramatically. For the game of guarding a territory, the only reward received during the game is the distance between the invader and the territory at the end of the game. Therefore, it is extremely difficult for a player to learn its optimal strategy based on this very delayed reward. To deal with the temporal credit assignment problem and speed up the learning process, one can apply reward shaping to the learning problem [33]. Shaping can be implemented in reinforcement learning by designing intermediate shaping rewards as an informative reinforcement signal to the learning agent and reward the agent for making a good estimate of the desired behavior [23, 34, 35]. The idea of reward shaping is to provide an additional reward as a hint, based on the knowledge of the problem, to improve the performance of the agent [33].

The Isaacs' guarding a territory game is a two-player zero-sum DG. The invader's goal is to reach the territory. If the invader cannot reach the territory, it at least moves to a point as close to the territory as possible [2]. Accordingly, the defender tries to intercept the invader at a point as far away as possible from the territory [2]. We denote the invader as I and the defender as D in Fig. 5-24. The dynamics of the invader I and the defender D are defined as

**5.73**

**5.74**

where   is the defender's strategy and   is the invader's strategy.

**Figure 5-24** The differential game of guarding a territory.

Reproduced from [18], © X. Lu.

In order to simplify the problem, we establish a relative coordinate frame centered at the defender's position with its  -axis in the direction of the invader's position as shown in Fig. 5-24. The territory is represented by a circle with center     and radius  . Different from   and   in the original coordinate frame, we define   as the defender's strategy and   as the invader's strategy in relative coordinates.

The payoff for this game is defined as

**5.75**

where   denotes the players' initial positions,   is the radius of the target, and   is the terminal time. The terminal time is the time when the invader reaches the territory, or the invader is intercepted before it reaches the territory. The above payoff indicates how close the invader can move to the territory if both players start from their initial positions and follow their stationary strategies   and   thereafter. In this game, the invader tries to minimize the payoff   while the defender tries to maximize it.

In Fig. 5-24, we draw the bisector BC of the segment ID. According to the dynamics of the players in (5.73) and (5.74), the players can move in any direction instantaneously with the same speed. Therefore, the region above the line BC is where the invader can reach before the defender, and the region below the line BC is where the defender can reach before the invader. We draw a perpendicular line TO to the bisector BC through the point T. Then point O is the closest point on the line BC to the territory T. Starting from the initial position  , if both players play their optimal strategies, the invader can only reach point O as its closest point to the territory.

The value of the game can be found as the shortest distance between the line BC and the territory. We define the value of the game as

**5.76**

where   and   are the players' Nash equilibrium strategies given by

**5.77**

**5.78**

## 5.12 Reward Shaping in the Differential Game of Guarding a Territory

In reinforcement learning, the player may suffer from the temporal credit assignment problem where a reward is received only after a sequence of actions. For example, players in a soccer game are given rewards only after a goal is scored. This will lead to the difficulty in distributing credit or punishment to each action from a long sequence of actions. We define the terminal reward when the reward is received only at the terminal time. If the reinforcement learning problem is in the continuous domain with only a terminal reward, it is almost impossible for the player to learn without any information other than this terminal reward.

In the DG of guarding a territory, the reward is received only when the invader reaches the territory or is intercepted by the defender. According to the payoff function given in (5.75), the terminal reward for the defender is defined as

**5.79**

where   is the distance between the invader and the territory at the terminal time. Since we only have terminal rewards in the game, the learning process of the defender will be prohibitively slow. To solve this, one can use a shaping reward function for the defender to compensate for the lack of immediate rewards.

The purpose of reward shaping is to improve the learning performance of the player by providing an additional reward to the learning process. But the question is how to design good shaping reward functions for different types of games. In the pursuit–evasion game, the immediate reward is defined as

**5.80**

where   denotes the distance between the pursuer and the evader at time  . One might consider the above immediate reward as the shaping reward function for the DG of guarding a territory. However, the immediate reward in (5.80) is not a good candidate for the shaping reward function in our game. The goal of the pursuer is to minimize the distance between the pursuer and the evader at each time step. Different from the pursuer, the goal of the defender in the DG of guarding a territory is to keep the invader away from the territory. Since the defender and the invader have the same speed, the defender may fail to protect the territory if the defender keeps chasing after the invader all the time.

Based on the above analysis and the characteristics of the game, we design the following shaping reward function for the defender:

**5.81**

where   and   denote the territory's relative position of the  -axis at time   and  , respectively.

The shaping reward function in (5.81) is designed based on the idea that the defender tries to protect the territory from invasion by keeping the territory and the invader on opposite sides. In other words, if the invader is on the defender's left side, then the defender needs to move in a direction where it can keep the territory as far to the right side as possible. As shown in the relative coordinates in Fig. 5-24, the invader is located on the positive side of the  -axis. Then, the goal of the defender in Fig. 5-24 is to keep the invader on the positive side of the  -axis and move in a direction where it can keep the territory further to the negative side of the  -axis.

## 5.13 Simulation Results

We assume that the defender does not have any information about its optimal strategy or the invader's strategy. The only information the defender has is the players' current positions. We apply the aforementioned FQL and FACL algorithms in Section 5.4 to the game and make the defender learn to intercept the invader. To compensate for the lack of immediate rewards, the shaping reward functions introduced in Section 5.12 are added to the FQL and FACL algorithms. Simulations are conducted to show the learning performance of the FQL and FACL algorithms based on different reward functions. Then we add one more defender to the game. We use the same FACL algorithm to both defenders independently. Each defender only has its own position and the invader's position as the input signals. Then the FACL algorithm becomes a completely decentralized learning algorithm in this case. We test, through simulations, how the two defenders can cooperate with each other to achieve good performance even though they do not directly share any information.

### 5.13.1 One Defender Versus One Invader

We first simulate the DG of guarding a territory with two players whose dynamics are given in (5.73) and (5.74).

To reduce the computational load,   in (5.26) is defined as a triangular MF. In this game, we define three input variables, which are the relative  -position   of the invader, the relative  -position   of the territory, and the relative  -position   of the territory. The predefined triangular MFs for each input variable are shown in Figs. 5.25–5.27. The number of fuzzy rules applied to this game is  . The selection of the number of rules and the MFs in the premise part of the fuzzy rules is based on the prior knowledge of the game.

**Figure 5-25** MFs for  .

Reproduced from [18], with permission of Carleton University.

Figure 5-26 Membership functions for input variables.

Reproduced from [18], with permission of Carleton University.

**Figure 5-27** Membership functions for input variables.

Reproduced from [18], © X. Lu.

For the FQL algorithm, we pick the discrete action set   as

**5.82**

The  -greedy policy in (5.29) is set to  . For the FACL algorithm, we set the learning rate   in (5.43) and   in (5.35). The exploration policy in the FACL algorithm is chosen as a random white noise   with  . To reduce the influence of the future rewards to the current state, we choose a small discount factor   in (5.33) and (5.42).

We now define episodes and training trials for the learning process. An _episode_ or a single run of the game is when the game starts at the players' initial positions and ends at a terminal state. A _terminal state_ in this game is the state where the defender captures the invader or the invader enters the territory. A _training trial_ is defined as one complete learning cycle which contains 200 training episodes. We set the invader's initial position at   for each training episode. The center of the territory is located at   with radius  .

* * *

### Example 5.2

We assume that the invader plays its Nash equilibrium strategy all the time. The defender, starting at the initial position  , learns to intercept the NE invader. We call the invader that always plays its Nash equilibrium strategy as the _NE invader_. We run simulations to test the performance of the FQL and FACL algorithms with different shaping reward functions introduced in Section 5.12. Figures 5.28–5.30 show the simulation results after one training trial including 200 training episodes. In Fig. 5-28, with only the terminal reward given in (5.79), the trained defender failed to intercept the invader. The same happened when the shaping reward function given in (5.80) was used in the FQL and the FACL algorithms, as shown in Fig. 5-29. As we discussed in Section 5.12, the shaping reward function in (5.80) is not a good candidate for this game. With the help of our proposed shaping reward function in (5.81), the trained defender successfully intercepted the invader, as shown in Fig. 5-30.

This example verifies the importance of choosing a good shaping reward function for the FQL and FACL algorithms for our game.

* * *

**Figure 5-28** Reinforcement learning with no shaping function in Example 5.2. (a) Trained defender using FQL with no shaping function. (b) Trained defender using FACL with no shaping function.

Reproduced from [18], © X. Lu.

**Figure 5-29** Reinforcement learning with a bad shaping function in Example 5.2. (a) Trained defender using FQL with the bad shaping function in Example 5.2. (b) Trained defender using FACL with the bad shaping function in Example 5.2.

Reproduced from [18], © X. Lu.

**Figure 5-30** Reinforcement learning with a good shaping function in Example 5.2. (a) Trained defender using FQL with the good shaping function in Example 5.2. (b) Trained defender using FACL with the good shaping function in Example 5.2.

Reproduced from [18], with permission of Carleton University.

* * *

### Example 5.3

In this example, we show the average performance of the FQL and FACL algorithms with the proposed shaping reward function given in (5.81).

The training process includes 20 training trials with 200 training episodes for each training trial. For each training episode, the defender randomly chooses one initial position from the defender's initial positions 1–4 shown in Fig. 5-31. After every 10 training episodes in each training trial, we set up a testing phase to test the performance of the defender trained so far. In the testing phase, we let the NE invader play against the trained defender and calculate the performance error as follows:

**5.83**

where   represents the initial positions of the players, the payoffs   and   are calculated based on (5.75), and   denotes the calculated performance difference for players' initial positions  . In this example, the invader's initial position is fixed during learning. Therefore, the players' initial positions   are represented as the defender's initial positions 1–6 shown in Fig. 5-31. We use   to represent the calculated performance error for the defender's initial position   at the  th training episode. For example,   denotes the performance error calculated based on (5.83) for defender's initial position 1 at the  th training episode. Then we average the performance error over 20 trails and get

**5.84**

where   denotes the averaged performance error for players' initial position   at the  th training episode over 20 training trails.

Figure 5-32 shows the results where the average performance error   becomes smaller after learning for the FQL and the FACL algorithms. Note that the defender's initial positions 5 and 6 in Fig. 5-31 are not included in the training episodes. Although we did not train the defender's initial positions 5 and 6, the convergence of the performance errors   and   verify that the defender's learned strategy is close to its NE strategy. Compared to Fig. 5-32a for the FQL algorithm, in Fig. 5-32b the performance errors for the FACL algorithm converge closer to zero after the learning. The reason is that the global continuous action in (5.30) for the FQL algorithm is generated based on a fixed discrete action set   with only eight elements given in (5.82). The closeness of the defender's learned action (strategy) to its NE action (strategy) is determined by the size of the action set   in the FQL algorithm. A larger size of the action set encourages the convergence of the defender's action (strategy) to its NE action (strategy), but the increasing dimension of the Q function will cause a slow learning speed, as we discussed at the beginning of Section 5.4. For the FACL algorithm, the defender's global continuous action is updated directly by the prediction error in (5.42). In this way, the convergence of the defender's action (strategy) to its NE action (strategy) is better in the FACL algorithm.

* * *

**Figure 5-31** Initial positions of the defender in the training and testing episodes in Example 5.3.

Reproduced from [18], with permission of Carleton University.

**Figure 5-32** Example 5.3: average performance of the trained defender versus the NE invader. (a) Average performance error   in the FQL algorithm. (b) Average performance error   in the FACL algorithm.

Reproduced from [18], © X. Lu.

### 5.13.2 Two Defenders Versus One Invader

We now add a second defender to the game with the same dynamics as the first defender as defined in (5.73). The payoff for this game is defined as

**5.85**

where  , and   are the strategies for defender 1, defender 2, and the invader, respectively, and   is the radius of the target. Based on the analysis of the two-player game in Section 5.11, we can also find the value of the game for the three-player DG of guarding a territory. For example, we call the gray region in Fig. 5-33 as the invader's reachable region where the invader can reach before the two defenders. Then the value of the game becomes the shortest distance from the territory to the invader's reachable region. In Fig. 5-33, point O on the invader's reachable region is the closest point to the territory. Therefore, the value of the game becomes

**5.86**

where   are the NE strategies for defender 1, defender 2, and the invader, respectively. Based on (5.86), the players' NE strategies are given as

**5.87**

**5.88**

**5.89**

**Figure 5-33** The differential game of guarding a territory with three players.

Reproduced from [18], © X. Lu.

We apply the FACL algorithm to the game and make the two defenders learn to cooperate to intercept the invader. The initial position of the invader and the position of the target are the same as in the two-player game. Each defender in this game uses the same parameter settings of the FACL algorithm as in Section 5.13.1. Moreover, each defender has the information of only its own position and the invader's position without any information from the other defender. Each defender uses the same FACL algorithm independently, which makes the FACL algorithm a completely decentralized learning algorithm in this game.

* * *

### Example 5.4

We assume that the invader plays its Nash equilibrium strategy given in (5.89) all the time. The two defenders, starting at the initial position   for defender 1 and   for defender 2, learn to intercept the NE invader. Similar to the two-player game in Section 5.13.1, we run a single trial including 200 training episodes to test the performance of the FACL algorithm with different shaping reward functions given in Section 5.12. In Fig. 5-34, two defenders failed to intercept the NE invader with only the terminal reward and with the shaping reward function given in (5.80). On the contrary, with the proposed shaping reward function in (5.81), the two trained defenders successfully intercepted the NE evader after one training trial, as shown in Fig. 5-35.

* * *

**Figure 5-34** Reinforcement learning without shaping or with a bad shaping function in Example 5.4. (a) Two trained defenders using FACL with no shaping function versus the NE invader after one training trial. (b) Two trained defenders using FACL with the bad shaping function versus the NE invader after one training trial.

Reproduced from [18], © X. Lu.

**Figure 5-35** Two trained defenders using FACL with the good shaping function versus the NE invader after one training trial in Example 5.4.

Reproduced from [18], © X. Lu.

* * *

### Example 5.5

In this example, we show the average performance of the FACL algorithm with our proposed shaping reward function for the three-player game. Similar to Example 5.3, we run 20 training trials with 200 training episodes for each training trial. The training process includes 20 training trials with 200 training episodes for each training trial. For each training episode, the defender randomly chooses one initial position from the defender's initial positions 1–2 shown in Fig. 5-36a.

After every 10 training episodes, we set up a testing phase to test the performance of the defender trained so far. The performance error in a testing phase is defined as

**5.90**

where   represents the defender's initial positions 1–4 shown in Fig. 5-36a, and   and   are the payoffs calculated based on (5.85). Then we average the performance error over 20 trails and get

**5.91**

where   denotes the averaged performance error for players' initial position   at the  th training episode over 20 training trails. The simulation result in Fig. 5-36b shows that the average performance error     converges close to zero after 200 training episodes. Based on the simulation results, the two trained defenders successfully learned to intercept the NE invader. Although there is no training performed for positions 3 and 4, as shown in Fig. 5-36a, the convergence of   and   in Fig. 5-36b verifies the good performance of two trained defenders. Simulation results also verify the effectiveness of the proposed shaping reward function to the FACL algorithm in the three-player DG of guarding a territory.

* * *

**Figure 5-36** Example 5.5: average performance of the two trained defenders versus the NE invader. (a) Initial positions of the players in the training and testing episodes. (b) Average performance error for the trained defenders versus the NE invader.

Reproduced from [18], © X. Lu.

## References

  1. [1] R. Abielmona, E. Petriu, M. Harb, and S. Wesolkowski, "Mission-driven robotic intelligent sensor agents for territorial security," _IEEE Computational Intelligence Magazine_ , vol. **6** , no. 1, pp. 55–67, 2011.
  2. [2] R. Isaacs, _Differential Games: A Mathematical Theory with Applications to Warfare and Pursuit, Control and Optimization_. New York: John Wiley and Sons, Inc., 1965.
  3. [3] M. E. Harmon, L. C. Baird III, and A. H. Klopf, "Reinforcement learning applied to a differential game," _Adaptive Behavior_ , vol. **4** , no. 1, pp. 3–28, 1995.
  4. [4] J. W. Sheppard, "Colearning in differential games," _Machine Learning_ , vol. **33** , pp. 201–233, 1998.
  5. [5] S. N. Givigi, H. M. Schwartz, and X. Lu, "A reinforcement learning adaptive fuzzy controller for differential games," _Journal of Intelligent and Robotic Systems_ , vol. **59** , pp. 3–30, 2010.
  6. [6] S. F. Desouky and H. M. Schwartz, "Self-learning fuzzy logic controllers for pursuit-evasion differential games," _Robotics and Autonomous Systems_ , vol. **59** , pp. 22–33, 2011.
  7. [7] K. H. Hsia and J. G. Hsieh, "A first approach to fuzzy differential game problem: guarding a territory," _Fuzzy Sets and Systems_ , vol. **55** , pp. 157–167, 1993.
  8. [8] Y. S. Lee, K. H. Hsia, and J. G. Hsieh, "A strategy for a payoff-switching differential game based on fuzzy reasoning," _Fuzzy Sets and Systems_ , vol. **130** , no. 2, pp. 237–251, 2002.
  9. [9] L. Jouffe, "Fuzzy inference system learning by reinforcement methods," _IEEE Transactions on Systems, Man, and Cybernetics Part C_ , vol. **28** , no. 3, pp. 338–355, 1998.
  10. [10] K. M. Passino and S. Yurkovich, _Fuzzy Control_. Boston, Massachusetts: Addison-Wesley Longman Publishing Co., Inc., 1st ed., 1998.
  11. [11] J.-S. R. Jang and C.-T. Sun, _Neuro-fuzzy and soft computing: a computational approach to learning and machine intelligence_. Upper Saddle River, New Jersey: Prentice-Hall, Inc., 1997.
  12. [12] L. A. Zadeh, "Fuzzy sets," _Information and Control_ , vol. **8** , no. 3, pp. 338–353, 1965.
  13. [13] B. Al Faiya, "Learning in Pursuit-Evasion Differential Games Using Reinforcement Fuzzy Learning," Master's thesis, Carleton University, Ottawa, ON, Canada, 2012.
  14. [14] T. Takagi and M. Sugeno, "Fuzzy identification of systems and its applications to modelling and control," _IEEE Transactions on Systems, Man, and Cybernetics_ , vol. **SMC-15** , pp. 116–132, 1985.
  15. [15] L.-X. Wang, _A Course in Fuzzy Systems and Control_. Upper Saddle River, New Jersey, Prentice-Hall, Inc., 1997.
  16. [16] J. Jantzen, Design of Fuzzy Controllers. Technical Univ. of Denmark: Technical Report (No:98-E864) Department of Automation, Hoboken, NJ, 1999.
  17. [17] T. J. Ross, _Fuzzy Logic with Engineering Applications_. John Wiley & Sons, Ltd, 2010.
  18. [18] X. Lu, "On Multi-Agent Reinforcement Learning in Games." Ph.D. Thesis Carleton University, Ottawa, ON, Canada, 2012.
  19. [19] X. Dai, C. Li, and A. Rad, "An approach to tune fuzzy contorllers based on reinforcement learning for autonomous vehicle control," _IEEE Transactions on Intelligent Transportation Systems_ , vol. **6** , no. 3, pp. 285–293, 2005.
  20. [20] L. X. Wang, _A Course in Fuzzy Systems and Control_. Englewood Cliffs, New Jersey: Prentice Hall, 1997.
  21. [21] T. Takagi and M. Sugeno, "Fuzzy identification of systems and its application to modeling and control," _IEEE Transactions on Systems, Man, and Cybernetics_ , vol. **15** , pp. 116–132, 1985.
  22. [22] J.-S. R. Jang and C.-T. Sun, _Neuro-Fuzzy and Soft Computing: A Computational Approach to Learning and Machine Intelligence_. Upper Saddle River, New Jersey: Prentice-Hall, Inc., 1997.
  23. [23] R. S. Sutton and A. G. Barto, _Reinforcement Learning: An Introduction_. Cambridge, Massachusetts: The MIT Press, 1998.
  24. [24] S. N. Givigi, H. M. Schwartz, and X. Lu, "An experimental adaptive fuzzy controller for differential games," in Proceedings IEEE Systems, Man and Cybernetics'09, (San Antonio, United States), Oct 2009.
  25. [25] W. M. van Buijtenen, G. Schram, R. Babuska, and H. B. Verbruggen, "Adaptive fuzzy control of satellite attitude by reinforcement learning," _IEEE Transactions on Fuzzy Systems_ , vol. **6** , no. 2, pp. 185–194, 1998.
  26. [26] R. Isaacs, _Differential Games_. New York: John Wiley & Sons, Inc., 1965.
  27. [27] A. MERZ, "The homicidal chauffeur," _AIAA Journal_ , vol. **12** , pp. 259–260, 1974.
  28. [28] T. Basar and G. J. Olsder, _Dynamic Noncooperative Game Theory_. New York: Academic Press, 2nd ed., SIAM Classics, 1999.
  29. [29] S. H. Lim, T. Furukawa, G. Dissanayake, and H. F. D. Whyte, "A time-optimal control strategy for pursuit-evasion games problems," in Proceedings of the 2004 IEEE International Conference on Robotics and Automation, (New Orleans, LA), April 2004.
  30. [30] S. Desouky and H. Schwartz, "Hybrid intelligent systems applied to the pursuit-evasion game," in Systems, Man and Cybernetics, 2009. SMC 2009. IEEE International Conference on, (San Antonio, TX, October 2009, pp. 2603–2608, 2009.
  31. [31] S. Desouky and H. Schwartz, "Q( )-learning fuzzy logic controller for a multi-robot system," in IEEE International Conference on Systems, Man and Cybernetics, 2010. SMC 2010, (Istanbul, Turkey), October 2010.
  32. [32] S. F. Desouky and H. M. Schwartz, "Genetic based fuzzy logic controller for a wall-following mobile robot," in American Control Conference, 2009 ACC 2009, (St. Louis, MO), June 2009, pp. 3555–3560, IEEE, 2009.
  33. [33] M. Grze  and D. Kudenko, "Online learning of shaping rewards in reinforcement learning," _Neural Networks_ , vol. **23** , pp. 541–550, 2010.
  34. [34] M. J. Matari , "Reinforcement learning in the multi-robot domain," _Autonomous Robots_ , vol. **4** , pp. 73–83, 1997.
  35. [35] J. Randløv and P. Alstrøm, "Learning to drive a bicycle using reinforcement learning and shaping," in 15th International Conference on Machine Learning, pp. 463–471, 1998.

# Chapter 6  
Swarm Intelligence and the Evolution of Personality Traits

## 6.1 Introduction

Swarm intelligence can be defined as the study of the social insect metaphor for solving problems in computer science or engineering [1]. It is a very powerful idea and a very interesting topic of research.

In this chapter, we study some of the ideas involved in the subject. We start by discussing the evolution of swarm intelligence and swarm-based robotics. We continue by discussing the necessity of the representation of the environment. Thereafter, we introduce the concept of personality traits as applied to swarm-based robotics.

## 6.2 The Evolution of Swarm Intelligence

Swarm intelligence grew out of the observation of social insect colonies. It emphasizes the distributedness and direct or indirect interaction among (relatively) simple agents [1]. The approach is also designed to be flexible and robust, because a large number of agents will make the whole system resistant to individual failures.

The first and main application of swarm intelligence is in combinatorial optimization. It may be thought of as an alternative to classical approaches and, more specifically, genetic programming. Thus, it is also successfully applied to communication networks [1]. A more exciting approach is the trial of achieving artificial intelligence based on simple agents—a type of collective intelligence. In this sense, intelligence is perceived as the capacity of solve problems and not pure rationality.

One of the main ideas of swarm intelligence is the small amount of (formal) communication among the many individuals in the society. The concept is that the individuals would be able to get information directly from the environment just by observing the behavior of the other individuals. This was named _stigmergy_ (from the Greek _stigma_ : sting, and _ergon_ : work) [2]. The implications of this idea are enormous. First of all, the need for the bandwidth of communication among the agents is largely reduced. Second, the representation of the environment turns out to be very important because it is through this representation (and not the world itself) that a robot communicates. And finally, when we walk toward a robotic representation, sensors become a key aspect of the implementation.

In robotics, the key advantage of swarm intelligence is its simplicity. Since hardware has advanced so much in the past decade or so, it has become possible to implement simple robots and test them in operation. Most important is the possibility to implement the algorithms in very simple chips, such as field-programmable gate arrays (FPGAs).

In this chapter, we deal mostly with the approach of swarm intelligence applied to robotics. We try to understand the nature of cooperation among them and try coordination algorithms that will provide a basis for future development.

## 6.3 Representation of the Environment

The way the environment is represented has a great influence on which techniques may be used to control the robots as well as in how the payoff tables used by game theory are implemented. In order to reduce the robots' computational requirements, the environment is represented by potential fields in a technique known as _co-fields_ [3].

Co-fields are based upon cooperation through social potential fields [4]. Each robot is considered to be a particle with a given position in a fixed time. The environment, containing the other robots, obstacles, and enemies, is represented individually by potential fields. The potential fields represent attraction or repulsion among the objects. In the approach presented here, the meaning of the field is determined by the robot through the adaptation of personality traits as discussed in next section. For now, we may say that the algorithm the robot is running might prefer a downhill—where the robot looks for a low potential valley within its representation—or an uphill—where the robot pursues a peak—approach depending on the task it has and the personalities it developed.

For each robot, according the potential field created by any object it perceives, we may write the "force" [5] acting over it by

**6.1**

where, again, the attractive and repulsive forces are defined differently for each robot. As a result of that, each individual robot perceives the world in a potentially very different way from the others, much like people. In Fig. 6-1, the actual configuration of the world and the ways each one of two robots perceives it are shown. As can be seen, robot A does not know anything about robot B, which, on the other hand, has a representation of its own state (position) that does not fit the actual data, and the other three objects are represented as a cluster (in the form of a big attractor) and not individually. The differences in the representations may result from the learning of new traits of personality or from noise in the sensors. Either way, the robot will have some outcome from its reading. Even if it means it will do nothing, this will come as a result of a computation. In Eq. (6.1),   is the resultant of the individual forces (attractive and repulsive) acting on the robot.

**Figure 6-1** (a) Actual configuration of the world. (b) The way robot A perceives it. (c) The way robot B perceives it. Reproduced from [21] © S. Givigi and H. M. Schwartz.

The direction of the robot's movement is the direction of the resultant force. Observe that the force may be represented as

**6.2**

where   is the unit vector in the direction of the resultant force. In other words, it is

**6.3**

We use this notation in order to emphasize that the fields just define the direction of the movement, but the final decision to move in that direction and the velocity of the movement are determined by the personality traits as defined in the next section. The goal of the robot (equalize the sum of forces or get to a maximum/minimum value of them) is highly dependent on the task it has to perform.

## 6.4 Swarm-Based Robotics in Terms of Personalities

One of the suggestions of the theory of evolution is that animals have emotions [8]. Moreover, these emotions are shared by the same species. Also, _traits of personality_ (a term that is used interchangeably with emotions) are important for the maintenance of objectives and collaboration [6]. Using these ideas, we can define a way robots may react to their environment [7, 9].

In our problem, the robots are assumed, initially, to be homogeneous in configuration and capabilities (understood as the set of traits of personality available to each one of them). However, like ants in a colony, they should differ from each other in order to better perform a complex task. But we do not want to add complexity to our algorithms. In order to solve this dilemma, we make use of personality traits. Therefore, the algorithms are the same for every robot, but changing these numerical values (the "traits") will change the behavior of individual robots. Although simple, this idea is very powerful and, when combined with reinforcement learning, may lead to a heterogeneous population in which some robots are able to specialize in executing certain tasks but at the same time they may learn how to execute a different action if it becomes necessary.

Personality traits are represented by real numbers  . They are used in order to represent the individual intentions when faced with changes in the environment. The choice of actions is made considering the traits of personality a robot has and the payoffs related to each action at a given moment in time. Notice that the payoffs may change according to a change in the representation of the environment. We may give a human example to explain that. In our diet we usually would not consider eating worms. However, if we were lost in a jungle, we would do anything that would keep us alive. In the same way, a robot can change the values of its payoffs if the environment as it perceives it changes. Thus, the payoffs or rewards are dependent on the personalities of the robots.

* * *

### Definition 6.1

For a player  , we define the personality traits to be

**6.4**

and the reward functions defined for each one of the   personality traits are represented by the vector

**6.5**

* * *

However, in this section we are going to drop the subscript  , since the algorithm to be introduced in the next section will be explained for just one robot.

The reward functions   represent how well a personality trait contributes to the success of the robot. These functions are arbitrary and defined based on the problem under consideration [9]. When an action   is chosen to be executed, all personality traits   are then updated. The effect of the action taken is evaluated using the equation

**6.6**

where the individual reward functions   are related to how beneficial for the robot the execution of action   in the presence of state   is according to each personality trait   and, therefore, determines the reward and/or penalty related to the trait of personality. Function   is a suitably defined function that weights the cost function inside the summation in a way particular to each problem under consideration. Notice that the reward functions   are some feedbacks from the environment. Since there could potentially be more robots acting on the environment, the reward that one particular robot gets depends indirectly on the actions taken by the other agents present. Furthermore, we assume that the weights   (i.e., the personality traits) are normalized, so

**6.7**

However, notice that the personality traits vector   is not a probability vector. In other words,   is not the probability of the robot to take action  . Indeed, the dimension of the personality traits vector and the number of actions are, in general, not the same.

Equation (6.6) takes into account all the traits of personality   and the environment as represented at time   (the current time step). Moreover, action   is the action under consideration and   is the state that the robot perceives the environment to be in at time  .

Furthermore, some procedure for evolving the personalities is necessary. The main purpose of that is to diminish the dilemma between stability and adaptability (plasticity) of learning.

The dynamics of the personality vector are described by the following general difference equation

**6.8**

where the function   depends on the application under consideration.

Equation (6.8) implies, because the utility function is a function of all personality traits, that each trait of personality influences the others (notice that the term   may include the reward functions for all the other personality traits). Therefore, changing a single trait will affect all the others. Furthermore, since the utilities include the actions of all other players (as explained above), the utilities and actions of other players also influence how the personality traits for one robot change.

The implementation of swarm-based robotics in terms of personalities is a very promising research topic. The implementation of such a technique is straightforward. It may also be shown that such a procedure results in coordination among a large number of robots [10].

In the following sections, some applications of the ideas presented so far are presented. Game theory and swarm intelligence are linked in the solution of some problems that may be related to multiple robotic environments, and algorithms and heuristics based on the idea of personality traits will be developed.

## 6.5 Evolution of Personality Traits

Swarm robotics has been defined by Sahin as _the study of how a large number of relatively simple physically embodied agents can be designed such that a desired collective behavior emerges from the local interactions among agents and between the agents and the environment_ [11]. In our approach, we use a looser definition in what concerns the term _desired_ collective behavior. We are more interested in what Beni [12] called _unpredictability_ of the system. In other words, we are interested in the patterns and behaviors that will arise from the group interactions.

In practice, swarm intelligence is not intended to generate a rational individual entity as classical artificial intelligence proposes [1]. However, through investigation of simple computational models that may be implemented in simple machines, swarm intelligence tries to explore how complex tasks might be performed by a social entity because of behaviors that are not directly predicted by the particular characteristics of each individual [13]. For example, if we have a society with a majority of peaceful agents, when some aggressive individuals enter the community, we cannot say that the majority will make the new individuals become peaceful. It is our purpose to try to predict such behaviors through modeling and simulation in order to justify techniques that may be used in a swarm-based robotic environment.

In order to observe the emergence of group behaviors, we rely on the concept of "personality traits" [6, 7]. Using the adaptation of personality traits discussed, the underlying behavior of each robot changes, and by changing each robot's behavior the group's behavior also changes [1].

In order to demonstrate the ideas presented so far, we introduce three simulations that incrementally become more complex and together show how powerful is the approach suggested. We start, in Section 6.6, with a description of the general framework for simulation. In Section 6.7, we introduce a simulation of a zero-sum (matrix) game wherein no saddle point exists and therefore mixed strategies must be used. A theoretical proof of convergence is given, and the theoretical optimal solution is compared with the results obtained by the learning procedure presented in this chapter. In Section 6.8, we define some concepts that will be used in the solution of the problems presented in the following sections. Section 6.9 presents a more complex application than the one discussed in Section 6.7. In this section, we model a robotic conflict using a non-zero-sum game. Moreover, this time, we will have more players (three robots) and the reward will not only be the payoff table but a combination of payoffs and goal achievement. There is no proof of convergence for this case, and its existence is an open question. The results shown are based on heuristics. In Section 6.10, we introduce a situation in which the robots do not perceive the environment completely. Therefore, we will make use of potential fields for the representation of the environment and a still more complex learning procedure. This is also an open problem. However, the results are very promising. Finally, Section 6.11 concludes the chapter with a discussion of all simulations, bringing them together in a detailed manner.

## 6.6 Simulation Framework

All the simulations presented in this chapter will follow a single framework. However, the meaning of some of the terms will change as we go forward in considering more complicated situations. The general framework is described in Algorithm 6.1.

For each of the simulations presented in this chapter, the steps in Algorithm 6.1 could be expanded as needed. Specially, in the simulations shown in Section 6.10, each of the steps above is implemented as a series of several items in the algorithm.

## 6.7 A Zero-Sum Game Example

The game that we will analyze in this section is reported in Reference [14] and is represented in Table 6.1. This is a zero-sum game, meaning that the payoffs for each player always add to zero. For example, if player A plays the strategy A1 and player B plays the strategy B1, player A gets rewarded 4 units while player B gets a penalty of 4; whereas if player B decides to play strategy B2, then player B gets a reward of 4 units while player A gets penalized 4 units.

**Table 6.1** Zero-sum game example.

|  | B1 | B2 | B3 | B4 | B5 | B6  
---|---|---|---|---|---|---|---  
Player A | A1 | 4 |   | 3 | 2 |   | 3  
| A2 |   |   |   | 0 | 0 | 4  
strategies | A3 |   | 2 | 1 |   | 2 |

As may be seen from Table 6.1, there is no saddle point for the game, therefore there must be a mixed strategy set for both players. The optimal strategies, calculated using a linear programming solver such as the simplex method, for both players, are shown in Table 6.2.

**Table 6.2** Optimal mixed strategies.

Player | Strategy | Optimal frequency (%)  
---|---|---  
Player A | A1 |    
| A2 |    
| A3 |    
Player B | B1 |    
| B2 |    
| B3 |    
| B4 |    
| B5 |    
| B6 |

### 6.7.1 Convergence

A general proof of convergence of strategies (or actions) to a Nash equilibrium is virtually impossible to be obtained for Eq. (6.8) of Section 6.4 or, equivalently, for the algorithm presented in Section 6.6. Therefore, we now provide a proof of convergence for the special case of zero-sum games.a Our proof will follow closely the one found in Reference [15]. However, one fundamental difference exists. Since we use personality traits, the strategies' dynamics depend on them and additional considerations must be made. Therefore, personality dynamics are introduced in order to derive the strategies dynamics.

For a zero-sum game, the utility functions for the two players involved would be

**6.9**

**6.10**

where   and   are arrays of probabilities where   is the probability that strategy   for player   be executed. The matrix   is the payoff matrix for both players. For the simulation at hand, matrix   is

**6.11**

In order to proceed with our proof, we need to define some notations. This is done in the following definition.

* * *

### Definition 6.2

Consider  , where   represents the number of strategies.

  *   denotes the simplex [16] in   (Fig. 6-2), that is

  *   is the set of interior points of a simplex [16], that is

  *   is the boundary of the simplex [16] (Fig. 6-2), that is

  *   is the  th vertex of the simplex  , that is

* * *

**Figure 6-2** Simplex of a player with two strategies. Reproduced from [21] © S. Givigi and H. M. Schwartz.

Now we define the best response mappings as

**6.12**

**6.13**

The utilities in (6.9) and (6.10) are implementations of the utility function (6.6). We also need to define the reward functions related to each personality trait (the functions  ) and the function used to update the personality traits (function   used in (6.8)) for each of the players. Note that the arguments for the utility functions are apparently different from the parameters found in (6.6); however, the parameters are embedded in the definitions of   and  , because they are dependent on   and  , respectively (6.15). Function   is the identity.

Let us now define the concept of empirical frequency (expectation of the opponent executing each of its actions). The empirical frequency   is calculated as the running average [15] of the observed actions of the opponent (recall that we have access to the action the opponent has played at each time step)

**6.14**

where   is the action executed by player   at time step   and   is a vertex of the simplex as defined in Definition 6.2. We may assume that as  ,  . Therefore, in the proof we are going to use both termsinterchangeably.

Let us define a mapping from the personality space to the strategy space   as

**6.15**

Notice that   transforms from personalities to likelihood of actions. We can now define the reward functions for each personality trait, defined as (for each player)

**6.16**

**6.17**

where   and  . These reward functions make use of the pseudo-inverse and are used in the convergence proof. In our example (with matrix   defined in (6.11)),   strategies and   strategies. Therefore, we select   personality traits and   personality traits. Notice that according to (6.16) and (6.17)   and  . Moreover,   and  . Other than those, no assumption is made. Furthermore, the functions used to update the personality traits (  in (6.8)) are

**6.18**

The resulting personality dynamics are

**6.19**

In this simulation, we relaxed the condition of normalization presented in (6.7). However, this is just for simplicity of calculations. Had we wanted to do so, this could have been easily implemented. Matrices   and   used were

**6.20**

and

**6.21**

The values of matrices in (6.20) and (6.21) were generated randomly. The point is that, if the matrices satisfy the conditions listed above, the algorithm will converge. More importantly, if   and   are the identity matrices of the necessary dimensions, the algorithm reduces to fictitious play and convergence is still guaranteed [17].

Using these definitions, we find that the strategy dynamics for player   is

**6.22**

In the same way, the strategy dynamics for player   is

**6.23**

We now define a function that measures the maximum possible reward for the players

**6.24**

where   is the best "strategy"b that may be used by player  . Using (6.12), we know that

**6.25**

Therefore, from (6.24), using the definitions of utility functions in (6.9) and (6.10) together with the definition of best response mappings in (6.12) and (6.13), and collecting terms, one gets

**6.26**

In the same way

**6.27**

Finally, we may say that   and   with equality if and only if   and  .

Now we prove that the learning procedure will converge to the optimal solution. We start by the following lemma:

* * *

### Lemma 6.1

Define   and  . Then   and  .

* * *

* * *

### _Proof_

By definition (6.24)

We now use the fact that [18] ([15], Lemma 3.2)

which yields (using (6.22) and (6.26))

Therefore,  . A similar derivation may be used for  , yielding  .

* * *

And, finally, we enunciate the convergence theorem:

* * *

### Theorem 6.1

The solutions of the system of differential equations (6.22) and (6.23) satisfy   and  .

* * *

* * *

### _Proof_

We know from Lemma 6.1 that   and  . Define the function  . Taking its derivative, we have

Since   and   with equality only at the equilibrium point of (6.22) and (6.23),   is a Lyapunov function and the theorem follows the arguments.

* * *

### 6.7.2 Simulation Results

We now present the results for the problem presented in the matrix in (6.11).

Suppose that both players are initialized with personality traits set to random values (in the interval  ). This means that both players start with a random probability of playing each strategy that is different from the optimal one shown in Table 6.2. The question we want to answer is: if we use personalities as described above, will the players learn to play the best mixed strategy? If not, will there be any improvement over time?

Algorithm 6.2 is followed by both players. As described in (6.20) and (6.21), we have created five personality traits for player   and   personality traits for player  . Observe that this is not necessary and we could have used a much larger number of personalities (or, on the other hand, a smaller number greater than or equal to the number of actions) to characterize our player.

The utility functions are defined in (6.9) and (6.10). If we discretize the equation of dynamics for the personality traits ((6.22) and (6.23)), we end up with equations of the form (6.8) where, again, the value   may be called the _learning rate_ and is set to a positive number, and functions   are defined as in (6.18).

We then ran the simulation described in Algorithm 6.2. The loop in line 7 was run for   iterations. We then collected the final probabilities of using each one of the three actions at player  's disposal and each one of the six actions at player B's disposal as well as the value that player   obtained in each simulation (the value obtained by player   is just the negative of the one obtained by player B). The results are summarized in Table 6.3. One may notice that, indeed, the procedure made the personalities converge to their optimal values. Furthermore, we observe that the disadvantageous actions B1 and B3 were almost never used. Moreover, action B5, which is dominated by action B2, was never used. The learning procedure even caught the subtlety with which B2 dominates B5. Furthermore, the average payoff for player B was  , which is very close to the theoretical value of the game,   [14]. Notice that for a zero-sum game the approach reduces to fictitious play. Therefore, convergence to the Nash equilibrium will always occur. This is not the case for the other simulations presented in this chapter.

**Table 6.3** Experimental results obtained for both players.

Player | Action | Optimal frequency (%) | Experimental frequency (%)  
---|---|---|---  
Player A | A1 |   |    
| A2 |   |    
| A3 |   |    
Player B | B1 |   |     
| B2 |   |    
| B3 |   |     
| B4 |   |    
| B5 |   |    
| B6 |   |

## 6.8 Implementation for Next Sections

In the next two simulations, we are going to use the following implementation.

Going back to (6.8), we have to define how the function   will behave. Defining  , where   is the action taken at time   and   the action taken at time  , we define the step as

**6.28**

where   is the number of personality traits of a robot. Now we define the adaptation law as

**6.29**

Equations (6.28) and (6.29) imply, because of the presence of all personality traits in the denominator, that each trait of personality influences the others. Therefore, changing a singular trait will affect the way all the others work. Furthermore, the convergence of (6.29) is highly dependent on the value of the learning rate  : if this is small, the convergence is too slow and the robots take too long to adapt to new situations; if it is too high, the system oscillates a lot around some value before it converges, and when it does, it has a large probability to go to a local maximum (minimum). In our simulations, we use a small value for this term so that we achieve a smooth convergence. Equation (6.29) is in the same form as used in the reinforcement learning literature. More details may be found in Reference [19].

When the state is recognized, the action is chosen according to the formula known as the _randomized strategy_ [19], which is useful for leading the robot to explore new actions and not just exploit a learnt sequence of actions. For completeness sake, we will repeat the next equation, which demonstrates the randomized strategy:

**6.30**

In (6.30),   is the probability that action   will be executed when the state is   in the presence of the personality traits  , where   is a vector of personality traits (as introduced in Section 6.4). The term   is a coefficient that defines how often the robot explores new solutions or exploits the ones it already knows as better ones. When   increases, the probability that the robot explores new choices decreases, and vice versa.   is a temperature parameter inspired in the Boltzmann theory of statistical mechanics. It is desired that, over time,   decreases to diminish exploration [19]. The utility function   is related to the action under consideration and the current state.   is the long-term expected reward and not just the instantaneous one. This means that the decisions the robot takes are based on the expectation to solve the problem (find a target or perform a predefined task) and not just on the instantaneous reward. This difference is implemented in the personalities, because as robots learn over time, they will develop the capability to "predict" the payoffs of their actions. Moreover,   is the number of personality traits. And, finally,   is the number of possible actions that a robot may perform. In all simulations we will use   (i.e.,  ) and  .   means that we do not reduce exploration as time goes by.   means that the robots have a preference for exploitation of already learnt strategies but are also open to exploration [19].

## 6.9 Robots Leaving a Room

Our second simulation is similar to the one introduced and reported in Reference [9]. The setup is as follows: Three robots of 1 unit in diameter are located in a room with dimensions   (corners at  , and  ). There is a door centered at   and with dimensions so that just one robot may pass. Inside the room, there are three robots located at positions  , and  , that is, at a distance 6 units from the door (Fig. 6-3). It is assumed that one robot knows the positions of the other two without any noise, and it is also assumed that the robots only move in a straight line from their initial position toward the center of the door with a fixed speed, 1 unit per second. The problem may be described as a game shown in Table 6.4, which has the payoffs for player A. The values   and   in the table must follow the rule

**6.31**

where the values of   and   will depend on how the designer chooses to represent the environment. If the designer wants to enhance the action "Walk" for player A, then set  . On the other hand, if the designer wants to enhance the action "Wait," then set  . And finally, if both are considered to be at the same level, set  .

**Figure 6-3** Artistic depiction of the problem of robots leaving a room. Reproduced from [21] © S. Givigi and H. M. Schwartz.

**Table 6.4** Modeling of a game between two robots trying to leave a room.

Player A | Walk |   |    
---|---|---|---  
strategies | Wait |   | 0

Before we state the algorithm, we need to make some definitions.

* * *

### Definition 6.3

Definitions for Algorithm 6.3.

  1. The payoffs for the robots 1 and 3 in Fig. 6-3 are according to the matrix

**6.32**

where   and   (Table 6.4 and Eq. (6.31)). For player 2, the payoff table is

**6.33**

where   and   (Table 6.4 and (6.31)). The values are different such that robot 2's expected reward is greater than its expected penalty.
  2. The probability for a robot to move is given by

**6.34**

where   is related to action  , that is, "Walk," and   is related to action  , that is, "Wait."

* * *

The results were obtained after   repetitions of the game with a learning rate  . First of all, one of the robots on the sides (robots   and  ) converged to a purely "cooperative" robot, that is, its personality trait for waiting for the others became  ; whereas the other robot on the side converged to a purely "competitive" robot, that is, its personality trait for always walking became  . Second, the robot in the middle chooses its actions on a 50/50 basis. As result of all this, the average of the   games is   s to leave the room and the standard deviation is   s. Also,   out of the   repetitions obtained the best solution of   s.

One may notice that the robots did not work only for their own advantage. Table 6.4 shows that the strategy "Wait" is dominated by the strategy "Walk." However, behaving the way they did made the overall result much better for the group. This is one of the interesting results that will be exploited in the next simulation. Here we see the spontaneous emergence of altruistic behavior which enhances the performance of the group. The emergence of altruism is due to the calculations done in steps 13 and 15 of the algorithm. Notice that the matrices in (6.32) and (6.33) do not have a positive payoff for the strategy "Wait." However, since the traits that determine the execution of the actions are normalized (step 15), the negative payoffs that the strategy "Wait" gets combined with the negative payoffs of the collisions when strategy "Walk" is chosen will drive one of the robots to be altruistic.

## 6.10 Tracking a Target

We now make use of all the ideas presented so far and define a more complex and challenging simulation mission to be accomplished by several robots working together. We set up the simulation environment as shown in Fig. 6-4. In this figure, we depict a target (a tank) and several robots that are moving around it. Their objectives are to find the target and go back to the base. In our simulation environment, the position of the target changes from simulation to simulation and the robots perceive the environment as potential fields (Gaussian potential fields). Each single robot is able to identify the target potential field, the other robots' fields, and the base field. No noise is added to the readings, and some delay is possible in the measurements. We also assume that the low-level dynamics of the robots and the control loops necessary to stabilize them are already implemented.

**Figure 6-4** Artistic depiction of the simulation environment. Reproduced from [21] © S. Givigi and H. M. Schwartz.

Each robot has three traits of personality: "courage" ( ), "fear" ( ), and "cooperation" ( ), which influence which action the robot will take. For example, a courageous robot may pursue the gradient of the target, while a cooperative and fearful one may tend to huddle together with other robots in order to look for the target as a group. Again, these behaviors are derived from our assumptions on the definition of the "emotions" of the robots.

For this simulation, the environment is supposed to be in only two states:  , meaning high risk for the robot (of being shot), and  , which means that the robot is in a low risk of being shot. The decision about which state the robot is in is psychological, that is, it depends on the values of traits of personality of each robot. In this way, if a robot is "courageous," high risk has a different meaning compared to a "fearful" robot.

Let   be a function determining the threshold in separating states   and  . Let also   be the trait "courage,"   "fear," and   "cooperation." Define   as the maximum potential field found so far. We then define the probability for the robot to identify the environment as state   (high risk) as

**6.35**

Since the traits of personality are normalized (as explained in the previous sections), we choose the threshold function to be

**6.36**

Therefore, if the trait of personality   (courage) is dominant, the probability the robot will identify the environment as being "high risk" will decrease. On the other hand, since  , the probability increases when "fear" ( ) and "cooperation" ( ) are dominant. Notice that   could be out of the interval  ; if that happens, we simply truncate it.

In the same way, only two actions are possible. We will call them  , which means to follow an uphill approach (getting closer to the dangerous target), and  , which means to follow a downhill path (according to danger). Table 6.5 describes the payoffs related to each decision when the robot identifies the environment to be in each specific state. The values in Table 6.5 are empirical, and by choosing different payoffs the robots would end up with different behaviors. Also notice that the table is not exactly a payoff table as we had in the previous examples; in this case we do not have a conflict among the robots. The numbers in the table mean that, when the robot perceives the state to be in the "high risk" state  , it is more "profitable" to execute action   (downhill path), and when the robot finds itself in the low risk state  , the robot would prefer to execute action   (uphill path). Later on (in Eq. (6.37)), we will see that the choice is not so straightforward, but in general the rules just explained will be applied.

**Table 6.5** Utility payoffs for states.

Actions |   |   | 5  
---|---|---|---  
|   | 4 |

After the robot identifies the target, it gets back to the base with its estimation of the target location. The closer the robot gets to the target, the greater the danger of being shot (at each time step we divide the potential field where the robot is by the maximum value of the field-, the position of the target, and according to this number, randomly shoot at the robot simulating an action taken by the enemy). When the robot is shot, we assume that it is still operational, but has to go back to the base in order to avoid malfunctioning. Actually, since we may have a large number of robots, this assumption is not necessary, but by making use of it we simplify our simulation environment. When the robot is shot, we artificially increase its "fear" trait of personality in order to avoid being shot in the future. The task "get back to base" is hardwired in this approach, and after the robot identifies the target it just follows the track back to safety. Notice that this behavior is artificial and not desired, because the robot must be able to help other robots in need even if it is on its way back to the base. However, we do not implement this feature for the sake of simplicity.

The traits of personality are defined as follows:

  1. Courage ( ): the robot goes in the direction of danger, that is, in the direction of the increasing potential field, therefore, this trait makes it more likely for the robot to identify the environment as in the "low risk" state (state   in Table 6.5).
  2. Fear ( ): the robot goes in the opposite direction of danger, that is, in the direction of the decreasing potential field, therefore, this trait makes it more likely for the robot to identify the environment as in the "high risk" state (state  ).
  3. Cooperation ( ): robots tend to huddle together in order to decrease the possibility of being shot. This trait makes the robots work together.

The behavior in (3) is explained by the assumption in the simulation that the chance of the robot being shot is inversely proportional to the number of robots huddled together. This is not a deliberate hypothesis; in fact, the same assumption has been made when studying the formation of patterns of animals in the wild (flock formation, fish schooling, etc.) [20].

To choose an action, we use the value function   in (6.37) which maps the state of the environment and the action under consideration to a reward. In the case of game theory, we need to calculate the expected value of the value function. Therefore, define  , that is, the summation in (6.6). Now, define   as the expected value for the payoff for all possible actions  . We can think of this as a game against Nature [14], in which the environment is supposed to play with a mixed strategy  . Therefore, the expected outcome of the game in Table 6.5 is

**6.37**

Equation (6.37) is the application of game theory expectation calculation to the framework introduced in Section 6.4. Actually, this equation is just the implementation of (6.6) in terms of game theory, where   is the expectation function.

Then, the action is chosen randomly based on the probability (6.30), where   ( ,  ):

**6.38**

Before we state the algorithm, we need to introduce some definitions:

* * *

### Definition 6.4

Definitions for Algorithm 6.4.

  1. The target is identified by a Gaussian field. If   designates the position of the target, let

be the Gaussian field irradiated by it.   is the standard deviation of the field and   is a term to scale the sensitivity of the robots.
  2. The robots also irradiate Gaussian fields. If   is the position of a robot, let

be the Gaussian field around it.   is the standard deviation of the field.
  3. The uphill unit vector for robot   located at   is

**6.41**

  4. The downhill unit vector for robot   located at   is

**6.42**

  5. The probability for the robot identifying that it is in state   (high risk) is

**6.43**

where   is the maximum field found so far for each robot. Accordingly, the probability to be in state   (low risk) is

**6.44**

  6. The probability of executing action   is

**6.45**

Accordingly,  . Equation (6.45) is (6.30), where  ,  , and  .
  7. The personality traits are updated using the adaptation law

**6.46**

where

**6.47**

  8. The probability of a robot being shot is

**6.48**

where   are all the points visited by the robot previously.

* * *

As stated in Algorithm 6.4, the choice for the reward functions   is dependent on the application. It may be argued that the reward functions would have to include some kind of external payoff based on the success of the task. However, this is not considered in the model of Algorithm 6.4.

The interpretation of the reward functions used in Algorithm 6.4 is as follows:

  *   is the function for the personality trait  , "courage." For action   "follow the uphill gradient," the reward is  . Notice that this value is positive if the angle between the gradient   and the uphill unit vector   is in the interval   and negative otherwise. For action  , "follow the downhill gradient," the reward is  . Notice that this value is positive if the angle between the gradient   and the downhill unit vector   is in the interval   and negative otherwise. In other words, the personality trait "courage" returns a larger value if the direction of the movement is closer to the gradient of the target. Since   and   are constituted by a summation of the gradient of the target and the gradients of the robots (Eqs.(6.41) and (6.42)), the direction that is closer to the danger is preferred.
  *   is the function for the personality trait  , "fear." For action   "follow the uphill gradient," the reward is  . Notice that this value is positive if the angle between the summation of gradients   and the uphill unit vector   is in the interval   and negative otherwise. For action  , "follow the downhill gradient," the reward is  . Notice that this value is positive if the angle between the summation of gradients   and the downhill unit vector   is in the interval   and negative otherwise. In other words, the personality trait "fear" returns a larger reward for the action that moves the robot closer to other robots.
  *   is the function for the personality trait  , "cooperation." For both actions, the reward is calculated as  , for   where   is the future position of the robot. Let   be the robot's current position and   the speed of the robot, which in our case is 1 unit per second. For action   "follow the uphill gradient," the reward function   is evaluated at  . For action  , "follow the downhill gradient," the reward function   is evaluated at  . The personality trait "cooperation" assumes that when the robot moves closer to other robots, the survival of the groups is enhanced.

Indeed, the concept of success in the definition of reward functions is very subjective. Depending on the information we have available and the complexity of the model we establish, success would have a completely different meaning. For example, with the same setup of Algorithm 6.4 we may assume that the robots know where the target is, and the task could be just to get close to it. In this case, the reward functions   could include external information on how dangerous the environment becomes at each step, say how close a shot came to hit the robot, or how close we got to the target. Notice that in Algorithm 6.4 we did not assume that this information was available.

Since we chose a low value for the learning rate ( ), it is expected that there will be a slow convergence of the traits of personality to a steady-state value. Results for one arbitrarily chosen robot are depicted in Fig. 6-5. This figure indicates that the traits of personality do converge to a steady-state value. In this figure, the value function is  , where   is the action executed at time  . Notice that the value function varies around some range (this is not necessarily the case; until further proof, this should be taken as a particularity of the simulation analyzed). We may notice that the robot becomes a "fearful" robot (  increases, while the other traits decrease). Therefore, we may hypothesize that this particular robot is in some kind of cluster of robots, which makes variations on the cost functions for the particular traits more difficult. Moreover, the particular values of the personalities are characteristic of the one simulation at hand. If we had a different initialization, we could get to different steady-state values for the traits of personality, since the environment changes considerably as well as the robots' initial conditions (the initial values for the traits of personality). Table 6.6 shows that in a given run all the robots do converge to a steady-state value and they are related to each other. This is not necessarily true for different payoff tables (like Table 6.5) and reward functions ( ) and must be considered (until further proof) as a particularity of the simulation setup under analysis.

**Figure 6-5** Utility function and personality traits of one robot. Reproduced from [21] © S. Givigi and H. M. Schwartz.

**Table 6.6** Convergence of the personality traits.

| Courage ( ) | Fear ( ) | Cooperation ( )  
---|---|---|---  
Number of |  | Standard |  | Standard |  | Standard  
robots | Average | deviation | Average | deviation | Average | deviation  
10 | 0.1648 | 0.1377 | 0.1158 | 0.1435 | 0.7194 | 0.2743  
20 | 0.2451 | 0.1006 | 0.2381 | 0.1713 | 0.5167 | 0.2316  
30 | 0.1299 | 0.0930 | 0.3066 | 0.1827 | 0.5636 | 0.1692

In order to evaluate the quality of the simulations, we measure the quality of the target location by the robots. When the  th robot goes back to base, it records the position   where it was shot (recall, we suppose that the robot just goes back to base when it is shot). Therefore, if   is the actual position of the target, the error of the best target location is  , where   is the number of robots in the simulation. We also measure the total time it takes for all the robots to get back to base and the average location error for all robots in the simulation. The results are shown in Table 6.7, wherein we give the average and standard deviation of the target location error, total time of the missions, and average location error for all robots. All the results are obtained through 10 executions of the target-tracking mission.

**Table 6.7** Simulation results.

| Target location error | Total time | Location error for all robots  
---|---|---|---  
Number of |  | Standard |  | Standard |  | Standard  
robots | Average | deviation | Average | deviation | Average | deviation  
10 | 12.2000 | 6.5201 | 93.3000 | 55.6698 | 17.3810 | 7.7339  
20 | 9.5880 | 3.8975 | 136.1000 | 45.4715 | 15.5337 | 5.4713  
50 | 8.4136 | 3.9315 | 322.5000 | 117.8740 | 15.3012 | 5.5135

The results indicate that the behaviors of some robots are independent of the number of robots in the fleet. There is also a tendency to get a better location of the target with increasing number of robots. This is due to our assumption that the robots are less likely to get shot when they are in larger numbers (Eq. (6.48)) because of huddling together, which has been observed in the simulations. In fact, in order to visualize better the effect of the other robots in how a robot decides to act, we considered the enemy (the tank) to be more accurate and replaced (6.48) by

**6.49**

That is, the robots are   times more likely to be shot than predicted in the algorithm (therefore the probability is multiplied by   instead of  ). Also, the presence of other robots in the neighborhood makes it more unlikely for a robot to be shot (this is the meaning of the factor   in the equation above). In this way, robots will take advantage of the increase in the number of robots in the neighborhood. Table 6.7 also indicates that, as the number of robots increases, the total time for target location also increases, although not linearly. This happens for two different reasons: First, the robots take longer to leave the base (we assume that just one robot leaves the base at each time step). Second, as we have a larger number of robots, the chance of being shot decreases (again, (6.49)) and, therefore, they take much longer to get back to base.

When we use the probability in (6.48) (as in the simulation illustrated in Fig. 6-5), the traits "fear" and "cooperation" are always more important, giving rise to the most interesting behavior observed in the simulation, namely the tendency for the robots to huddle together. In most simulations, they formed a big group and kept as such until the individual robots were being shot by the enemy. This may also be seen in Table 6.7 because, as we increase the number of robots, the average distance to the target slightly decreases. This is also a result from the emergent huddling behavior. Figure 6-6 shows a picture of the state of the robots in the simulation. We can see that the robots do huddle together, but some of them (the more courageous ones) move farther from the center of the swarm. However, they are more likely to be shot (a result seen from (6.48)).

**Figure 6-6** State of the robots during the simulation. Reproduced from [21] © S. Givigi and H. M. Schwartz.

Another aspect observed in the simulations was the behavior of robots after some of them were shot. Observe that, since the number of active robots decreases, the reward   for the personality trait  , "fear," calculated in step 19 of Algorithm 6.4, and   for the personality trait  , "cooperation," calculated on step 20, decrease. Therefore, the reward   for the trait of personality  , "courage," gets more important for the remaining robots and they tend to "attack" the target more directly. This was a behavior observed when just some few robots were left. Since there is no other robot to help them, the remaining robot takes more risks and move toward the target, thereby increasing the risk of being shot.

In order to examine how resilient to spurious behaviors the swarm was, we fixed some robots as courageous and ran the simulation again. The idea was to check out when the group would start showing different group behaviors than the ones observed so far. Figures 6.7–6.9 are snapshots of the simulation over the period of time when some robots were set to "courageous." We also reduced the probability of getting shot even more, to just   of the value in (6.49). Figure 6-7 shows the state of the simulation when   out of   robots were made courageous. It does not look very different from the state of the simulation in Fig. 6-6. Figure 6-8 shows the state of the simulation when   out of   robots were made courageous, and Fig. 6-9 shows the state of the simulation when   out of   robots turned courageous. We see that in Fig. 6-8 the group of robots start to break and, in Fig. 6-9, when half the robots turn courageous, the group of robots is completely broken. This suggests that the swarm of robots is resilient to outlier individuals up to some limit, but as the number of robots with some specific trait of personality increases, the swarm dynamics can dramatically change. In the cases depicted in Figs. 6.7–6.9, we see that, when more robots become courageous, they drive the entire group to a courageous state. We note that for this behavior to become noticeable we artificially and arbitrarily should set for the courageous robots the trait of personality  , "courage," to   and the other two traits to zero.

**Figure 6-7** State of the simulation when two robots turned courageous. Reproduced from [21] © S. Givigi and H. M. Schwartz.

**Figure 6-8** State of the simulation when five robots turned courageous. Reproduced from [21] © S. Givigi and H. M. Schwartz.

**Figure 6-9** State of the simulation when 10 robots turned courageous. Reproduced from [21] © S. Givigi and H. M. Schwartz.

The last interesting behavior that we want to discuss is how some robots turn around and follow other more courageous robots, that is, they wait until the courageous robots take the lead and then follow them. Figure 6-10 shows one robot that turned back and is waiting until a more courageous one passes by so it may follow the latter. The reason why this happens is that the traits of personality "fear" and "cooperation" are much bigger than the trait "courage." Therefore, the robot is (a) afraid of being shot and (b) wanting to share the risk with other robots.

**Figure 6-10** Robot waiting for a more courageous robot. Reproduced from [21] © S. Givigi and H. M. Schwartz.

## 6.11 Conclusion

This chapter has presented a unique method of modeling and controlling a swarm of robots. It integrates ideas from game theory and incorporates the novel use of adaptive personality features to achieve an intelligent swarm. Three different simulations have been presented. Each simulation scenario highlights a different aspect of swarm intelligence using game theory and adaptive personalities.

The first simulation illustrated how two agents or robots can play a zero-sum game and how the agent/robot personalities would converge to the Nash equilibrium. A proof of convergence theoretically validated the method. The second simulation is an example of three robots that must cooperate in leaving a room. We showed how the proposed method could achieve optimal performance. Furthermore, one robot converges to the "always walk" condition, another converges to the altruistic "always wait" condition, and the third converges to the mixed 50% wait and 50% walk strategy.

The third simulation illustrated how the proposed method could be used to locate a target. The effect of different robot personalities on the performance of the swarm was shown. Cooperative robots tend to huddle into a tight swarm, whereas more courageous robots leave the swarm and lead the pack. We also demonstrated that the swarm was resilient to spurious individuals. By fixing some individuals as "aggressive," we showed that it takes up to half of the swarm to change the resulting group behavior. This is an important result because malfunctioning robots must be dealt with.

## References

  1. [1] E. Bonabeau, M. Dorigo, and G. Theraulaz, _Swarm Intelligence: From Natural to Artificial Systems_. New York, New York: Oxford University Press, 1999.
  2. [2] P. P. Grassé, "La Reconstruction du nid et les Coordinations Inter-Individuelles chez Bellicosistermes Natalensis et Cubetermes sp. La théorie de la Stigmergie: Essai d'interprétation du Comportement des Termites Constructeurs," _Insectes Sociaux_ , vol. **6** , pp. 41–80, 1959.
  3. [3] M. Mamei, F. Zambonelli, and L. Leonardi, "Cofields: a physically inspired approach to motion cordination," _IEEE Pervasive Computing_ , vol. **3** , no. 2, pp. 52–61, 2004.
  4. [4] R. Chalmers, D. Scheidt, T. Neighoff, S. Witwicki, and R. Bamberger, "Cooperating unmanned vehicles," in AIAA 1st Intelligent Systems Technical Conference, 2004.
  5. [5] J. Borenstein and Y. Koren, "Real time obstable avoidance for fast mobile robots," _IEEE Transactions on Systems, Man, and Cybernetics_ , vol. **19** , no. 5, pp. 1179–1187, 1989.
  6. [6] M. Mynsk, _The Society of Mind_. New York, New York: Simon & Schuster, 1986.
  7. [7] S. N. Givigi and H. M. Schwartz, "A game theoretic approach to swarm robotics," _Applied Bionics and Biomechanics_ , vol. **3** , no. 3, pp. 131–142, 2006.
  8. [8] C. Darwin, _The Expression of the Emotions in Man and Animals_. Chicago, Illinois: University of Chicago Press, 1965.
  9. [9] D. Yingying, H. Yan, and J. Jing-ping, "Self-organizing multi-robot system based on personality evolution," in IEEE International Conference on Systems, Man, and Cybernetics, vol. **5** , 2002.
  10. [10] S. Givigi and H. M. Schwartz, "Evolutionary swarm intelligence applied to robotics," in Prooceedings of the IEEE International Conference on Mechatronics and Automation, pp. 1005–1010, 2005.
  11. [11] E. Sahin, "Swarm robotics: from sources of inspiration to domains of application," in _Swarm Robotics: SAB 2004 International Workshop, Santa Monica, CA, USA, July 17, 2004: revised selected papers_ (E. Sahin and W. M. Spears, eds.), (Berlin, Heidelberg), pp. 10–20, Springer-Verlag, 2005.
  12. [12] G. Beni, "From swarm intelligence to swarm robotics," in _Swarm Robotics: SAB 2004 International workshop, Santa Monica, CA, USA, July 17, 2004: revised selected papers_ (E. Sahin and W. M. Spears, eds.), (Berlin, Heidelberg), pp. 1–9, Springer-Verlag, 2005.
  13. [13] M. Dorigo, V. Trianni, E.  ahin, R. Groß, T. Labella, G. Baldassarre, S. Nolfi, J. Deneubourg, F. Mondada, D. Floreano, and L. Gambardella, "Evolving self-organizing behaviours for a swarm-bot," _Autonomous Robots_ , vol. **17** , pp. 223–245, 2004.
  14. [14] P. D. Straffin, _Game Theory and Strategy_. Washington, District of Columbia: The Mathematical Association of America, 1993.
  15. [15] J. S. Shamma and G. Arslan, "Unified convergence proofs of continuous-time fictitious play," _IEEE Transactions on Automatic Control_ , vol. **49** , no. 7, pp. 1137–1142, 2004.
  16. [16] J. W. Weibull, _Evolutionary Game Theory_. Cambridge, Massachusetts: MIT Press, 1995.
  17. [17] J. Robinson, "An iterative method of solving a game," _Annals of Mathmatics_ , vol. **54** , no. 2, pp. 296–301, 1951.
  18. [18] D. P. Bertsekas, _Dynamic Programming and Optimal Control_. Belmont, Massachusetts: Athena Scientific, 1995.
  19. [19] L. P. Kaelbling, M. L. Littman, and A. W. Moore, "Reinforcement learning: a survey," _Journal of Artificial Intelligence Research_ , vol. **4** , pp. 237–285, 1996.
  20. [20] R. Dawkins, _The Selfish Gene_. New York, New York: Oxford University Press, new ed., 1989.
  21. [21] G. Sidney, "Analysis and Design of Swarm Based Robots Using Game Theory". Ph.D. Thesis, Ottawa, ON: Carleton University, Sept. 2009.

a In the particular case of zero-sum games, the convergence is to a Nash equilibrium. b For a discussion on pure and mixed strategies, refer to [16].

# Index

  1. Autoregressive exogenous (ARX) model
  2. Bellman equation
  3. Bellman optimality equation _see_ optimal state-value function
  4. Channel equalization
  5. Co-fields technique
  6. Defuzzification method
  7. Differential games (DGs) 
    1. definition
    2. evader–pursuer game 
      1. capture radius
      2. capture time
      3. control strategy
      4. eligibility traces
      5. equations of motion
      6. learns to escape
      7. membership functions
      8. pursuer evader dynamics
    3. fuzzy systems _see_ fuzzy inference systems (FISs)
    4. guarding a territory game _see_ guarding a territory game
    5. homicidal chauffeur 
      1. capture time
      2. maximum steering angle
      3. minimum turning radius
      4. problem model
      5. pursuer's _vs._ evader's speed
      6. simulation results
    6. reinforcement learning algorithms
  8. Dirty gradient method
  9. Dynamic programming
  10. Echo cancellation
  11. Evader–pursuer game 
    1. capture radius
    2. capture time
    3. control strategy
    4. eligibility traces
    5. equations of motion
    6. learns to escape
    7. membership functions
  12. Exponential moving-average Q-learning (EMA Q-learning) algorithm
  13. Finite impulse response (FIR) filter
  14. Friend-or-foe Q-learning (FFQ) algorithm
  15. Fuzzification method
  16. Fuzzy actor–critic learning (FACL) algorithm
  17. Fuzzy inference systems (FISs) 
    1. actor–critic learning system 
      1. algorithm
      2. architecture
      3. definition
      4. exploration part
      5. prediction error
      6. random white noise
      7. value function
    2. controller structure
    3. fuzzifier and defuzzifier
    4. fuzzy sets and rules 
      1. crisp/classical set
      2. IF-THEN rules
      3. linguistic labels, MFs
      4. union and intersection operations
    5. product inference engine 
      1. definition
      2. generalized modus ponens
      3. intersection and union operators
      4. Mamdani implication
      5. output
      6. structure
    6. Q-learning 
      1. algorithm
      2. estimation error
      3. global continuous action
      4.  -greedy policy
      5. IF-THEN rules
      6. Nash equilibrium strategy
      7. _q_ -function
      8. state/action space
      9. TS rules
    7. Q( _λ_ )-learning 
      1. action-value function
      2. agent's goal
      3. algorithm
      4. construction
      5. learning rate
      6. pursuer's fuzzy decision table
    8. universal approximation theorem 
      1. error estimation
      2. first-order nonlinear system
      3. IF-THEN rules
      4. MFs
      5. nonlinear function
      6. seven fuzzy sets
      7. system dynamics
  18. Gradient ascent (GA) algorithm 
    1. joint strategy
    2. matching pennies game
    3. mixed strategy game
    4. payoff function
    5. pure strategy games
    6. 2 _×_ 2 zero-sum matrix game
  19. Guarding a territory game 
    1. FQL and FACL algorithms
    2. fuzzy controller
    3. fuzzy reasoning strategy
    4. game value
    5. one defender _vs._ one invader 
      1. average performance error
      2. defender's initial positions
      3. discrete action set
      4.  -greedy policy
      5. membership functions
      6. NE action strategy
      7. NE invader strategy
      8. reinforcement learning
      9. terminal state
      10. training trial
    6. optimal strategy
    7. overview
    8. payoff
    9. practical application
    10. reward shaping
    11. simulation
    12. two defenders _vs._ one invader 
      1. FACL algorithm
      2. invader's reachable region
      3. performance error
      4. shaping reward functions
  20. Homicidal chauffeur game 
    1. capture time
    2. maximum steering angle
    3. minimum turning radius
    4. problem model
    5. pursuer's _vs._ evader's speed
    6. simulation results
  21. Information matrix
  22. Lagging anchor algorithm
  23. Least mean squares (LMS) approach 
    1. channel dynamics
    2. cost function
    3. dirty gradient method/stochastic gradient method
    4. error signal
    5. FIR filter
    6. Newton–Raphson method _vs._ RLS algorithm
    7. steepest descent method
    8. variance
    9. Wiener solution
  24. Least squares (LS) algorithm 
    1. ARX model
    2. cost function minimization
    3. information matrix
    4. operating conditions
    5. prediction error
    6. scalar cost function
    7. two-dimensional linear regression fit
    8. white noise term
  25. Lemke–Howson algorithm 
    1. payoff matrix
    2. reward function
    3. simplex method
    4. two-player two-action game
  26. Linear programming 
    1. matching pennies game
    2. minimization/maximization problem
    3. probability distribution
    4. revised matching pennies game
    5. 2 _×_ 2 zero-sum matrix game
  27. Linear reward–inaction ( _L_ _R_ − _I_ ) lagging anchor learning algorithm 
    1. asymptotic behavior
    2. equilibrium point
    3. linearization matrix
    4. Nash equilibrium 
      1. in fully mixed strategies
      2. in pure strategies
    5. ODE
    6. Routh–Hurwitz stability criterion
    7. simulation
  28. Linear reward–penalty ( _L_ _R_ − _I_ ) algorithm
  29. Markov decision processes (MDP)
  30. Markov property
  31. Matching pennies game
  32. Membership functions (MFs)
  33. Minimax-Q algorithm 
    1. disadvantage
    2. minimax principle
    3. player's optimal strategy
    4. safe strategy
    5. 2 _×_ 2 grid game 
      1. defender's reward matrix
      2. discount factor
      3.  -greedy policy
      4. implementation
      5. linear programming
      6. MATLAB
      7. minization problem, defender
      8. playing field
      9. _Q_ -values
      10. reward function, defender
      11. reward function, invader
    6. two-player zero-sum stochastic games
  34. Mixed strategy game
  35. Multiagent reinforcement learning (MARL)
  36. Multiplayer stochastic games 
    1. action-value functions
    2. convergence
    3. EMA Q-learning algorithm
    4. FFQ algorithm
    5. fully cooperative game/team game
    6. grid game 1
    7. grid game 2
    8. guarding a territory game
    9. infinite gradient ascent
    10. Lemke–Howson algorithm _see_ Lemke–Howson algorithm
    11. _L_ _R_ − _I_ lagging anchor algorithm
    12. Markov decision process
    13. MARL
    14. minimax-Q algorithm _see_ minimax-Q algorithm
    15. Nash Q-learning algorithm _see_ Nash Q-learning algorithm
    16. PGA-APP
    17. PHC algorithm
    18. rationality
    19. reward function
    20. simplex algorithm
    21. state-specific matrix game
    22. state-value function
    23. transition function
    24. two-player fully competitive game/zero-sum game
    25. WoLF-PHC algorithm
    26. WPL algorithm
  37. Nash equilibrium (NE) 
    1. definition
    2. fully mixed strategy
    3. general-sum matrix game
    4. pure strategy
    5. strict Nash equilibrium
    6. strict Nash equilibrium in pure strategies
    7. WoLF-PHC algorithm
    8. zero-sum game
  38. Nash Q-learning algorithm 
    1. convergence
    2. direct implementation
    3. Hu and Wellman theorem
    4. learning process
    5. state-specific matrix game
  39. Newton–Raphson method
  40. Optimal state-value function
  41. Personality traits 
    1. adaptation law
    2. definition
    3. dynamics
    4. evolution
    5. payoffs
    6. randomized strategy
    7. real numbers
    8. reinforcement learning
    9. reward functions
    10. robots leaving a room 
      1. altruistic behavior
      2. artistic depiction
      3. competitive robot
      4. cooperative robot
      5. game modeling
      6. probability to move
      7. setup
    11. simulation framework
    12. stability and adaptability, learning
    13. tracking a target 
      1. advantage
      2. artistic depiction
      3. control loops
      4. convergence
      5. cooperation
      6. courage
      7. downhill path
      8. executing action
      9. fear
      10. Gaussian fields
      11. interpretation of reward functions
      12. low-level dynamics
      13. objectives
      14. risk states
      15. simulation results
      16. steady-state value
      17. threshold function
      18. uphill approach
      19. utility payoffs
      20. value function
    14. utility function
    15. zero-sum game 
      1. best response mapping
      2. convergence
      3. convergence theorem
      4. empirical frequency
      5. optimal mixed strategies
      6. optimal solution
      7. payoff matrix
      8. personality dynamics
      9. simulation results
      10. strategy dynamics of players
      11. utility functions
  42. Policy hill-climbing (PHC) algorithm 
    1. multiplayer stochastic games
    2. two-player matrix games
  43. Policy iteration algorithm
  44. Prisoners' dilemma game
  45. Pure strategy game
  46. Q-learning 
    1. algorithm
    2. estimation error
    3. global continuous action
    4.  -greedy policy
    5. IF-THEN rules
    6. Nash equilibrium strategy
    7. _q_ -function
    8. state/action space
    9. TS rules
  47. _Q_ ( _λ_ ) learning algorithm
  48. _Q_ ( _λ_ )-learning fuzzy inference system (QLFIS) technique 
    1. action-value function
    2. agent's goal
    3. algorithm
    4. construction
    5. learning rate
    6. pursuer's fuzzy decision table
  49. Recursive least squares (RLS) algorithm
  50. Robots leaving a room game 
    1. altruistic behavior
    2. artistic depiction
    3. competitive robot
    4. cooperative robot
    5. game modeling
    6. probability to move
    7. setup
  51. Rock-paper-scissors game
  52. Routh–Hurwitz stability criterion
  53. Self-tuning regulator
  54. Single-agent reinforcement learning 
    1. action value function
    2. agent–environment interaction
    3. agent's policy mapping
    4. basic structure
    5. Bellman equation
    6. definition
    7. distributed policy
    8. greedy action
    9. learning value functions
    10. Markov property
    11. MDP
    12. myopic algorithm
    13. _n_ -armed bandit problem
    14. optimal state-value function
    15. policy iteration algorithm
    16. pure strategy
    17. state-action value function
    18. TD learning _see_ temporal difference (TD) learning
    19. terminal time
  55. Stage game
  56. Steepest descent method
  57. Stochastic gradient method
  58. Supervised learning 
    1. LMS approach
    2. LS algorithm
    3. RLS algorithm
    4. stochastic approximation
  59. Swarm intelligence 
    1. definition
    2. evolution
    3. swarm robotics 
      1. attractive and repulsive forces
      2. co-fields technique
      3. personality traits _see_ personality traits
      4. resultant force
  60. Takagi–Sugeno (TS) fuzzy system
  61. TD( _λ_ ) learning
  62. Temporal difference (TD) learning 
    1. eligibility traces 
      1. convergence speed
      2. one-step prediction error
      3. _Q_ (λ) learning algorithm
      4. TD(λ) learning
      5. two-step predictor
    2. Q-learning
    3. state-action function
    4. temporal difference algorithm
    5. value of state
  63. Tracking a target game 
    1. advantage
    2. artistic depiction
    3. control loops
    4. convergence
    5. cooperation
    6. courage
    7. downhill path
    8. executing action
    9. fear
    10. Gaussian fields
    11. interpretation of reward functions
    12. low-level dynamics
    13. objectives
    14. risk states
    15. simulation results
    16. steady-state value
    17. threshold function
    18. uphill approach
    19. utility function
    20. utility payoffs
    21. value function
  64. Two-player matrix games 
    1. decentralized learning
    2. GA algorithm _see_ gradient ascent (GA) algorithm
    3. lagging anchor algorithm
    4. learning automation
    5. linear programming _see_ linear programming
    6. linear reward–penalty algorithm
    7. _L_ _R_ − _I_ lagging anchor learning algorithm _see_ linear reward–inaction ( _L_ _R_ − _I_ ) lagging anchor learning algorithm
    8. matching pennies game
    9. mixed strategy
    10. Nash equilibrium (NE) 
      1. definition
      2. fully mixed strategy
      3. general-sum matrix game
      4. pure strategy
      5. strict Nash equilibrium
      6. strict Nash equilibrium in pure strategies
      7. zero-sum game
    11. PHC
    12. prisoners' dilemma game
    13. rock-paper-scissors game
    14. WoLF-IGA algorithm
    15. WoLF-PHC algorithm
  65. Universal approximation theorem 
    1. error estimation
    2. first-order nonlinear system
    3. IF-THEN rules
    4. MFs
    5. nonlinear function
    6. seven fuzzy sets
    7. system dynamics
  66. Value iteration algorithm
  67. Weighted policy learning (WPL) algorithm
  68. Wiener solution
  69. Win or learn fast-infinitesimal gradient ascent (WoLF-IGA) algorithm
  70. Win or learn fast-policy hill climbing (WoLF-PHC) algorithm 
    1. multiplayer stochastic games
    2. two-player matrix games 
      1. expected reward
      2. learning agent _j_
      3. matching pennies game
      4. NE
      5. variable learning rule
  71. Zero-sum game 
    1. best response mapping
    2. convergence
    3. convergence theorem
    4. empirical frequency
    5. optimal mixed strategies
    6. optimal solution
    7. payoff matrix
    8. personality dynamics
    9. simulation results
    10. strategy dynamics of players
    11. utility functions

# WILEY END USER LICENSE AGREEMENT

Go to www.wiley.com/go/eula to access Wiley's ebook EULA. 
