11institutetext: Young Researchers and Elite Club, Mashhad Branch, Islamic
Azad University, Mashhad, Iran

# The specific heat and magnetic properties of a spin-1/2 ladder including
butterfly-shaped unit blocks

Hamid Arian Zad __e-mail<EMAIL_ADDRESS>
###### Abstract

The specific heat, structural characterization, and magnetic property studies
of a new spin ladder with the geometry of butterfly-shaped configuration are
reported. The model introduced here is an infinite spin ladder-type including
spin-1/2 particle for which unit blocks consist of two butterflies connected
together through their bodies (Body-Body bridges). Localized spins on the
wings of butterflies have XXZ Heisenberg interaction with two extra spin-1/2
particles assumed in the center of each cage (unit block), while they have
pure Ising-type interaction with those spins that are localized on the bodies.
Hence, there are six interstitial spins and four nodal spins (Body-Body
interaction) per block. To obtain the partition function of this model, we use
the transfer matrix approach, then we examine the magnetization process, as
well as, the specific heat of the model. Interestingly, we see a wide
magnetization plateau at $\frac{5}{6}$ of the saturation magnetization that is
strongly dependent on the magnetic field and anisotropy variations. Moreover,
some unexpected phenomena are observed in the low-temperature limit, such as
anomalous triple-peak in the specific heat function which gradually turns to a
double-peak upon increasing the magnetic field and/or anisotropic Heisenberg
coupling, due to the ferromagnetic phase predomination.

##  1 Introduction

Obtaining a profound perception about interacting quantum many-body systems
like low-dimensional magnetic materials with competing interactions or
geometrical frustration have become an intriguing research object in a number
of subjects such as condensed matter physics, material science and inorganic
chemistry. In these particular areas many investigations concerned about
quantum ferrimagnetic chains have been carried out, due to that they present a
relevant combination of ferromagnetic and antiferromagnetic phases. As a
result of zero and finite temperature phase transitions, these materials
present various ground states and thermal properties Kitaev ; Gu ;
Dillenschneider ; Ivanov ; Werlang ; Sachdev ; Rojas2 ; RojasM ; Strecka .
Spin ladders can be count as attractive models among these systems. The latter
consist of square-shaped topological units along the ladder Strecka ; Koga ;
Okamoto ; Muller ; Vuletic ; Notbohm ; Buttner ; Blundell ; Bacq ; Arian1 ;
Feng2007 .

During the past two decades it has become possible to synthesize a large
variety of compounds such as $A_{3}Cu_{3}(PO_{4})_{4}$ with $A=Ca,Sr$ Drillon1
, $Cu_{3}Cl_{6}(H_{2}O)_{2}\cdot 2H_{8}C_{4}SO_{2}$ Okamoto1999 ; Okamoto2003
, the ferromagnetic diamond chains in polymeric coordination compound
$Cu_{3}(TeO_{3})_{2}Br_{2}$ Uematsu  and the natural mineral azurite
($Cu_{3}(CO_{3})_{2}(OH)_{2}$) Kikuchi1 ; Kikuchi2 , which can be properly
introduced in terms of Heisenberg spin models. Recently, A. Baniodeh et al.
verified experimentally the ground state as well as low-temperature
thermodynamic properties of material $\big{[}Fe_{10}Gd_{10}(Me-tea)_{10}(Me-
teaH)_{10}(NO_{3})_{10}\big{]}\cdot 20MeCN$ as a saw-tooth spin chain in
detail Baniodeh . Motivated by some compounds such as $Bi_{2}Fe_{4}O_{9}$, F.
C. Rodrigues et al. designed an interesting spin model for one stripe of the
Cairo pentagonal Ising-Heisenberg lattice, then they investigated in detail
zero-temperature phase transition for such model in Ref. Rodrigues .

Quantum phase transitions have been one of the most interesting topics of
strongly correlated systems during the last decade. It is basically a phase
transition at zero temperature where the quantum fluctuations play the
dominant role Arian1 ; Feng2007 ; Saadatmand ; Valverde ; Ananikian2012 ;
Abgaryan1 ; Strecka1 ; Arian2 . Further studies to investigate these quantum
spin models have provided precise outcomes for the ground-state phase
transition in the presence of an external magnetic field, which can be induced
through the exchange couplings Sahoo1 ; Sahoo2 ; Giri ; Hovhannisyan . It is
quite noteworthy that the ground state and thermodynamics of the spin ladders
constituted by higher spins have been particularly examined as well Ivanov ;
Giri .

Magnetization curves of low-dimensional quantum ferromagnets/antiferromagnets
are topical issue of current research interest, in order to they often exhibit
intriguing features such as magnetization plateaus. The spin-1/2 quantum chain
in a transverse magnetic field Hida ; Verkholyak , the spin-1/2 quantum spin
ladder Arian1 ; Cabra , spin-1/2 Ising-Heisenberg diamond chain in a
transverse magnetic field Gu ; Rojas2 ; RojasM ; Ananikian2012 ; Abgaryan1 ;
Strecka1  are a few exactly solved quantum spin models for which magnetization
varies smoothly with rising absolute magnetic field until reaches its
saturation magnetization. For the small quantum spin clusters, V. Ohanyan et
al. investigated general non-commutativity features of the magnetization
operator and Hamiltonian Ohanyan2015 . The specific heat of magnetic materials
has attracted much attention over the past two decades, since it usually
exhibits an anomalous thermal behavior by altering other parameters of the
Hamiltonian such as coupling constants, spin exchange anisotropy and magnetic
field etc. Such a parameter can be typically approximated under a certain
thermodynamic condition by the Schottky theory Strecka ; Karlova2016 . The
associated round maximum of the specific heat, the so-called Schottky peak,
has been experimentally detected in various magnetic compounds Bernu ;
Misguich ; Helton .

In solid state physics and Material science, most of the theoretical
treatments are based on numerical techniques. Hence, an analytical approach to
describe the ground state, magnetic and thermodynamic properties of the
quantum spin systems such as the magnetization and specific heat, is
definitely required. A promising method is the transfer-matrix formalism which
has widely been applied to a number of strongly correlated systems at zero-
temperature, as well as, low-temperature for studying the ground- and low-
lying state properties of spin models. In the present paper, we theoretically
describe how the transfer matrix method can be used to calculate the
thermodynamic properties of a new specie of spin-1/2 ladder with Ising-
Heisenberg interactions.

In the present work, we are going to examine the magnetization and the
specific heat for the interstitial half-spins of a spin ladder-type of
decanuclear spin-1/2 particle cages in the presence of an external magnetic
field at low temperature. The considered ladder with periodic boundary
conditions is shown in Fig. 1. The great motivation to consider such a
particular spin ladder with analytical Hamiltonian is to investigate
theoretically some thermodynamic parameters like magnetization and specific
heat of a so close spin model to real magnetic materials in terms of spin
configuration that exhibits stimulating behaviors against magnetic field at
low temperature.

Figure 1: Schematic structure of a Ising-Heisenberg spin ladder of decanuclear
spin-1/2 particle cages. WB and BB abbreviations denote Wing-Body and Body-
Body interactions, respectively.

The paper is organized as follows. In Sec. 2 we introduce the exactly solvable
model. In Sec. 3, we present the thermodynamic solution of the model with in
the transfer-matrix formalism. In this section, we also numerically discuss
the magnetization and specific heat of the model in the presence of an
external homogeneous magnetic field. Some conclusions and future outlooks are
briefly mentioned in Sec. 4.

##  2 Model and exact solution within the transfear matrix formalism

The Hamiltonian of the spin model shown in Fig. 1 can be expressed as

$\begin{array}[]{lcl}H=\sum\limits_{i=1}^{N}\Big{[}-\sum\limits_{j=1}^{4}{J}_{H}({\bf
S}_{j,i}\cdot{\bf
S}_{j+2,i})_{\Delta}+J_{Is}\big{(}S_{1,i}^{z}S_{2,i}^{z}+S_{5,i}^{z}S_{6,i}^{z}\big{)}\\\
J_{Is}\big{[}(\sigma_{1,i}^{z}+\sigma_{1,i+1}^{z})(S_{1,i}^{z}+S_{2,i}^{z})+(\sigma_{2,i}^{z}+\sigma_{2,i+1}^{z})(S_{5,i}^{z}+S_{6,i}^{z})+\\\
\sigma_{1,i}^{z}\sigma_{2,i}^{z}+\sigma_{2,i}^{z}\sigma_{2,i+1}^{z}\big{]}-g\mu_{B}B_{z}\big{(}\sum\limits_{j=1}^{6}S_{j,i}^{z}+\frac{1}{2}\sum\limits_{j=1}^{4}\sigma_{j,i}^{z}\big{)}\Big{]},\end{array}$
(1)

where $N$ is the number of blocks and

$\begin{array}[]{lcl}({\bf S}_{j,i}\cdot{\bf
S}_{j+2,i})_{\Delta}=S_{j,i}^{x}S_{j+2,i}^{x}+S_{j,i}^{y}S_{j+2,i}^{y}+\Delta
S_{j,i}^{z}S_{j+2,i}^{z},\end{array}$ (2)

corresponds to the interstitial anisotropic Heisenberg spins coupling
${J}_{H}$ and $\Delta$, while the nodal spins localized on the $i$-th rung are
representing by Ising-type exchanges $J_{Is}$. $2S^{\alpha}=\sigma^{\alpha}$
for which ${\sigma^{\alpha}}=\\{{\sigma}^{x},{\sigma}^{y},{\sigma}^{z}\\}$ are
Pauli operators (with $\hbar=1$). ${B}_{z}$ is applied homogeneous magnetic
field in the $z$-direction. The gyromagnetic ratio is taken to be $g=2.42$
($\mu_{B}=1$) in the plots drawn in this paper.

The cornerstone of our further calculations is based on the commutation
relation between different block Hamiltonians $[h_{i},h_{j}]=0$, which will
allow us to characterize the partition function of the ladder under
consideration and represent it as a product over block partition functions
${Z}=Tr\Big{[}\displaystyle\prod_{i=1}^{N}\exp(-\beta h_{i})\Big{]},$ where
$\beta=\frac{1}{k_{B}T}$, $k_{B}$ is the Boltzmann’s constant and $T$ is the
temperature. In the two qubit standard eigenbasis of the composite spin
operators
$\\{\sigma_{1,i}^{z},\sigma_{2,i}^{z},\sigma_{1,i+1}^{z},\sigma_{2,i+1}^{z}\\}$
of the two consecutive rungs of the block $i$, we can consider the following
matrix representation to formulate partition function ${Z}$ as

$\begin{array}[]{lcl}{Z}=Tr\big{[}\langle\sigma_{1,1}^{z}\sigma_{2,1}^{z}|\mathcal{T}|\sigma_{1,2}^{z}\sigma_{2,2}^{z}\rangle\cdots\langle\sigma_{1,N}^{z}\sigma_{1,N}^{z}|\mathcal{T}|\sigma_{2,N+1}^{z}\sigma_{2,N+1}^{z}\rangle\big{]},\end{array}$
(3)

where $\sigma_{j,i}^{z}=\pm 1$, and under the periodic boundary conditions we
have $\sigma_{j,N+1}=\sigma_{j,1}$ . We can figure out the $4\times 4$
transfer matrix $\mathcal{T}$ as follows

$\begin{array}[]{lcl}\mathcal{T}(i)=\langle\sigma_{1,i}^{z}\sigma_{2,i}^{z}|\exp(-\beta
h_{i})|\sigma_{1,i+1}^{z}\sigma_{2i,+1}^{z}\rangle=\\\
\sum\limits_{k=1}^{64}\exp\big{[}-\beta\mathcal{E}_{k}(\sigma_{1,i}^{z}\sigma_{2,i}^{z},\sigma_{1,i+1}^{z}\sigma_{2,i+1}^{z})\big{]}.\end{array}$
(4)

$\mathcal{E}_{k}$ denotes eigenvalues of the unit block Hamiltonian. Since we
seek eigenvalues of the transfer matrix in the thermodynamic limit
$N\rightarrow\infty$, the largest eigenvalue $\Lambda_{max}$ has the most
effect on the thermodynamic properties of the system, whereas other three
smaller eigenvalues are almost effectless and their contribution can be
completely neglected. Hence, the free energy per block can be obtained from
the largest eigenvalue of the transfer matrix (4) as

$\begin{array}[]{lcl}f=-\frac{1}{\beta}\lim\limits_{N\rightarrow\infty}\ln\frac{1}{N}{Z}=-\frac{1}{\beta}\ln\Lambda_{max}.\end{array}$
(5)

Figure 2: Magnetization per saturation value $M/M_{s}$ as a function of
external magnetic field $B/J_{Is}$ for fixed value of $J_{H}=1.5J_{Is}$ and
three different coupling constant $\Delta=0.2J_{Is}$, $\Delta=J_{Is}$ and
$\Delta=2J_{Is}$, at (a) low temperature $T=0.2J_{Is}$, (b) $T=J_{Is}$, and
(c) $T=5J_{Is}$.

##  3 Results and discussion

Now one can utilize the thermodynamic relations to evaluate various quantities
that would be investigated. Specific heat, entropy, and magnetization per
block can be consequently defined as

$\begin{array}[]{lcl}{M}=-\Big{(}\frac{\partial f}{\partial
B}\Big{)}_{T},\quad{S}=-\Big{(}\frac{\partial f}{\partial
T}\Big{)}_{B},\quad{C}=-T\Big{(}\frac{\partial^{2}f}{\partial
T^{2}}\Big{)}_{B}.\end{array}$ (6)

Figure 2 illustrates the magnetic field dependences of magnetization in the
unit of its saturation. Figure 2 (a) demonstrates the magnetization per block
against the magnetic field at low temperature, and Figs. 2 (b) and 2 (c)
display this quantity versus the magnetic field at higher temperatures. It is
quite obvious that the magnetization curve shows an intermediate plateau at
$\frac{5}{6}$ of saturation magnetization . The plateau becomes wider upon
increasing the coupling constant $\Delta/J_{Is}$, namely, for higher values of
$\Delta/J_{Is}$, magnetization jumps from the $\frac{5}{6}-$plateau to the
saturation magnetization at higher absolute values of the magnetic field.
Interestingly, as the temperature increases the plateau gradually disappears
until at high temperature the magnetization behaves as a smooth logarithmic
curve without plateau. It its also noteworthy that with increase of the
temperature the magnetization curves coincide together, in this situation the
spin exchange anisotropy $\Delta/J_{Is}$ acts as a resistance factor of this
coincidence.

Figure 3: The specific heat of the introduced spin ladder as a function of the
temperature for various fixed values of the magnetic field $B=0.1J_{Is}$,
$B=J_{Is}$ and $B=2J_{Is}$, where other parameters are taken as
$\Delta=2J_{Is}$ and $J_{H}=1.5J_{Is}$. The inset displays the temperature
dependence of specific heat in the presence of a weak magnetic field for three
different dimensionless coupling constant $\Delta=0.2J_{Is}$, $\Delta=J_{Is}$
and $\Delta=2J_{Is}$.

Now let us examine the effects of anisotropy $\Delta/J_{Is}$ and the magnetic
field on the temperature dependence of the specific heat. To this end, we
display in Fig. 3 the temperature dependence of the specific heat for the
model under consideration for the several fixed values of the magnetic field.
When the temperature growths from zero the specific heat increases till a
small peak arises ($T<J_{Is}$) in weak magnetic field (red curve). By
inspecting Figs. 2 and 3 and a precise comparing, one can realize that this
peak arises when the magnetization plateau appears. It could be expected that
for very weak magnetic fields ($B\ll J_{Is}$) and/of high anisotropies
($\Delta>2J_{Is}$, for more detail see the inset), the specific heat curve
manifests a Schottky-type maximum that strongly depends on the strength of the
magnetic field. With further increase of the magnetic field, this
thermodynamic quantity exhibits more peaks. Actually, in the presence of the
higher magnetic fields, the specific heat of the model displays a small peak
at finite low temperatures. When the temperature increases, a steep increase
appears where second peak is created, and in turn third peak arises that is
highest peak. The latter peak diminishes upon increasing the magnetic field.
With further increase of the magnetic field the height of such a peak
gradually decreases until becomes smaller than second peak and moves toward
higher temperatures. This phenomenon is in accordance with the ferromagnetic-
antiferromagnetic quantum phase transition. As an outstanding result, here the
specific heat shows three separated peaks that are strongly dependent on the
magnetic field. Besides, first and second peaks undergo considerable changes
under magnetic field variations, as a matter of fact, they merge together upon
increasing magnetic field. These changes in specific heat behavior are
compatible with the magnetic alternations of the system.

The inset of Fig. 3 shows the temperature dependence of the specific heat for
various fixed values of the coupling constant $\Delta/J_{Is}$ in the presence
of a weak magnetic field ($B=0.2J_{Is}$). Obviously, the specific heat curves
coincide at high temperature when a weak magnetic field is applied. At low
temperature, this quantity depicts different behavior with respect to the
coupling constant $\Delta/J_{Is}$ changes. To clarify this point, one can see
that when $\Delta/J_{Is}$ decreases the smallest peak of specific heat curve
gradually disappears, whereas the specific heat resists to keep its larger
peaks. This adventure indicates that the system undergoes one another quantum
phase transition that may occur under this specific thermodynamic condition.
At high temperature the specific heat decreases and gradually goes to zero.

##  4 Conclusions

In this paper, we have theoretically investigated thermodynamic properties of
a new spin ladder-type consisting of spin-1/2 particle cages for which unit
blocks include four pivalate ligands bridge wing-body spin centers within the
butterflies. We consider two extra interstitial half-spins in each cage which
have XXZ Heisenberg interaction with spins localized on the bodies of
butterflies. To do so, we have examined the magnetization process and specific
heat of this model by means of solution within the transfer-matrix formalism.

In terms of numerical investigations, we understood that the magnetization has
a plateau at $\frac{5}{6}$ of the saturation magnetization. This plateau
rigorously depends on the temperature and spin exchange anisotropy.
Furthermore, it has been demonstrated that in the presence of the weak
magnetic fields, the specific heat curve manifests three separated peaks
temperature dependence. Magnetic field and the anisotropy variations can
remarkably alter the shape and the temperature position of these peaks.
Namely, the magnetic field increment (the anisotropy decrement) leads to
vanishing the smallest peak, hence, the specific heat has just a double-peak.
The thermal excitation of low-lying energy causes this anomalous double-peak.
Thus, the specific heat variations with respect to the temperature are in a
good accordance with the low-temperature magnetization response to the
anisotropy and temperature changes, this may indicates the ground-state phase
transition related to the magnetization jump.

Further applications of the method discussed in this paper pave the way to set
and interpret the numerical and analytical expressions for utilizing transfer
matrix formalism in realistic scenarios and comparison of the results with the
experimental data obtained from investigating novel magnetic materials with
the similar spin configuration, which can play an important role to better
understand features of more complicated magnetic materials and their
thermodynamic properties.

## Acknowledgments

H. Arian Zad acknowledges the receipt of the grant from the ICTP Affiliated
Center Program AF-04.

## References

  * (1) G. Vidal, J. I. Latorre, E. Rico and A. Kitaev,  Phys. Rev. Lett. 90, 227902 (2003).
  * (2) B. Gu and G. Su, Phys. Rev. B 75, 174437 (2007).
  * (3) R. Dillenschneider, Phys. Rev. B 78, 224413 (2008).
  * (4) N. B. Ivanov, J. Richter and J. Schulenburg, Phys. Rev. B 79, 104412 (2009).
  * (5) T. Werlang, C. Trippe, G. A. P. Ribeiro and G. Rigolin,  Phys. Rev. Lett. 105, 095702 (2010).
  * (6) S. Sachdev, Quantum Phase Transitions (Cambridge University Press, Cambridge, (2011)).
  * (7) O. Rojas, M. Rojas, N. S. Ananikian and S. M. D. Souza,  Phys. Rev. A 86, 042330 (2012).
  * (8) J. Torrico, M. Rojas, S. M. D. Souza, O. Rojas and N. S. Ananikian, Europhys. Lett. 108, 50007 ( 2014).
  * (9) J. Strecka, R. C. Alecio, M. Lyra and O. Rojas, J. Magn. Magn. Mater. 409, 124 (2016).
  * (10) A. Koga, S. Kumada, N. Kawakami and T. Fukui,  J. Phys. Soc. Jpn. 67, 622 (1998).
  * (11) K. Okamoto, N. Okazaki and T. Sakai,  J. Phys. Soc. Jpn. 71, 196 (2002).
  * (12) M. Muller, T. Vekua and H. J. Mikeska Phys. Rev. B 66, 134423 (2002).
  * (13) T. Vuletic, B. K. Hamzic, T. Ivek, S. Tomic, B. Gorshunov, M. Dressel and J. Akimitsu,  Phys. Rep. 428, 169 ( 2006).
  * (14) S. Notbohm, Spin Dynamics of Quantum Spin-Ladders and Chains, PhD thesis, University of St Andrews, (2007).
  * (15) S. Chen, H. Buttner and J. Voit,  Phys. Rev. B 67, 054412 (2003).
  * (16) S. A. Blundell and M. D. N. Regueir,  Eur. Phys. J. B 31, 453 (2003).
  * (17) O. L. Bacq, A. Pasturel, C. Lacroix and M. D. N. Regueiro,  Phys. Rev. B 71, 014432 (2005).
  * (18) H. Arian Zad and N. Ananikian,  J. Phys. Condens. Matt. 29, 455402 (2017).
  * (19) X. Y. Feng, G. M. Zhang and T. Xiang,  Phys. Rev. Lett. 98, 087204 (2007).
  * (20) M. Drillon, M. Belaiche, P. Legoll, J. Aride, A. Boukhari and A. Moqine,  J. Magn. Magn. Mater. 128, 83 (1993).
  * (21) K. Okamoto, T. Tonegawa and M. Kaburagi and M. Kaburagi, J. Phys.: Condens. Matter. 11, 10485 (1999).
  * (22) K. Okamoto, T. Tonegawa and M. Kaburagi, J. Phys.: Condens. Matter. 15, 5979 (2003).
  * (23) D. Uematsu and M. Sato, J. Phys. Soc. Jpn. 76, 084712 (2007).
  * (24) H. Kikuchi, Y. Fujii, M. Chiba, S. Mitsudo, T. Idehara and T.Kuwai, J. Magn. Magn. Mater. 272, 900 (2004).
  * (25) H. Kikuchi, Y. Fujii, M. Chiba, S. Mitsudo, T. Idehara, T. Tonegawa, K. Okamoto, T. Sakai, T. Kuwai and H. Ohta Phys. Rev. Lett. 94, 227201 (2005).
  * (26) A. Baniodeh, N. Magnani, Y. Lan, G. Buth, C. E. Anson, J. Richter, M. Affronte, J. Schnack and A. K. Powell,  npj Quant. Mater 3, 10 (2018).
  * (27) F. C. Rodrigues, S. M. de Souza and O. Rojas, Annals of Phys. 379, 1 (2017).
  * (28) S. N. Saadatmand, B. J. Powell and I. P. McCulloch, Phys. Rev. B 91, 245119 (2015).
  * (29) J.S. Valverde, O. Rojas and S. M. de Souza, J. Phys.: Condens. Matt. 20, 345208 (2008).
  * (30) N. S. Ananikian, L. N. Ananikyan, L. A. Chakhmakhchyan and O. Rojas, J. Phys.: Condens. Matt. 24, 256001(2012).
  * (31) V. S. Abgaryan, N. S. Ananikian, L. N. Ananikyan and V. Hovhannisyan, Solid State Comm.  203, 5 (2015); V. S. Abgaryan, N. S. Ananikian, L. N. Ananikyan and V. Hovhannisyan, Solid State Comm.  224, 15 (2015) .
  * (32) O. Rojas, M. Rojas, S. M. D. Souza, J. Torrico, J. Strecka and M. L. Lyra,  Physica A 486, 367 (2017).
  * (33) H. Arian Zad and N. Ananikian, J. Phys. Condens. Matt. 30, 165403 (2018).
  * (34) V. M. L. D. Prasad Goli, S. Sahoo, S. Ramasesha and D.Sen, J. Phys.: Condens. Matt. 25, 125603 (2013).
  * (35) S. Sahoo, V. M. L. D. Prasad Goli, D.Sen and S. Ramasesha, J. Phys.: Condens. Matt. 26, 276002 (2014).
  * (36) G. Giri, D. Dey, M. Kumar, S. Ramasesha, and Z. G. Soos,  Phys. Rev. B 95, 224408 (2017).
  * (37) V. Hovhannisyan, J. Strecka and N. Ananikian, J. Phys.: Condens. Matt. 28, 085401(2016).
  * (38) K. Hida, J. Phys. Soc. Jpn. 63, 2514 (1994).
  * (39) T. Verkholyak, J. Strecka, M. Jascur and J. Richter, Eur. Phys. J. B 80, 433 (2011).
  * (40) D. C. Cabra, A. Honecker and P. Pujol, Phys. Rev. Lett. 79, 5126 (1997).
  * (41) V. Ohanyan, O. Rojas, J. Strecka and S. Bellucci, Phys. Rev. B 92, 214423 (2015).
  * (42) K. Karlova, J. Strecka and T. Madaras, Physica B 488, 49 (2016).
  * (43) G. Misguich and B. Bernu, Phys. Rev. B 71, 014417 (2005).
  * (44) G. Misguich and P. Sindzingre, Eur. Phys. J. B59, 305 (2007).
  * (45) J. S. Helton, K. Matan, M. P. Shores, E. A. Nytko, B. M. Bartlett, Y. Yoshida, Y. Takano, A. Suslov, Y. Qiu, J.-H. Chung, D. G. Nocera and Y. S. Lee, Phys. Rev. Lett.98, 107204 (2007).
  * (46) J. A. Sheikh, A. Adhikary, H. S. Jena, S. Biswas, and S. Konar, Inorg. Chem. 53, 1606 (2014).


# Learned Belief Search:
Efficiently Improving Policies in Partially Observable Settings

Hengyuan Hu  Adam Lerer  Noam Brown  Jakob Foerster

###### Abstract

Search is an important tool for computing effective policies in single- and
multi-agent environments, and has been crucial for achieving superhuman
performance in several benchmark fully and partially observable games.
However, one major limitation of prior search approaches for partially
observable environments is that the computational cost scales poorly with the
amount of hidden information. In this paper we present _Learned Belief Search_
(LBS), a computationally efficient search procedure for partially observable
environments. Rather than maintaining an exact belief distribution, LBS uses
an approximate auto-regressive counterfactual belief that is learned as a
supervised task. In multi-agent settings, LBS uses a novel public-private
model architecture for underlying policies in order to efficiently evaluate
these policies during rollouts. In the benchmark domain of Hanabi, LBS can
obtain $55\%\sim 91\%$ of the benefit of exact search while reducing compute
requirements by $35.8\times\sim 4.6\times$, allowing it to scale to larger
settings that were inaccessible to previous search methods.

##  1 Introduction

Search has been a vital component for achieving superhuman performance in a
number of hard benchmark problems in AI, including Go (Silver et al., 2016,
2017, 2018), Chess (Campbell et al., 2002), Poker (Moravčík et al., 2017;
Brown & Sandholm, 2017, 2019), and, more recently, self-play Hanabi (Lerer et
al., 2020). Beyond achieving impressive results, the work on Hanabi and Poker
are some of the few examples of search being applied in large partially
observable settings. In contrast, the work on belief-space planning typically
assumes a small belief space, since these methods scale poorly with the size
of the belief space.

Inspired by the recent success of the SPARTA search technique in Hanabi (Lerer
et al., 2020), we propose _Learned Belief Search_ (LBS) a simpler and more
scalable approach for policy improvement in partially observable settings,
applicable whenever a model of the environment and the policies of any other
agents are available at test time. Like SPARTA, the key idea is to obtain
Monte Carlo estimates of the expected return for every possible action in a
given action-observation history (AOH) by sampling from a belief distribution
over possible states of the environment. However, LBS addresses one of the key
limitations of SPARTA. Rather than requiring a sufficiently small belief
space, in which we can compute and sample from an exact belief distribution,
LBS samples from a learned, auto-regressive belief model which is trained via
supervised learning (SL). The auto-regressive parameterization of the
probabilities allows LBS to be scaled to high-dimensional state spaces,
whenever these are composed as a sequence of features.

Another efficiency improvement over SPARTA is replacing the full rollouts with
partial rollouts that bootstrap from a value function after a specific number
of steps. While in general this value function can be trained via SL in a
separate training process, this is not necessary when the blueprint (BP) was
trained via RL. In these cases the RL training typically produces both a
policy and an approximate value function (either for variance reduction or for
value-based learning). In particular, it is common practice to train
_centralized_ value functions, which capture the required dependency on the
sampled state even when this state cannot be observed by the agent during test
time.

While LBS is a very general search method for Partially Observable Markov
Decision Processes (POMDPs), our application is focused on single-agent policy
improvement in Decentralized POMDPs (Dec-POMDPs) (in our specific case,
Hanabi). One additional challenge of single-agent policy improvement in Dec-
POMDPs is that, unlike standard POMDPs, the Markov state $s$ of the
environment is no longer sufficient for estimating the future expected return
for a given AOH of the searching player. Instead, since the other players’
policies also depend on their entire action-observation histories, _e.g._ ,
via Recurrent-Neural Networks (RNNs), only the union of Markov state $s$ and
all AOHs is sufficient.

This in general makes it challenging to apply LBS, since it would require
sampling entire AOHs, rather than states. However, in many Dec-POMDPs,
including Hanabi, information can be split between the common-knowledge (CK)
trajectory and private observations. Furthermore, commonly information is
‘revealing’, such that there is a mapping from the most recent private
observation and the CK trajectory to the AOH for each given player. In these
settings it is sufficient to track a belief over the union of private
observations, rather than over trajectories, which was also exploited in
SPARTA. We adapt LBS to this setting with a novel public-RNN architecture
which makes replaying games from the beginning, as was done in SPARTA,
unnecessary.

When applied to the benchmark problem of two player Hanabi self-play, LBS
obtains $55\%\sim 91\%$ of the benefit of exact search while reducing compute
requirements by $35.8\times\sim 4.6\times$ depending on the trade-offs between
speed and performance. We also successfully apply LBS to a six- and seven-card
versions of Hanabi, where calculating the exact belief distribution would be
prohibitively expensive.

##  2 Related Work

###  2.1 Belief Modeling & Planning in POMDPs

Deep RL on POMDPs typically circumvents explicit belief modeling by using a
policy architecture such as an LSTM that can condition its action on its
history, allowing it to implicitly operate on belief states (Hausknecht &
Stone, 2015). ‘Blueprint’ policies used in this (and prior) work take that
approach, but this approach does not permit search since search requires
explicitly sampling from beliefs in order to perform rollouts.

There has been extensive prior work on learning and planning in POMDPs. Since
solving for optimal policies in POMDPs is intractable for all but the smallest
problems, most work focuses on approximate solutions, including offline
methods to compute approximate policies as well as approximate search
algorithms, although these are still typically restricted to small grid-world
environments (Ross et al., 2008).

One closely related approach is the Rollout algorithm (Bertsekas & Castanon,
1999), which given an initial policy, computes Monte Carlo rollouts of the
belief-space MDP assuming that this policy is played going forward, and plays
the action with the highest expected value. In the POMDP setting, rollouts
occur in the MDP induced by the belief states111SPARTA’s single agent search
uses a similar strategy in the DEC-POMDP setting, but samples states from the
beliefs rather than doing rollouts directly in belief space..

There has been some prior work on search in large POMDPs. Silver & Veness
(2010) propose a method for performing Monte Carlo Tree Search in large POMDPs
like Battleship and partially-observable PacMan. Instead of maintaining exact
beliefs, they approximate beliefs using a particle filter with Monte Carlo
updates. Roy et al. (2005) attempt to scale to large belief spaces by learning
a compressed representation of the beliefs and then performing Bayesian
updates in this space.

Most recently MuZero combines RL and MCTS with a learned implicit model of the
environment (Schrittwieser et al., 2019). Since recurrent models can
implicitly operate on belief states in partially-observed environments, MuZero
in effect performs search with implicit learned beliefs as well as a learned
environment model.

###  2.2 Games & Hanabi

Search has been responsible for many breakthroughs on benchmark games. Most of
these successes were achieved in fully observable games such as Backgammon
(Tesauro, 1994), Chess (Campbell et al., 2002) and Go (Silver et al., 2016,
2017, 2018). More recently, belief-based search techniques have been scaled to
large games, leading to breakthroughs in poker (Moravčík et al., 2017; Brown &
Sandholm, 2017, 2019) and the cooperative game Hanabi (Lerer et al., 2020), as
well as large improvements in Bridge (Tian et al., 2020).

There has been a growing body of work developing agents in the card game
Hanabi. While early hobbyist agents codified human conventions with some
search (O’Dwyer, 2019; Wu, 2018), more recent work has focused on Hanabi as a
challenge problem for learning in cooperative partially-observed games (Bard
et al., 2020). In the self-play setting (two copies of the agent playing
together), the Bayesian Action Decoder (BAD) was the first learning agent
(Foerster et al., 2019), which was improved upon by the Simplified Action
Decoder (SAD) (Hu & Foerster, 2020). The state-of-the-art in Hanabi self-play
is achieved by the SPARTA Monte Carlo search algorithm applied to the SAD
blueprint policy (Lerer et al., 2020).

There has been recent work on ad-hoc team play and zero-shot coordination, in
which agents are paired with unknown partners (Canaan et al., 2019; Walton-
Rivers et al., 2017; Hu et al., 2020).

##  3 Setting and Background

In this paper we consider a Dec-POMDP, in which $N$ agents each take actions
$a_{t}^{i}$ at each timestep, after which the state $s_{t}$ updates to
$s_{t+1}$ based on the conditional probability
$P(s_{t+1}|s_{t},\mathbf{a}_{t})$ and the agents receive a (joint) reward
$r(s_{t},\mathbf{a_{t}})$, where $\mathbf{a}_{t}$ is the joint action of all
agents.

Since the environment is partially observed each agent only obtains the
observation $o_{t}^{i}=Z(s_{t},i)$ from a deterministic observation function
$Z$. We denote the environment trajectory as
$\tau_{t}=\\{s_{0},\mathbf{a}_{0},...s_{t},\mathbf{a}_{t}\\}$ and the action-
observation history (AOH) of agent $i$ as
$\tau^{i}_{t}=\\{o_{0}^{i},{a}^{i}_{0},...,o_{t}^{i},{a}^{i}_{t}\\}$. The
total forward looking return from time $t$ for a trajectory $\tau$ is
$R^{t}(\tau)=\sum_{t^{\prime}\geq
t}\gamma^{t^{\prime}-t}r(s_{t},\mathbf{a_{t}})$, where $\gamma$ is an optional
discount factor. Each agent chooses a policy $\pi^{i}(\tau^{i})$ conditioned
on its AOHs, with the goal that the joint policy $\pi=\\{\pi^{i}\\}$ maximises
the total expected return $J_{\pi}=\mathbb{E}_{\tau\sim P(\tau|\pi)}R(\tau)$.

Starting from a common knowledge blueprint (BP), i.e. a predetermined policy
that is known to all players, in order to perform search in a partially
observable setting, agents will need to maintain beliefs about the state of
the world given their observations. We define beliefs
$B^{i}(\tau_{t})=P((s_{t},\\{\tau_{t}^{j}\\})|\tau_{t}^{i})$, which is the
probability distribution over states and AOHs, given player $i$’s private
trajectory. Note that in Dec-POMDPs the beliefs must model other agents’ AOHs
as well as the current state, since in general the policies of other players
condition on these AOHs.

In general, the domain of $B^{i}$ (the _range_) is extremely large, but in
Dec-POMDPs with a limited amount of hidden information there is often a more
compact representation. For example, in card games like Hanabi, the range
consists of the unobserved cards in players’ hands. SPARTA (Lerer et al.,
2020) assumed that the domain was small enough to be explicitly enumerated. In
our case, we assume that the beliefs are over private features $f^{i}$ that
can be encoded as a sequence of tokens from some vocabulary:
$f^{i}=\prod_{j}f^{i}_{j}\in\mathcal{V}$. Furthermore, it simplifies the
algorithm if, as is typically the case, we can factor out these private
features from $\tau$ to produce a public trajectory $\tau^{pub}$; then each
$\tau^{i}$ can be specified by the pair $(\tau^{pub},f^{i})$ and $\tau$ by
$(\tau^{pub},f^{1},...,f^{N})$.

LBS is applicable to general POMDPs, which are a natural corner case of the
Dec-POMDP formalism when we set the number of players to 1.

##  4 Method

The starting point for our method is the single-agent search version of SPARTA
(Lerer et al., 2020): Given a set of BP policies, $\pi^{i}$, we estimate
expected returns, $Q(a^{i}|\tau^{i})$, by sampling possible trajectories
$\tau$ from a belief conditioned on $\tau^{i}$:

$Q(a^{i}|\tau^{i})=\mathbf{E}_{{\tau}\sim P(\tau|\tau^{i})}Q(a^{i}|\tau)$ (1)

Here $Q(a^{i}|\tau)$ is the expected return for playing action $a^{i}$ given
the history $\tau$:

$Q(a^{i}|\tau)=\mathbf{E}_{{\tau^{\prime}}\sim
P(\tau^{\prime}|\tau,a^{i})}R^{t}(\tau^{\prime}),$ (2)

where $R^{t}(\tau^{\prime})$ is the Monte Carlo forward looking return from
time $t$.

Whenever the argmax of $Q(a^{i}|\tau^{i})$ exceeds the expected return of the
BP, $Q(a_{BP}|\tau^{i})$, by more than a threshold $\delta$, the search-player
deviates from the BP and plays the argmax instead. For more details, please
see Figure 1 (LHS) and the original paper.

Even though this is single-agent search, in SPARTA this process is costly:
First of all, the belief $P(\tau|\tau^{i})$ is an exact counterfactual belief,
which requires evaluating the BP at every timestep for every possible $\tau$
to identify which of these are consistent with the actions taken by the other
agents. Secondly, to estimate $R^{t}(\tau^{\prime})$ SPARTA plays full
episodes (_rollouts_) until the end of the game.

Lastly, since in Dec-POMDPs policies condition on full AOHs (typically
implemented via RNNs) the games have to be replayed from the beginning for
each of the sampled $\tau$ to obtain the correct hidden state,
$h(\tau^{i}(\tau))$, for all players $i$, for each of the sampled
trajectories, $\tau$.

Figure 1: Comparison of SPARTA (Lerer et al., 2020) and LBS (ours). SPARTA
maintains an explicit belief distribution with an accompanying AOH
$h_{2}^{priv}$ for each belief state. LBS uses an auto-regressive belief model
to sample states from the belief distribution, given the AOH. AOHs do not need
to be maintained for each belief state in LBS since the model only relies on
the public trajectory. Additionally, LBS uses an N-step rollout followed by a
bootstrap value estimate.

Learned Belief Search addresses all of these issues: First of all, rather than
using costly exact beliefs, we use supervised learning (SL) to train an auto-
regressive belief model which predicts $P(\tau|\tau^{i})$. As described in
Section 3, in our setting this reduces to predicting the _private
observations_ for all other players $f^{-i}$, since the public trajectory is
known. We use an auto-regressive model to encode the private observations as
it can be decomposed to sequence of tokens $f^{-i}=\prod_{j}f_{j}^{-i}$. For
scalability, as illustrated in Figure 2 (RHS), the auto-regressive belief
model is parameterized by a neural network with weights $\phi$:

$P_{exact}(f^{-i}|\tau^{i})\rightarrow
P_{\phi}(f^{-i}|\tau^{i})=\prod_{j}P(f^{-i}_{j}|f^{-i}_{<j},\tau^{i}).$ (3)

Secondly, to avoid having to unroll episodes until the end of the game we use
a learned value function to bootstrap the expected return after a predefined
number, $N$, of steps. While this value function in general needs to be
trained via SL, this is not necessary in our setting: Since our BPs are
recurrent DQN agents that learn an approximate expected return via value-
decomposition networks (VDN), we can directly use the BP to estimate the
expected return, as illustrated in Figure 1 (B) :

$R^{t}(\tau^{\prime})\simeq\sum^{t+N}_{t^{\prime}=t}r_{t^{\prime}}+\sum_{i}Q^{i}_{BP}(a^{i}_{BP}|f^{i}_{t+N},\tau^{pub}_{t+N})|\tau^{\prime}.$
(4)

This is a fairly general insight, since RL training in POMDPs commonly
involves centralized value functions that correctly capture the dependency of
the expected return on the central state.

Lastly, we address a challenge that is specific to Dec-POMDPs: To avoid having
to re-unroll the policies for the other agents from the beginning of the game
for each of the sampled $\tau$, LBS uses a specific RNN architecture. Inspired
by other public-private methods (Foerster et al., 2019; Kovařík et al., 2019;
Horák & Bošanskỳ, 2019), we exploit that the public trajectory in combination
with the current private observation contains the same information as the
entire private trajectory and only feed the public information $\tau^{pub}$
into the RNN. The public hidden state $h(\tau^{pub}_{t})$ is then combined
with the private observation $f^{i}_{t}$ through a feedforward neural network,
as illustrated in Figure 2 (LHS).

$\pi(\tau^{i}_{t})\rightarrow\pi(h(\tau^{pub}_{t}),f^{i}_{t})$ (5)

We note that whenever it is possible to factor out the public trajectory, this
architecture can be used. If not, LBS can still be used, but instead for each
sampled $f^{i}$ we would need to reconstruct the entire game from scratch to
obtain the correct model state.

We also point out that in this paper we only consider single player search
where all others act according to the BP. Carrying out search for more than
one player would not be theoretically sound because the trained belief model
would no longer be accurate. Crucially, the learned belief model can only
provide accurate implicit beliefs when the other players are playing according
to the blueprint policy, because the belief model is trained before any agent
conducts search. As a consequence, doing independent LBS for multiple players
at the same time would lead to inaccurate beliefs. As we show later in the
paper, it will lower the performance. Further details, including specific
architectures, of our three innovations are included in Section 5.

Figure 2: (A): Illustration of the public-LSTM network used for the BP policy.
(B): The auto-regressive network for modeling beliefs .

##  5 Experimental Setup

We evaluate our methods in Hanabi, a partially observable fully cooperative
multi-step board game. In Hanabi, the deck consists of five different colors
and five ranks from 1 to 5. For each color. There are three 1s, two 2s, 3s, 4s
and one 5, totaling 50 cards. At beginning of a game, each player draw 5
cards. Each player cannot observe their own cards but instead can see other
players’ cards. Players take turn to move and the goal for the team is to play
cards of each color from 1 to 5 in the correct order to get points. At each
turn, the active player can either play a card, discard a card, or select a
partner and reveal information about their cards. Playing a wrong card will
cause the entire team to lose 1 life token. The game will terminate early if
all 3 life tokens are exhausted and the team will get 0 point. To reveal
information, the active player can either choose a color or a rank and every
card of that color/rank will be revealed to the chosen player. The game starts
with 8 information tokens. Each reveal action costs 1 token and each discard
action regains 1 token. Players will draw a new card after play/discard action
until the deck is finished. After the entire deck is drawn, each player has
one last turn before the game ends. For simplicity we focus on 2-player Hanabi
for all our experiments and note that it is straightforward to extend our
method to any number of players.

###  5.1 Blueprint Training

As explained in Section 3 the public and private observations in Hanabi can be
factorized into public and private features. We modify the open-source Hanabi
Learning Environment (HLE) (Bard et al., 2020) to implement this. Here, the
only private observation is the partner’s hand, while all other information is
public. There are many different options for implementing the public-RNN
concept. We end up with the design shown in Figure 2 (A). Specifically, the
LSTM only takes public features as input while an additional MLP takes in the
concatenation of private and public features. The outputs of the two streams
are fused through element-wise multiplication before feeding into the dueling
architecture (Wang et al., 2016) to produce Q values. We have also
experimented with other designs such as using concatenation in place of the
element-wise multiplication, or feeding only private observation to the MLP.
Empirically we find that the design chosen performs the best, achieving the
highest score in self-play.

We use the distributed training setting described in (Hu et al., 2021). We
follow their hyper-parameters but replace the network with the one described
above. The training jobs run with 40 CPU cores and 3 GPUs.

###  5.2 Belief Training

The belief model is trained to predict the player’s own hand given their
action observation history. An overview of the architecture is shown in the
right panel of Fig 2. An encoder LSTM converts the sequence of observations to
a context vector. The model then predicts its own hand in an auto-regressive
fashion from oldest card to newest. The input at each step is the
concatenation of the context vector and the embedding of the last predicted
card. The model is trained end-to-end with maximum likelihood:

$\mathcal{L}(c_{1:n}|\tau)=-\sum_{i=1}^{n}\log p(c_{i}|\tau,c_{1:i-1}),$ (6)

where $n$ is the number of cards in hand and $c_{i}$ is the value of the
$i$-th card.

We use a setup similar to that of reinforcement learning to train the belief
model instead of a more traditional way of creating a fixed train, test and
validation set. We use a trained policy and a large number of parallel Hanabi
simulators to continuously collect trajectories and write them into a replay
buffer. In parallel we sample from the replay buffer to train the belief model
using a supervised loss. This helps us easily avoid over-fitting without
manually tuning hyper-parameters and regularization. The RL policy used to
generate data is fixed during the entire process. It takes 20 CPU cores and 2
GPUs to train the belief models.

###  5.3 LBS Implementation Details

Learned Belief Search is straightforward once we have trained a BP and a
belief model. The search player samples hands from the belief model and
filters out the ones that are inconsistent with current game status based on
their private observation. In the extremely rare case where the belief model
fails to produce a sufficient number of legal hands, it reverts back to the
BP. To understand the impact of various design parameters, we experimented
with both playing out all trajectories until the end of the game as well as
rolling out for a fixed number of steps and using a bootstrapped value
estimate at the final state. Similar to SPARTA, the search actor only deviates
from the BP if the expected value of the action chosen by search is
$\delta=0.05$ higher than that of the BP and a UCB-like pruning method is used
to reduce the number of samples required. All search experiments are executed
using 5 CPU cores, 1 GPU and 64GB of memory.

##  6 Results

In this section, we first show the performance and run time of our method
compared with blueprint baseline and exact search method, SPARTA. We then
study the quality of the learned belief by comparing it to two analytical
benchmarks. Finally, we study trade-offs between training and testing under a
fixed budget.

###  6.1 Performance

Figure 3: Comparison of speed and average score of different policies in 5-card (top) and 6-card (bottom) Hanabi. The number next to each LBS data point is the rollout depth. LBS with different rollout depths provide a tunable trade-off between speed and performance. LBS provides most of the performance benefits of exact search (SPARTA) at a fraction of the compute cost, and the speedup grows with the size of the belief space (5-card vs 6-card). Variant | Blueprint | SPARTA | LBS
---|---|---|---
5-card | 24.08 $\pm$ 0.01 | ($<$1s) | 24.52 $\pm$ 0.01 | (215s) | 24.48 $\pm$ 0.01 | (47s)
6-card | 24.57 $\pm$ 0.01 | ($<$1s) | 24.82 $\pm$ 0.01 | (1747s) | 24.76 $\pm$ 0.01 | (42s)
7-card | 23.67 $\pm$ 0.02 | ($<$1s) | Out-of-Mem Error | 24.26 $\pm$ 0.01 | (58s)
Table 1: Result on different Hanabi variants. Each cell contains the mean and standard error of mean (s.e.m.) over 5000 games. It also shows the average time it takes to run a game in the parentheses next to the performance. Note that for the 7-card variant, we reduce the maximum number of hints to 4 in order to make the game harder. All the experiments are executed using 5 CPU cores, 1 Nvidia Quadro GP100 GPU and 64GB of memory. SPARTA fails to run on the 7-card variant due to out-of-memory error since the entire belief space is too large to fit into the allocated memory. Method | Depth | Time | Blueprint Strength
---|---|---|---
Weak | Medium | Strong | Best
Blueprint |  |  $<$1s | 15.38 $\pm$ 0.05 | 22.99 $\pm$ 0.03 | 24.08 $\pm$ 0.01 | 24.42 $\pm$ 0.01
SPARTA |  | 215s | 19.53 $\pm$ 0.03 | 24.16 $\pm$ 0.02 | 24.52 $\pm$ 0.01 | 24.66 $\pm$ 0.01
LBS | $\infty$ | 121s | 18.88 $\pm$ 0.03 | 23.95 $\pm$ 0.02 | 24.42 $\pm$ 0.01 | 24.59 $\pm$ 0.01
LBS | 32 | 84s | 19.05 $\pm$ 0.03 | 24.01 $\pm$ 0.02 | 24.45 $\pm$ 0.01 | 24.60 $\pm$ 0.01
LBS | 16 | 47s | 19.27 $\pm$ 0.03 | 24.04 $\pm$ 0.02 | 24.48 $\pm$ 0.01 | 24.62 $\pm$ 0.01
LBS | 8 | 25s | 19.14 $\pm$ 0.03 | 24.03 $\pm$ 0.02 | 24.43 $\pm$ 0.01 | 24.59 $\pm$ 0.01
LBS | 4 | 14s | 18.75 $\pm$ 0.03 | 23.95 $\pm$ 0.02 | 24.41 $\pm$ 0.01 | 24.55 $\pm$ 0.01
LBS | 2 | 9s | 18.26 $\pm$ 0.04 | 23.81 $\pm$ 0.02 | 24.35 $\pm$ 0.01 | 24.44 $\pm$ 0.02
LBS | 1 | 6s | 17.99 $\pm$ 0.04 | 23.69 $\pm$ 0.02 | 24.26 $\pm$ 0.02 | 24.43 $\pm$ 0.02
Table 2: Average scores in 2-player Hanabi with different search variants.
Time column shows the average wall-clock time of each method to play a game.
Weak, Medium and Strong blueprints uses 512 hidden units per layer and are
trained with RL method after 1 hour, 5 hours, and 20 hours respectively. The
Best blueprint is a larger model with 1024 hidden units each layer trained for
72 hours. Each cell contains the mean and standard error of mean averaged over
5000 games. LBS variants achieve a substantial fraction of the policy
improvements of SPARTA over the blueprint at a lower computational cost. Both
overall best results (from SPARTA) and the best LBS results are bold for
better readability. Note that the Time column does not reflect the time for
the more expensive Best blueprint.

Table 1 demonstrates the scalability of LBS compared to SPARTA in environments
involving different amount of hidden information. We test them on modified
variants of Hanabi where each player holds 6 or 7 cards as well as the
official version of 5 cards. In these experiments we use setting mentioned in
Section 5.1 to train BP with RL and then train belief model until convergence
following Section 5.2. It worth noting that it is easier to achieve a higher
score with bigger hand size as on average more information will be revealed
per hint. In fact, we need to reduce the maximum number of hints from 8 to 4
in the 7 card variant to prevent the RL blueprint policy from being almost
perfect. For comparison, we run SPARTA on our models which can be seen as a
expensive upper bound for LBS. For LBS, we roll out for 16 steps before
bootstrapping from the $Q$ values. In the standard Hanabi, LBS delivers 90% of
the performance boost compared to SPARTA while being 4.6$\times$ faster. In
the 6-card variant, the SPARTA method runs 8$\times$ slower than it does on
standard Hanabi while LBS runs faster (likely due to shorter games),
delivering 76% of the improvement with 42$\times$ less time. In the 7-card
variant, the SPARTA exhausts the 64GB of memory as the storage required for
all possible hands and corresponding LSTM states grow exponentially w.r.t.
hand size. LBS, on the other hand, scales well and delivers strong
performance. Note that the run time of LBS on the 7-card variant is slower
partially due to a small change in the implementation to accommodate larger
hand.

Figure 3 summarizes the speed/performance trade-offs of LBS compared to
running an RL policy directly or using an exact search method (SPARTA). In
5-card Hanabi (left), we start with a blueprint policy that achieves an
average score of 22.99 after 5 hours of training, and apply LBS with different
rollout lengths as well as an exact search. LBS achieves most of the score
improvement of exact search while being much faster to execute. Changing the
rollout depth allows for tuning speed vs. performance. As we move to a larger
game (6-card Hanabi), SPARTA becomes 10$\times$ slower while LBS runs at
approximately the same speed and continues to provide a similar fraction of
the performance improvement.

As mentioned in Section 4, applying LBS independently on multiple players will
not lead to better performance due to the inaccurate beliefs. To verify this,
we run LBS on both players in standard 5-card Hanabi. The result is 24.34
$\pm$ 0.02, which is noticeably worse than the 24.48 $\pm$ 0.01 achieved by
single agent LBS.

A more comprehensive analysis of these trade-offs is shown in Table 2. We
train the BP with RL for a total of 20 hours and use 3 snapshots to
demonstrate the performance of LBS given BPs of different strength. Weak,
Medium and Strong policies are snapshots after 1 hour, 5 hours and 20 hours
respectively. The network uses 512 units for both LSTM and feed-forward
layers. The belief models are trained to convergence for each BP. All search
methods run 10K rollouts per step. The best performing variant is LBS with
16-step rollouts, delivering 91% of the improvement on average comparing to
the exact search while being 4.6$\times$ faster. Even the cheapest method, LBS
with 1-step rollouts, returns a decent improvement of 55% on average and
35.8$\times$ speedup. It also worth noting that LBS performs strongly even on
the weakest policy, demonstrating high versatility of the method.

To further test the limit of self-play in Hanabi, we train a larger model with
1024 units per layer for an extend period of 72 hours and apply both LBS and
SPARTA on top. The model is dubbed Best in Table 2. The BP itself gets 24.42
and SPARTA further boosts the performance to 24.66, the highest self-play
score ever reported in 2 player Hanabi. Remarkably, LBS achieves 24.62,
delivering 83% fo the benefit of SPARTA while taking less than $1/4$ of the
time (69s for LBS and 364s for SPARTA).

We note that the more expensive LBS that rolls out until the end of the games
(LBS-$\infty$) is not the best performing one. It consistently under-performs
some of the LBS-k variants by a small, in many cases significant, amount. We
hypothesis that under LBS-$\infty$ it is more likely for the agents to reach a
state that is under-explored during training. Therefore the approximate belief
will be less accurate and the estimate Q-value be wrong. The LBS-k methods
where the Q-value after k steps is used as a bootstrap may naturally avoid
those situations since the BP may also have low Q values for under-explored
states. One piece of evidence for this theory is that in LBS-$\infty$, 0.1% of
the games end up with a completely failed belief prediction and have to revert
back to BP while the same only happens to 0.0083% of the games for LBS-k.

Clearly, this is a potential problem: part of the reason search works well is
that it can discover moves that were underestimated and, consequently, under-
explored by the BP. The brittleness of the learned belief, in combination with
the difference in overall belief quality (Fig 4), help explain the difference
in performance between LBS and exact methods like SPARTA.

###  6.2 Belief Quality

Figure 4: Per-card cross entropy with the true hand for different beliefs in
games played by BP.

We examine the quality of the learned belief model by looking at its cross
entropy loss for predicting hidden card values. We compare against two
benchmarks: the exact beliefs marginalized over each card, and an auto-
regressive belief based only on grounded information. The grounded belief
predicts a distribution over card values proportional to remaining card
counts, for all card values consistent with past hints.

We generate 1000 games with the strong policy and compute the two benchmarks
together with the loss of the learned belief (Eq. 6) from a fully trained
belief model. Figure 4 shows how these 3 values change over the course of
games. We see that our learned belief model performs considerably better than
the grounded belief. There is still a gap between learned belief and exact
belief, especially in the later stage of the game. More powerful models such
as transformers (Vaswani et al., 2017) may further improve the belief learning
but we leave it for future work.

Figure 5: Result of fixed budget (24 hours) at training time. The ticks
“$a|b$”on x-axis means $a$ hours to train BP and $b$ hours to train belief
model.

Figure 6: Result of fixed budget at test time. The ticks “$a|b$” on x-axis
means run search for $a$ steps before bootstrapping with Q function and run
$b$ search per move. Each data point on both figures is evaluated on 5000
games and the shaded area is the standard error of mean.

###  6.3 Fixed Budget Training & Testing

Since one of the motivations for LBS is speed, it would be interesting to know
how we could allocate resources at training and test time to maximize
performance given a fixed computational budget. For fixed training budget, we
train the BP for $l$ hours and then train belief model for $24-l$ hours. We
evaluate these combinations with LBS-$\infty$ as well as BPs themselves. As
shown in Figure 6, with longer RL training, the BP improves monotonically, but
the final performance suffers due to a poor belief model. The best combination
is $\sim$18 hours for RL and $\sim$6 hours for belief learning.

We then take the models from the best combination to study how to allocate
compute between the number of rollouts and rollout depth. We start with LBS-1
and 128K search per step, and then halve the number of searches as we double
the search depth. The result is shown in Figure 6. If we compare the results
here with those from Table 2, we see that although LBS-16 still has the best
performance, the relative strength between LBS-32 and LBS-8 flips, indicating
that the trade-off may still matter in some cases.

##  7 Conclusion

We presented Learned Belief Search, a novel search algorithms for POMDPs that
can be used to improve upon the performance of a blueprint policy at test time
whenever a simulator of the environment is available. We also presented
extensions of LBS that make it applicable to fully cooperative, partially
observable multi-agent settings. The heart of LBS is an auto-regressive model
that can be used to generate samples from an approximate belief for any given
AOH.

While LBS achieves strong performance on the benchmark problem Hanabi, our
work also clearly points to a number of future directions. For a start, the
search process can bring the belief model to under-explored regions of the
state space. This could be addressed by retraining the belief model on the
data generated from LBS.

Another interesting direction for future work is to amortize the search
process, _e.g._ by integrating it into the training process, and to extend LBS
to multiplayer and multi-step search. To enable these directions, and many
others, we plan to open-source all of the code for LBS.

## References

  * Bard et al. (2020) Bard, N., Foerster, J. N., Chandar, S., Burch, N., Lanctot, M., Song, H. F., Parisotto, E., Dumoulin, V., Moitra, S., Hughes, E., Dunning, I., Mourad, S., Larochelle, H., Bellemare, M. G., and Bowling, M.  The hanabi challenge: A new frontier for ai research.  _Artificial Intelligence_ , 280:103216, 2020.  ISSN 0004-3702.
  * Bertsekas & Castanon (1999) Bertsekas, D. P. and Castanon, D. A.  Rollout algorithms for stochastic scheduling problems.  _Journal of Heuristics_ , 5(1):89–108, 1999.
  * Brown & Sandholm (2017) Brown, N. and Sandholm, T.  Superhuman AI for heads-up no-limit poker: Libratus beats top professionals.  _Science_ , pp. eaao1733, 2017.
  * Brown & Sandholm (2019) Brown, N. and Sandholm, T.  Superhuman AI for multiplayer poker.  _Science_ , pp. eaay2400, 2019.
  * Campbell et al. (2002) Campbell, M., Hoane Jr, A. J., and Hsu, F.-h.  Deep Blue.  _Artificial intelligence_ , 134(1-2):57–83, 2002\.
  * Canaan et al. (2019) Canaan, R., Togelius, J., Nealen, A., and Menzel, S.  Diverse agents for ad-hoc cooperation in hanabi.  In _IEEE Conference on Games 2019, CoG 2019_ , IEEE Conference on Computatonal Intelligence and Games, CIG. IEEE Computer Society, August 2019.  doi: 10.1109/CIG.2019.8847944.  2019 IEEE Conference on Games, CoG 2019 ; Conference date: 20-08-2019 Through 23-08-2019.
  * Foerster et al. (2019) Foerster, J., Song, F., Hughes, E., Burch, N., Dunning, I., Whiteson, S., Botvinick, M., and Bowling, M.  Bayesian action decoder for deep multi-agent reinforcement learning.  In _International Conference on Machine Learning_ , pp. 1942–1951, 2019.
  * Hausknecht & Stone (2015) Hausknecht, M. and Stone, P.  Deep recurrent q-learning for partially observable mdps.  In _2015 AAAI Fall Symposium Series_ , 2015.
  * Horák & Bošanskỳ (2019) Horák, K. and Bošanskỳ, B.  Solving partially observable stochastic games with public observations.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pp. 2029–2036, 2019.
  * Hu & Foerster (2020) Hu, H. and Foerster, J. N.  Simplified action decoder for deep multi-agent reinforcement learning.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=B1xm3RVtwB.
  * Hu et al. (2020) Hu, H., Peysakhovich, A., Lerer, A., and Foerster, J.  “other-play”for zero-shot coordination.  In _Proceedings of Machine Learning and Systems 2020_ , pp. 9396–9407. 2020.
  * Hu et al. (2021) Hu, H., Lerer, A., Cui, B., Pineda, L., Wu, D., Brown, N., and Foerster, J. N.  Off-belief learning.  _CoRR_ , abs/2103.04000, 2021.  URL https://arxiv.org/abs/2103.04000.
  * Kovařík et al. (2019) Kovařík, V., Schmid, M., Burch, N., Bowling, M., and Lisỳ, V.  Rethinking formal models of partially observable multiagent decision making.  _arXiv preprint arXiv:1906.11110_ , 2019.
  * Lerer et al. (2020) Lerer, A., Hu, H., Foerster, J. N., and Brown, N.  Improving policies via search in cooperative partially observable games.  In _AAAI_ , pp. 7187–7194, 2020.
  * Moravčík et al. (2017) Moravčík, M., Schmid, M., Burch, N., Lisỳ, V., Morrill, D., Bard, N., Davis, T., Waugh, K., Johanson, M., and Bowling, M.  Deepstack: Expert-level artificial intelligence in heads-up no-limit poker.  _Science_ , 356(6337):508–513, 2017.
  * O’Dwyer (2019) O’Dwyer, A.  Hanabi.  https://github.com/Quuxplusone/Hanabi, 2019.
  * Ross et al. (2008) Ross, S., Pineau, J., Paquet, S., and Chaib-Draa, B.  Online planning algorithms for pomdps.  _Journal of Artificial Intelligence Research_ , 32:663–704, 2008.
  * Roy et al. (2005) Roy, N., Gordon, G., and Thrun, S.  Finding approximate pomdp solutions through belief compression.  _Journal of artificial intelligence research_ , 23:1–40, 2005.
  * Schrittwieser et al. (2019) Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., et al.  Mastering atari, go, chess and shogi by planning with a learned model.  _arXiv preprint arXiv:1911.08265_ , 2019.
  * Silver & Veness (2010) Silver, D. and Veness, J.  Monte-carlo planning in large pomdps.  In _Advances in neural information processing systems_ , pp. 2164–2172, 2010.
  * Silver et al. (2016) Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al.  Mastering the game of go with deep neural networks and tree search.  _Nature_ , 529(7587):484, 2016.
  * Silver et al. (2017) Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., et al.  Mastering the game of go without human knowledge.  _Nature_ , 550(7676):354, 2017.
  * Silver et al. (2018) Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Sifre, L., Kumaran, D., Graepel, T., et al.  A general reinforcement learning algorithm that masters chess, shogi, and go through self-play.  _Science_ , 362(6419):1140–1144, 2018.
  * Tesauro (1994) Tesauro, G.  TD-Gammon, a self-teaching backgammon program, achieves master-level play.  _Neural computation_ , 6(2):215–219, 1994.
  * Tian et al. (2020) Tian, Y., Gong, Q., and Jiang, T.  Joint policy search for multi-agent collaboration with imperfect information.  _arXiv preprint arXiv:2008.06495_ , 2020.
  * Vaswani et al. (2017) Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, L. u., and Polosukhin, I.  Attention is all you need.  In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), _Advances in Neural Information Processing Systems 30_ , pp. 5998–6008. Curran Associates, Inc., 2017.  URL http://papers.nips.cc/paper/7181-attention-is-all-you-need.pdf.
  * Walton-Rivers et al. (2017) Walton-Rivers, J., Williams, P. R., Bartle, R., Perez-Liebana, D., and Lucas, S. M.  Evaluating and modelling hanabi-playing agents.  In _IEEE Congress on Evolutionary Computation (CEC)_ , pp. 1382–1389, 2017.
  * Wang et al. (2016) Wang, Z., Schaul, T., Hessel, M., Hasselt, H., Lanctot, M., and Freitas, N.  Dueling network architectures for deep reinforcement learning.  volume 48 of _Proceedings of Machine Learning Research_ , pp. 1995–2003, New York, New York, USA, 20–22 Jun 2016. PMLR.  URL http://proceedings.mlr.press/v48/wangf16.html.
  * Wu (2018) Wu, D.  A rewrite of hanabi-bot in scala.  https://github.com/lightvector/fireflower, 2018.