* D’Odorico et al. (2000) D’Odorico, S., Cristiani, S., Dekker, H., et al. 2000, in Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 4005, Discoveries and Research Prospects from 8- to 10-Meter-Class Telescopes, ed. J. Bergeron, 121–130, doi: 10.1117/12.390133
  * Drimmel & Spergel (2001) Drimmel, R., & Spergel, D. N. 2001, ApJ, 556, 181, doi: 10.1086/321556
  * Eilers et al. (2019) Eilers, A.-C., Hogg, D. W., Rix, H.-W., & Ness, M. K. 2019, ApJ, 871, 120, doi: 10.3847/1538-4357/aaf648
  * Erkal et al. (2019) Erkal, D., Belokurov, V., Laporte, C. F. P., et al. 2019, MNRAS, 487, 2685, doi: 10.1093/mnras/stz1371
  * Errani & Navarro (2021) Errani, R., & Navarro, J. F. 2021, MNRAS, 505, 18, doi: 10.1093/mnras/stab1215
  * Errani et al. (2023) Errani, R., Navarro, J. F., Smith, S. E. T., & McConnachie, A. W. 2023, arXiv e-prints, arXiv:2311.10134, doi: 10.48550/arXiv.2311.10134
  * Ferrone et al. (2023) Ferrone, S., Di Matteo, P., Mastrobuono-Battisti, A., et al. 2023, A&A, 673, A44, doi: 10.1051/0004-6361/202244141
  * Fukushige & Heggie (2000) Fukushige, T., & Heggie, D. C. 2000, MNRAS, 318, 753, doi: 10.1046/j.1365-8711.2000.03811.x
  * Gaia Collaboration et al. (2016) Gaia Collaboration, Prusti, T., de Bruijne, J. H. J., et al. 2016, A&A, 595, A1, doi: 10.1051/0004-6361/201629272
  * Gaia Collaboration et al. (2018) Gaia Collaboration, Helmi, A., van Leeuwen, F., et al. 2018, A&A, 616, A12, doi: 10.1051/0004-6361/201832698
  * Gaia Collaboration et al. (2023) Gaia Collaboration, Vallenari, A., Brown, A. G. A., et al. 2023, A&A, 674, A1, doi: 10.1051/0004-6361/202243940
  * Goodman & Weare (2010) Goodman, J., & Weare, J. 2010, Communications in Applied Mathematics and Computational Science, 5, 65, doi: 10.2140/camcos.2010.5.65
  * GRAVITY Collaboration et al. (2019) GRAVITY Collaboration, Abuter, R., Amorim, A., et al. 2019, A&A, 625, L10, doi: 10.1051/0004-6361/201935656
  * Grillmair (2017) Grillmair, C. J. 2017, ApJ, 847, 119, doi: 10.3847/1538-4357/aa8872
  * Grillmair & Dionatos (2006) Grillmair, C. J., & Dionatos, O. 2006, ApJ, 643, L17, doi: 10.1086/505111
  * Hammer et al. (2007) Hammer, F., Puech, M., Chemin, L., Flores, H., & Lehnert, M. D. 2007, ApJ, 662, 322, doi: 10.1086/516727
  * Harris (2010) Harris, W. E. 2010, arXiv e-prints, arXiv:1012.3224.  https://arxiv.org/abs/1012.3224
  * Ibata et al. (2020a) Ibata, R., Bellazzini, M., Thomas, G., et al. 2020a, ApJ, 891, L19, doi: 10.3847/2041-8213/ab77c7
  * Ibata et al. (2021a) Ibata, R., Diakogiannis, F. I., Famaey, B., & Monari, G. 2021a, ApJ, 915, 5, doi: 10.3847/1538-4357/abfda9
  * Ibata et al. (2011) Ibata, R., Sollima, A., Nipoti, C., et al. 2011, ApJ, 738, 186, doi: 10.1088/0004-637X/738/2/186
  * Ibata et al. (2020b) Ibata, R., Thomas, G., Famaey, B., et al. 2020b, ApJ, 891, 161, doi: 10.3847/1538-4357/ab7303
  * Ibata et al. (2021b) Ibata, R., Malhan, K., Martin, N., et al. 2021b, ApJ, 914, 123, doi: 10.3847/1538-4357/abfcc2
  * Ibata et al. (2019a) Ibata, R. A., Bellazzini, M., Malhan, K., Martin, N., & Bianchini, P. 2019a, Nature Astronomy, 3, 667, doi: 10.1038/s41550-019-0751-x
  * Ibata et al. (2017a) Ibata, R. A., Lewis, G. F., Thomas, G., Martin, N. F., & Chapman, S. 2017a, ApJ, 842, 120, doi: 10.3847/1538-4357/aa7514
  * Ibata et al. (2019b) Ibata, R. A., Malhan, K., & Martin, N. F. 2019b, ApJ, 872, 152, doi: 10.3847/1538-4357/ab0080
  * Ibata et al. (2018) Ibata, R. A., Malhan, K., Martin, N. F., & Starkenburg, E. 2018, ApJ, 865, 85, doi: 10.3847/1538-4357/aadba3
  * Ibata et al. (2017b) Ibata, R. A., McConnachie, A., Cuillandre, J.-C., et al. 2017b, ApJ, 848, 129, doi: 10.3847/1538-4357/aa8562
  * Ji et al. (2020) Ji, A. P., Li, T. S., Hansen, T. T., et al. 2020, AJ, 160, 181, doi: 10.3847/1538-3881/abacb6
  * Jiao et al. (2023) Jiao, Y., Hammer, F., Wang, H., et al. 2023, A&A, 678, A208, doi: 10.1051/0004-6361/202347513
  * Jurić et al. (2008) Jurić, M., Ivezić, Ž., Brooks, A., et al. 2008, ApJ, 673, 864, doi: 10.1086/523619
  * Klypin et al. (2002) Klypin, A., Zhao, H., & Somerville, R. S. 2002, ApJ, 573, 597, doi: 10.1086/340656
  * Koposov et al. (2010) Koposov, S. E., Rix, H.-W., & Hogg, D. W. 2010, ApJ, 712, 260, doi: 10.1088/0004-637X/712/1/260
  * Koposov et al. (2018) Koposov, S. E., Walker, M. G., Belokurov, V., et al. 2018, MNRAS, 479, 5343, doi: 10.1093/mnras/sty1772
  * Koposov et al. (2019) Koposov, S. E., Belokurov, V., Li, T. S., et al. 2019, MNRAS, 485, 4726, doi: 10.1093/mnras/stz457
  * Koposov et al. (2023) Koposov, S. E., Erkal, D., Li, T. S., et al. 2023, MNRAS, 521, 4936, doi: 10.1093/mnras/stad551
  * Kroupa et al. (1993) Kroupa, P., Tout, C. A., & Gilmore, G. 1993, MNRAS, 262, 545, doi: 10.1093/mnras/262.3.545
  * Kuijken & Gilmore (1991) Kuijken, K., & Gilmore, G. 1991, ApJ, 367, L9, doi: 10.1086/185920
  * Kunder et al. (2017) Kunder, A., Kordopatis, G., Steinmetz, M., et al. 2017, AJ, 153, 75, doi: 10.3847/1538-3881/153/2/75
  * Küpper et al. (2008) Küpper, A. H. W., Macleod, A., & Heggie, D. C. 2008, Astronomische Nachrichten, 329, 1061, doi: 10.1002/asna.200811069
  * Li et al. (2018a) Li, G.-W., Yanny, B., & Wu, Y. 2018a, ApJ, 869, 122, doi: 10.3847/1538-4357/aaed29
  * Li et al. (2018b) Li, T. S., Simon, J. D., Kuehn, K., et al. 2018b, ApJ, 866, 22, doi: 10.3847/1538-4357/aadf91
  * Li et al. (2019) Li, T. S., Koposov, S. E., Zucker, D. B., et al. 2019, MNRAS, 490, 3508, doi: 10.1093/mnras/stz2731
  * Li et al. (2021) Li, T. S., Koposov, S. E., Erkal, D., et al. 2021, ApJ, 911, 149, doi: 10.3847/1538-4357/abeb18
  * Lian et al. (2022) Lian, J., Zasowski, G., Mackereth, T., et al. 2022, MNRAS, 513, 4130, doi: 10.1093/mnras/stac1151
  * Ludlow et al. (2014) Ludlow, A. D., Navarro, J. F., Angulo, R. E., et al. 2014, MNRAS, 441, 378, doi: 10.1093/mnras/stu483
  * Majewski et al. (2000) Majewski, S. R., Patterson, R. J., Dinescu, D. I., et al. 2000, in Liege International Astrophysical Colloquia, Vol. 35, Liege International Astrophysical Colloquia, ed. A. Noels, P. Magain, D. Caro, E. Jehin, G. Parmentier, & A. A. Thoul, 619.  https://arxiv.org/abs/astro-ph/9910278
  * Majewski et al. (2017) Majewski, S. R., Schiavon, R. P., Frinchaboy, P. M., et al. 2017, AJ, 154, 94, doi: 10.3847/1538-3881/aa784d
  * Malhan & Ibata (2018) Malhan, K., & Ibata, R. A. 2018, MNRAS, 477, 4063, doi: 10.1093/mnras/sty912
  * Malhan et al. (2018) Malhan, K., Ibata, R. A., & Martin, N. F. 2018, MNRAS, 481, 3442, doi: 10.1093/mnras/sty2474
  * Malhan et al. (2022) Malhan, K., Ibata, R. A., Sharma, S., et al. 2022, ApJ, 926, 107, doi: 10.3847/1538-4357/ac4d2a
  * Martin et al. (2022) Martin, N. F., Ibata, R. A., Starkenburg, E., et al. 2022, MNRAS, 516, 5331, doi: 10.1093/mnras/stac2426
  * Martin et al. (2023) Martin, N. F., Starkenburg, E., Yuan, Z., et al. 2023, arXiv e-prints, arXiv:2308.01344, doi: 10.48550/arXiv.2308.01344
  * Mastrobuono-Battisti et al. (2012) Mastrobuono-Battisti, A., Di Matteo, P., Montuori, M., & Haywood, M. 2012, A&A, 546, L7, doi: 10.1051/0004-6361/201219563
  * Mateu (2023) Mateu, C. 2023, MNRAS, 520, 5225, doi: 10.1093/mnras/stad321
  * Mau et al. (2020) Mau, S., Cerny, W., Pace, A. B., et al. 2020, ApJ, 890, 136, doi: 10.3847/1538-4357/ab6c67
  * McClure-Griffiths & Dickey (2007) McClure-Griffiths, N. M., & Dickey, J. M. 2007, ApJ, 671, 427, doi: 10.1086/522297
  * McClure-Griffiths & Dickey (2016) —. 2016, ApJ, 831, 124, doi: 10.3847/0004-637X/831/2/124
  * McMillan (2017) McMillan, P. J. 2017, MNRAS, 465, 76, doi: 10.1093/mnras/stw2759
  * Momany et al. (2006) Momany, Y., Zaggia, S., Gilmore, G., et al. 2006, A&A, 451, 515, doi: 10.1051/0004-6361:20054081
  * Monari et al. (2019) Monari, G., Famaey, B., Siebert, A., Wegg, C., & Gerhard, O. 2019, A&A, 626, A41, doi: 10.1051/0004-6361/201834820
  * Muraveva et al. (2018) Muraveva, T., Delgado, H. E., Clementini, G., Sarro, L. M., & Garofalo, A. 2018, MNRAS, 481, 1195, doi: 10.1093/mnras/sty2241
  * Navarro et al. (1997) Navarro, J. F., Frenk, C. S., & White, S. D. M. 1997, ApJ, 490, 493, doi: 10.1086/304888
  * Odenkirchen et al. (2009) Odenkirchen, M., Grebel, E. K., Kayser, A., Rix, H.-W., & Dehnen, W. 2009, AJ, 137, 3378, doi: 10.1088/0004-6256/137/2/3378
  * Peñarrubia et al. (2014) Peñarrubia, J., Ma, Y.-Z., Walker, M. G., & McConnachie, A. 2014, MNRAS, 443, 2204, doi: 10.1093/mnras/stu879
  * Petersen et al. (2022) Petersen, M. S., Peñarrubia, J., & Jones, E. 2022, MNRAS, 514, 1266, doi: 10.1093/mnras/stac1429
  * Pietrzyński et al. (2019) Pietrzyński, G., Graczyk, D., Gallenne, A., et al. 2019, Nature, 567, 200, doi: 10.1038/s41586-019-0999-4
  * Portail et al. (2017) Portail, M., Gerhard, O., Wegg, C., & Ness, M. 2017, MNRAS, 465, 1621, doi: 10.1093/mnras/stw2819
  * Press et al. (1992) Press, W. H., Teukolsky, S. A., Vetterling, W. T., & Flannery, B. P. 1992, Numerical recipes in FORTRAN. The art of scientific computing (Cambridge University Press)
  * Randich et al. (2022) Randich, S., Gilmore, G., Magrini, L., et al. 2022, A&A, 666, A121, doi: 10.1051/0004-6361/202243141
  * Renaud et al. (2017) Renaud, F., Agertz, O., & Gieles, M. 2017, MNRAS, 465, 3622, doi: 10.1093/mnras/stw2969
  * Roederer & Gnedin (2019) Roederer, I. U., & Gnedin, O. Y. 2019, ApJ, 883, 84, doi: 10.3847/1538-4357/ab365c
  * Sanderson & Curtin (2016) Sanderson, C., & Curtin, R. 2016, Journal of Open Source Software, 1, 26, doi: 10.21105/joss.00026
  * Sbordone et al. (2014) Sbordone, L., Caffau, E., Bonifacio, P., & Duffau, S. 2014, A&A, 564, A109, doi: 10.1051/0004-6361/201322430
  * Schlafly & Finkbeiner (2011) Schlafly, E. F., & Finkbeiner, D. P. 2011, ApJ, 737, 103, doi: 10.1088/0004-637X/737/2/103
  * Schlegel et al. (1998) Schlegel, D. J., Finkbeiner, D. P., & Davis, M. 1998, ApJ, 500, 525, doi: 10.1086/305772
  * Schönrich et al. (2010) Schönrich, R., Binney, J., & Dehnen, W. 2010, MNRAS, 403, 1829, doi: 10.1111/j.1365-2966.2010.16253.x
  * Simon et al. (2020) Simon, J. D., Li, T. S., Erkal, D., et al. 2020, ApJ, 892, 137, doi: 10.3847/1538-4357/ab7ccb
  * Sivia & Skilling (2006) Sivia, D., & Skilling, J. 2006, Data analysis: a Bayesian tutorial, Oxford science publications (Oxford University Press).  http://books.google.com.au/books?id=6O8ZAQAAIAAJ
  * Smith et al. (2023) Smith, S. E. T., Cerny, W., Hayes, C. R., et al. 2023, arXiv e-prints, arXiv:2311.10147.  https://arxiv.org/abs/2311.10147
  * Snaith et al. (2014) Snaith, O. N., Haywood, M., Di Matteo, P., et al. 2014, ApJ, 781, L31, doi: 10.1088/2041-8205/781/2/L31
  * Starkenburg et al. (2017) Starkenburg, E., Martin, N., Youakim, K., et al. 2017, MNRAS, 471, 2587, doi: 10.1093/mnras/stx1068
  * Strader et al. (2011) Strader, J., Caldwell, N., & Seth, A. C. 2011, AJ, 142, 8, doi: 10.1088/0004-6256/142/1/8
  * Thomas et al. (2023) Thomas, G. F., Famaey, B., Monari, G., et al. 2023, A&A, 678, A180, doi: 10.1051/0004-6361/202346650
  * Tody (1986) Tody, D. 1986, in Society of Photo-Optical Instrumentation Engineers (SPIE) Conference Series, Vol. 627, Instrumentation in astronomy VI, ed. D. L. Crawford, 733, doi: 10.1117/12.968154
  * Tody (1993) Tody, D. 1993, in Astronomical Society of the Pacific Conference Series, Vol. 52, Astronomical Data Analysis Software and Systems II, ed. R. J. Hanisch, R. J. V. Brissenden, & J. Barnes, 173
  * van der Marel et al. (2002) van der Marel, R. P., Alves, D. R., Hardy, E., & Suntzeff, N. B. 2002, AJ, 124, 2639, doi: 10.1086/343775
  * Vasiliev (2019) Vasiliev, E. 2019, MNRAS, 484, 2832, doi: 10.1093/mnras/stz171
  * Walker et al. (2015) Walker, M. G., Mateo, M., Olszewski, E. W., et al. 2015, ApJ, 808, 108, doi: 10.1088/0004-637X/808/2/108
  * Wan et al. (2020) Wan, Z., Lewis, G. F., Li, T. S., et al. 2020, Nature, 583, 768, doi: 10.1038/s41586-020-2483-6
  * Wilkinson & Evans (1999) Wilkinson, M. I., & Evans, N. W. 1999, MNRAS, 310, 645, doi: 10.1046/j.1365-8711.1999.02964.x
  * Yanny et al. (2009) Yanny, B., Rockosi, C., Newberg, H. J., et al. 2009, AJ, 137, 4377, doi: 10.1088/0004-6256/137/5/4377
  * Yuan et al. (2020) Yuan, Z., Chang, J., Beers, T. C., & Huang, Y. 2020, ApJ, 898, L37, doi: 10.3847/2041-8213/aba49f
  * Yuan et al. (2022a) Yuan, Z., Martin, N. F., Ibata, R. A., et al. 2022a, MNRAS, 514, 1664, doi: 10.1093/mnras/stac1399
  * Yuan et al. (2022b) Yuan, Z., Malhan, K., Sestito, F., et al. 2022b, ApJ, 930, 103, doi: 10.3847/1538-4357/ac616f


# Batched Thompson Sampling for Multi-Armed Bandits††thanks: N. Karpov and Q.
Zhang are supported in part by CCF-1844234 and CCF-2006591.

Nikolai Karpov Qin Zhang

###### Abstract

We study Thompson Sampling algorithms for stochastic multi-armed bandits in
the batched setting, in which we want to minimize the regret over a sequence
of arm pulls using a small number of policy changes (or, batches). We propose
two algorithms and demonstrate their effectiveness by experiments on both
synthetic and real datasets. We also analyze the proposed algorithms from the
theoretical aspect and obtain almost tight regret-batches tradeoffs for the
two-arm case.

##  1 Introduction

Thompson sampling (TS), first proposed by Thompson in 1933 (Thompson 1933), is
a classic algorithm for solving online decision problems. It was not until a
decade ago that Thompson sampling has regained people’s attention; some
empirical studies (Scott 2010; Chapelle and Li 2011) showed that in several
applications, including online advertisement and article recommendation, TS-
based algorithms outperform alternatives such as upper confidence bound (UCB)
based algorithms. Since then Thompson sampling has been used extensively in
algorithms for Internet advertising (Graepel et al. 2010), online
recommendation (Kawale et al. 2015), Monte Carlo tree search (Bai, Wu, and
Chen 2013), revenue management (Ferreira, Simchi-Levi, and Wang 2018), website
optimization (Hill et al. 2017), etc. The method has also been studied from
the theoretical aspect, most notably for stochastic multi-armed bandit (MAB),
for which tight bounds on the regret have been obtained (Agrawal and Goyal
2012; Kaufmann, Korda, and Munos 2012; Agrawal and Goyal 2017; Jin et al.
2020).

In practical settings, it is desirable to make the algorithm have a small
number of policy changes. This is because in many applications the learning
performance would be much better if the data observations are processed in
batches, each of which under a fixed policy. For example, in clinical trials,
patients are usually tested in groups and the results are released in batches;
and in crowd-sourcing, questions and answers are typically sent and received
in batches. Another obvious advantage of batched algorithms is that such
algorithms are naturally parallelizable.

In this paper, we give the first study of Thompson sampling in the batched
setting using stochastic multi-armed bandit as the vehicle. We aim to
establish a theoretical foundation for batched Thompson sampling and
demonstrate its superior practical performance.

Multi-Armed Bandits.  In MAB we have $N$ arms, denoted by
$\\{1,2,\ldots,N\\}$. Each arm $i$ is associated with a reward distribution
with support in $[0,1]$ and (unknown) mean $\mu_{i}$. Let
$\mu_{*}=\max_{i\in[N]}\mu_{i}$.111We use $[Z]$ to denote the set
$\\{1,2,\ldots,Z\\}$.. We want to make a sequence of $T$ pulls over the $N$
arms with the goal of maximizing the accumulated reward. Each time we pull an
arm, we get a reward sampled from its associated distribution.

More precisely, for each time $t\in[T]$, let $\pi_{t}\in[N]$ be the arm pulled
at time $t$, and let $\pi=\\{\pi_{1},\pi_{2},\ldots,\pi_{T}\\}$ denote the
sequence of $T$ pulls. We define the regret with respect to the pull sequence
$\pi$ to be

$\text{Reg}_{T}(\pi)\triangleq\sum_{t=1}^{T}(\mu_{\star}-\mu_{\pi_{t}})=\sum_{t=1}^{T}\Delta_{\pi_{t}},$

where $\Delta_{i}=\mu_{*}-\mu_{i}$ is the gap between the mean of the best arm
and that of the $i$-th arm. $\text{Reg}_{T}(\pi)$ can be seen as the
difference between the reward of the optimal algorithm which always pulls the
best arm and that of the algorithm taking the pull sequence $\pi$.

In the batched setting, the sequence of $T$ pulls is partitioned into a set of
batches. Let $0=T^{(0)}<T^{(1)}<\ldots<T^{(m)}=T$. The $r$-th batch contains
$(T^{(r+1)}-T^{(r)})$ pulls, which are fully determined at the beginning of
the $r$-th batch. That is, they only depend on the indices of arms being
pulled and outcomes of the pulls before time $T^{(r)}$. Our goal is to design
an algorithm that uses a small number of batches and achieves a small expected
regret $\mathbf{E}[\text{Reg}_{T}(\pi)]$, where the expectation is taken over
the randomness of the algorithm and the arm pulls.

Thompson Sampling.  In Thompson sampling (TS), at any time step $t$, there is
a prior distribution $\mathcal{D}_{i}(t)$ on each arm $i$. At each time step,
we sample for each $i\in[N]$ a value $\theta_{i}(t)\sim\mathcal{D}_{i}(t)$,
and pull the arm associated with the largest sampled value, that is,
$\pi_{t}\leftarrow\arg\max_{i\in[N]}\theta_{i}(t)$.

In the setting where the sequence of pulls are fully adaptive, after each time
step $t$, we use the obtained pull outcome (reward) to compute the posterior
distribution of $\mathcal{D}_{\pi_{t}}(t)$, which is the new prior
distribution of arm $i$ for the next pull. The prior distributions of other
arms $j\neq\pi_{t}$ remains unchanged. In the batched setting, we can only
update the prior of arm $i$ for each $i\in[N]$ at the end of each batch using
the information obtained in the current batch.

Our Contributions. In this paper, we propose two batched algorithms for regret
minimization in MAB using Thompson sampling. Our first algorithm is designed
targeting an instance-dependent bound on the regret, that is, the regret is a
function of the number of arms $N$, the gaps $\Delta_{i}$, and the time
horizon $T$. Our second algorithm targets an instance-independent bound on the
regret, that is, the regret only depends on the time horizon $T$ and the
number of arms $N$.

As previously stated, Thompson sampling often has a significant advantage over
UCB-based algorithms in terms of practical performance. We have conducted an
extensive set of experiments on both synthetics and real datasets (Section 4).
Our experiments show that the proposed algorithms significantly outperform
existing (non-TS-based) algorithms in the batched setting. Our instance-
dependent algorithm even outperforms the fully adaptive Thompson sampling
algorithm on many datasets. We consider the empirical performance of our
algorithms the main contribution of this paper.

Our theoretical bounds are conducted for the special case when there are two
arms (i.e., $N=2$). In the instance-dependent case (Section 2), our algorithm
uses $\log T$ batches and achieves a regret of $O({\log T}/{\Delta})$, where
$\Delta$ is the gap between the mean of the best arm and that of the other
arm. In the instance-independent case (Section 3), our algorithm uses
$\log\log T$ batches and achieves a regret of $O(\sqrt{T\ln T})$. Based on the
lower bound results by Gao et al. (Gao et al. 2019), these tradeoffs are
almost tight.222In the case of two arms, Gao et al. showed that $\Omega(\log
T/\log\log T)$ batches is needed to achieve instance-dependent regret $O(\log
T/\Delta)$, and $\Omega(\log\log T)$ batches is needed to achieve instance-
independent regret $O(\sqrt{T})$.

Related Work. We now briefly survey previous work related to this paper.
Thompson sampling algorithms have been studied for regret minimization in MAB
in the sequential setting. Agrawal and Goyal (Agrawal and Goyal 2012) gave a
TS-based algorithm that achieves an instance-dependent upper bound on the
expected regret, which was then improved by Kaufmann et al. (Kaufmann, Korda,
and Munos 2012) to be asymptotically optimal. Agrawal and Goyal (Agrawal and
Goyal 2017) proposed a TS-based algorithm with almost tight regret bounds in
the instance-independent setting under Beta and Gaussian priors. Very
recently, Jin et al. (Jin et al. 2020) obtained an optimal instance-
independent regret upper bound $O(\sqrt{NT})$. All these algorithms are fully
adaptive.

In recent years, batched algorithms for regret minimization in MAB have
received considerable attention. Perchet et al. (Perchet et al. 2015) gave a
set of batched algorithms for inputs with two arms. Their algorithm for the
instance-independent case achieves $O(\log\log T)$ batches and that for the
instance-dependent case achieves $O(\log T)$ batches; both algorithms achieve
almost optimal regret (up to logarithmic factors). These results were later
generalized to the $N$-arm case by Gao et al. (Gao et al. 2019) and Esfandiari
et al. (Esfandiari et al. 2019). Though not explicitly stated, the earlier
algorithm UCB2 (Auer, Cesa-Bianchi, and Fischer 2002) can be implemented in
the batched model using $O(N\log T)$ batches, and the improved-UCB (Auer and
Ortner 2010) can be implemented in the batched model using $O(\log T)$
batches.

Finally, we note that batched algorithms have been studied for other basic
problems in reinforcement and online learning, including best and top-$k$ arm
identifications in MAB (Jun et al. 2016; Agarwal et al. 2017; Jin et al.
2019), multinomial logit bandit (Dong et al. 2020), online learning and convex
optimization (Cesa-Bianchi, Dekel, and Shamir 2013; Duchi, Ruan, and Yun
2018), and Q-learning (Bai et al. 2019).

Very recently, concurrent of our work, Karbasi et al. (Karbasi, Mirrokni, and
Shadravan 2021) studied the same problem (i.e., batched Thompson sampling for
regret minimization in MAB).333The first draft of this paper appeared in May
2021, before (Karbasi, Mirrokni, and Shadravan 2021) was posted on arXiv. They
proposed an instance-independent algorithm with $O(N\log T)$ batches and
regret $O(\sqrt{NT\ln T})$, and an instance-dependent algorithm with almost
optimal regret and $O(N\log T)$ batches. In the high level, their algorithms
can be seens as adding the doubling technique to standard TS algorithms for
each arm, which can make sure that the “lagged” prior distribution does not
deviate too much from the actual prior distribution at each step of the
batched algorithm. Compared with algorithms in (Karbasi, Mirrokni, and
Shadravan 2021), ours have the following advantages: (1) For $N=2$, our
tradeoffs are almost tight, while the batch complexity in the instance-
independent algorithm in (Karbasi, Mirrokni, and Shadravan 2021) is
exponentially larger than the optimal bound. (2) We presented full tradeoffs
between number of batches and regrets, while the analysis in (Karbasi,
Mirrokni, and Shadravan 2021) is only conducted for end points. (3) Most
importantly, the practical performance of our algorithms are significantly
better than those in (Karbasi, Mirrokni, and Shadravan 2021) in terms of the
number of batches for general $N$. We have included in Section 4 of this
version a detailed empirical comparison with the batched Thompson Sampling
algorithm in (Karbasi, Mirrokni, and Shadravan 2021) under Gaussian priors.

##  2 Instance-Dependent Algorithm

We start by introducing some useful notations. For each batch $r$, let
$T^{(r)}$ be the total number of pulls on the $N$ arms before the $r$-th
batch, and $T_{i}^{(r)}$ be the number of pulls on arm $i$ before the $r$-th
batch. For each $i\in[N]$ and batch $r$, let $\mu_{i}^{(r)}$ be the empirical
mean of the $i$-th arm after $T_{i}^{(r)}$ pulls.

Our batched TS-based algorithm with instance-dependent bounds is described in
Algorithm 1. Let us describe the algorithm briefly in words. At the beginning
of the $r$-th batch, we compute for each arm $i$ the probability that its
corresponding random variable
$X_{i}\sim\mathcal{N}\left(\mu^{(r)}_{i},\alpha/T^{(r)}_{i}\right)$ is larger
than that of other surviving arms $j\in I^{(r)}$; we denote this value by
$q_{i}^{(r)}$. Let $q^{(r)}$ be the largest value in $\\{q_{i}^{(r)}\\}_{i\in
I^{(r)}}$. We construct set $I^{(r+1)}$ by discarding arms in $I^{(r)}$ whose
associated probability $q_{i}^{(r)}$ is smaller than $q^{(r)}/\beta$. The
length of the $r$-th batch is set to be $\gamma^{r}\left|I^{(r+1)}\right|$
where $\gamma=T^{1/M}$ is a parameter to control the number of batches, except
for the last batch whose length is set to be $(T-T^{(r)})$. Once the batch
size is determined, the number of pulls on each surviving arm $i$ in the
$r$-th batch is proportional to its associated probability $q_{i}^{(r)}$.

Input: A set of $N$ arms $\\{1,\ldots,N\\}$, time horizon $T$, #batches $M$,
parameters $\alpha,\beta$

1 Initialize $I^{(1)}\leftarrow I$, $\gamma\leftarrow T^{1/M}$ ;

2 pull each arm once; $\forall i\in[N]$, $T^{(1)}_{i}\leftarrow 1$, and
$\mu^{(1)}_{i}\leftarrow\text{reward of pulling arm $i$}$; $T^{(1)}\leftarrow
N$ ;

3 for  _$r=1,2,\dotsc,M$_ do

4 if  _$T^{(r)}=T$_ then terminate the process;

5 for each $i\in I^{(r)}$, let $X^{(r)}_{i}$ denote the random variable
distributed according to
$\mathcal{N}\left(\mu^{(r)}_{i},\alpha/T^{(r)}_{i}\right)$ ;

6 foreach  _$i\in I^{(r)}$_ do
$q^{(r)}_{i}\leftarrow\Pr\left[X^{(r)}_{i}>\max\limits_{j\in I^{(r)},j\neq
i}\left\\{X^{(r)}_{j}\right\\}\right]$ ;

7 $q^{(r)}\leftarrow\max\limits_{i\in I^{(r)}}\left\\{q_{i}^{(r)}\right\\}$ ;

8 $I^{(r+1)}\leftarrow\left\\{q^{(r)}_{i}\geq q^{(r)}/\beta\mid i\in
I^{(r)}\right\\}$ ;

9
$T^{(r+1)}\leftarrow\min\left\\{T^{(r)}+\left|I^{(r+1)}\right|\cdot\gamma^{r},T\right\\}$
;

10 foreach  _$i\in I^{(r+1)}$_ do
$\hat{q}^{(r)}_{i}=q^{(r)}_{i}/\sum\limits_{j\in I^{(r+1)}}q^{(r)}_{j}$;

11 foreach  _$i\in I^{(r)}$_ do

12 pull arm $i$ for $\hat{q}^{(r)}_{i}\cdot\left(T^{(r+1)}-T^{(r)}\right)$
times; set $T_{i}^{(r+1)}\leftarrow
T_{i}^{(r)}+\hat{q}^{(r)}_{i}\cdot\left(T^{(r+1)}-T^{(r)}\right)$ ;

13 compute $\mu_{i}^{(r+1)}$ using $\mu_{i}^{(r)}$, $T_{i}^{(r)}$, and the
pull outcomes on arm $i$ in the current batch.

14

Algorithm 1 Batched-TS-D$([N],T,\alpha,\beta,M)$

We would like to make a few points, which also apply to the instance-
independent algorithm in Section 3.

  1. 1.

We do not perform the standard Thompson sampling (TS) at each time step, but
compute for each arm the probability that it gives the maximum reward based on
the prior distributions of the surviving arms once at the beginning of each
batch.444In practice this can be computed efficiently by numerical methods. In
other words, we set the number of pulls for arm $i$ in each batch to be the
expected number of pulls if we follow the standard TS algorithm with the mean
and variance being the empirical ones at the beginning of the round. If a
batch is large enough, then using the expectation has similar performance than
sampling at each step following the standard TS algorithm.

  2. 2.

The pruning step (Line 1) is added for the convenience of the analysis. In
Section 4, we will show that removing this line, which brings the algorithm
closer to the standard Thompson sampling algorithm, has little affect on the
performance of the algorithm.

  3. 3.

Algorithm 1 works for general $N$ (arms), though in the analysis below we only
prove theoretical bounds in the case when $N=2$. In Section 4, experiments are
also conducted for $N>2$.

Analysis.  For $N=2$, w.l.o.g., we assume arm $1$ is the best arm (but, of
course, the algorithm does not know this at the beginning). Let
$\Delta\triangleq\Delta_{2}=\mu_{1}-\mu_{2}$.

######  Theorem 1.

Setting $\alpha=\ln(2T)$ and $\beta=100$, Batched-TS-D$(2,T,\alpha,\beta,M)$
(Algorithm 1) has expected regret $O\left(T^{\frac{1}{M}}\ln T/\Delta\right)$
and uses at most $M$ batches.

Setting $M=\log T$, we have the following corollary.

######  Corollary 2.

Batched-TS-D$(2,T,\alpha,\beta,\log T)$ (Algorithm 1) has expected regret
$O\left({\ln T}/{\Delta}\right)$ and uses at most $\log T$ batches.

In this section we prove Theorem 1. We make use of the following standard
concentration inequality.

######  Lemma 3 (Hoeffding’s inequality).

Let $X_{1},\dotsc,X_{n}\in[0,1]$ be independent random variables and
$X=\sum\limits_{i=1}^{n}X_{i}$. Then

$\Pr[X>\mathbf{E}[X]+t]\leq\exp\left(-{2t^{2}}/{n}\right)\quad$

and

$\quad\Pr[X<\mathbf{E}[X]-t]\leq\exp\left(-{2t^{2}}/{n}\right)\,.$

Define the following event which we will condition on in the rest of the
proof.

$\mathcal{E}\triangleq\left\\{\forall{i}\in\\{1,2\\},\forall{t\in[T]}:\left|\mu_{i}-{\mu}_{i}(t)\right|\leq\sqrt{\frac{\ln(2T)}{t}}\right\\}\,.$

######  Lemma 4.

$\Pr\left[\mathcal{E}\right]\geq 1-{1}/{T}$.

###### Proof.

By Hoeffding’s inequality (Lemma 3), for any $i\in[N]$ and $t\in[T]$, we have

$\Pr\left[\left|\mu_{i}-{\mu}_{i}(t)\right|\geq\sqrt{\frac{\ln(NT)}{t}}\right]\leq
2e^{-2\ln(NT)}\leq\frac{2}{(NT)^{2}}.$ (1)

The lemma follows by applying a union bound on (1) over all $i\in[N]$ and
$t\in[T]$. ∎

We write

$\displaystyle\mathbf{E}[\text{Reg}_{T}(\pi)]$ (2) $\displaystyle=$
$\displaystyle\mathbf{E}[\text{Reg}_{T}(\pi)\ |\
\mathcal{E}]\Pr[\mathcal{E}]+\mathbf{E}[\text{Reg}_{T}(\pi)\ |\
\bar{\mathcal{E}}]\Pr[\bar{\mathcal{E}}]$ $\displaystyle\leq$
$\displaystyle\mathbf{E}[\text{Reg}_{T}(\pi)\ |\
\mathcal{E}]+T\cdot(1-\Pr[\mathcal{E}])$ $\displaystyle=$
$\displaystyle\mathbf{E}[\text{Reg}_{T}(\pi)\ |\ \mathcal{E}]+1.$

We thus only need to bound $\mathbf{E}[\text{Reg}_{T}(\pi)\ |\ \mathcal{E}]$.
The next lemma indicates that arm $1$ (i.e., the best arm) will never be
pruned at Line 1 of Algorithm 1 during the process.

######  Lemma 5.

For any $r$ we have $\Pr[X^{(r)}_{1}>X^{(r)}_{2}]>1/\beta$.

###### Proof.

Conditioned on $\mathcal{E}$, we have for any $i\in\\{1,2\\}$, it holds that
$\left|\mu^{(r)}_{i}-\mu_{i}\right|\leq\sqrt{\frac{\ln(2T)}{T^{(r)}_{i}}}$,
and

$\displaystyle\mu^{(r)}_{1}-\mu^{(r)}_{2}$ $\displaystyle\geq$
$\displaystyle\mu_{1}-\mu_{2}-\sqrt{\frac{\ln(2T)}{T^{(r)}_{1}}}-\sqrt{\frac{\ln(2T)}{T^{(r)}_{2}}}$
(3) $\displaystyle\geq$
$\displaystyle-\left(\sqrt{\frac{\ln(2T)}{T^{(r)}_{1}}}+\sqrt{\frac{\ln(2T)}{T^{(r)}_{2}}}\right),$

where the second inequality is due to the fact (our assumption) that arm $1$
is the best arm. Using the fact that $\forall
x,y>0,x+y\leq\sqrt{2}\cdot\sqrt{x^{2}+y^{2}}$, we have

$\mu^{(r)}_{1}-\mu^{(r)}_{2}\geq-\sqrt{2}\cdot\sqrt{\frac{\ln(2T)}{T^{(r)}_{1}}+\frac{\ln(2T)}{T^{(r)}_{2}}}.$
(4)

Let $Z\triangleq X^{(r)}_{1}-X^{(r)}_{2}$. Recall that
$X^{(r)}_{1}\sim\mathcal{N}\left(\mu^{(r)}_{1},\alpha/T^{(r)}_{1}\right)$ and
$X^{(r)}_{2}\sim\mathcal{N}\left(\mu^{(r)}_{2},\alpha/T^{(r)}_{2}\right)$. We
have

$\Pr[X^{(r)}_{1}>X^{(r)}_{2}]=\Pr[Z>0],$

where

$Z\sim\mathcal{N}\left(\mu^{(r)}_{1}-\mu^{(r)}_{2},\frac{\alpha}{T^{(r)}_{1}}+\frac{\alpha}{T^{(r)}_{2}}\right).$
(5)

Let $\Phi(x)=\frac{1}{\sqrt{2\pi}}\int_{-\infty}^{x}e^{-\frac{x^{2}}{2}}dx$ be
the cumulative distribution function (CDF) of $\mathcal{N}(0,1)$. By (4) and
(5), we have

$\displaystyle\Pr[Z>0]$ $\displaystyle=$
$\displaystyle\Phi\left(\frac{\mu^{(r)}_{1}-\mu^{(r)}_{2}}{\sqrt{\frac{\alpha}{T^{(r)}_{1}}+\frac{\alpha}{T^{(r)}_{2}}}}\right)$
$\displaystyle\geq$
$\displaystyle\Phi\left(-\sqrt{2}\cdot\sqrt{\frac{\alpha}{\ln(2T)}}\right)$
$\displaystyle\geq$ $\displaystyle\Phi\left(-\sqrt{2}\right)>0.01=1/\beta,$

where the first inequality is due to the monotonicity of the $\Phi(\cdot)$
function. ∎

The next lemma states that after being pulled for a sufficient number of
times, arm $2$ will be pruned at Line 1.

######  Lemma 6.

When $T^{(r)}_{2}>\frac{100\beta\ln(2T)}{\Delta^{2}}$ for some $r\geq 1$, we
have $\Pr[X^{(r)}_{2}>X^{(r)}_{1}]<{1}/{\beta}$.

###### Proof.

First, by the pruning condition at Line 1 of Algorithm 1, in any batch $r$
when there are still two arms left, we have

$\frac{q_{1}^{(r)}}{q_{2}^{(r)}}\in\left[\frac{1}{\beta},\beta\right]\quad\text{or}\quad\frac{T_{1}^{(r)}}{T_{2}^{(r)}}\in\left[\frac{1}{\beta},\beta\right].$
(6)

If $T^{(r)}_{2}>\frac{100\beta\ln(2T)}{\Delta^{2}}$, then by (6) we have
$T^{(r)}_{1}>\frac{100\ln(2T)}{\Delta^{2}}$. Conditioned on event
$\mathcal{E}$, we have
$\left|\mu^{(r)}_{i}-\mu_{i}\right|\leq\frac{\Delta}{10}$ for $i=1,2$. Since
$\mu_{1}-\mu_{2}=\Delta$, we have

$\mu^{(r)}_{1}-\mu^{(r)}_{2}\geq\frac{8}{10}\Delta.$ (7)

Let $Z\triangleq X^{(r)}_{2}-X^{(r)}_{1}$. We have
$\Pr[X^{(r)}_{2}>X^{(r)}_{1}]=\Pr[Z>0]$, where

$Z\sim\mathcal{N}\left(\mu^{(r)}_{2}-\mu^{(r)}_{1},\frac{\alpha}{T^{(r)}_{1}}+\frac{\alpha}{T^{(r)}_{2}}\right).$
(8)

By (7) and (8), we get

$\displaystyle\Pr[Z>0]$ $\displaystyle=$
$\displaystyle\Phi\left(\frac{\mu^{(r)}_{2}-\mu^{(r)}_{1}}{\sqrt{\alpha/T^{(r)}_{1}+\alpha/T^{(r)}_{2}}}\right)$
$\displaystyle\leq$
$\displaystyle\Phi\left(-\frac{8\Delta}{10}\cdot\frac{1}{\sqrt{2}(\Delta/10)}\right)$
$\displaystyle=$
$\displaystyle\Phi\left(-\frac{8}{\sqrt{2}}\right)<10^{-4}<1/\beta,$

where in the first inequality we have used the fact that
$T^{(r)}_{1},T^{(r)}_{2}>\frac{100\ln(2T)}{\Delta^{2}}$. ∎

Now we are ready to bound the expected regret. It is easy to see from the
description of the algorithm that for any $r$ we have
$\gamma^{(r+1)}/(\beta+1)\leq T^{(r)}_{i}\leq\gamma^{(r+1)}$. We thus have

$T^{(r+1)}_{i}/T^{(r)}_{i}\leq 2\gamma\beta.$ (9)

Consider the largest index $r$ such that
$T^{(r)}_{2}<\frac{100\beta\ln(2T)}{\Delta^{2}}$. We have
$T^{(r+1)}_{2}\geq\frac{100\beta\ln(2T)}{\Delta^{2}}$, and thus arm $2$ will
be pruned in the $(r+1)$-th batch. By (9) we also have $T^{(r+1)}_{2}\leq
2\gamma\beta T^{(r)}_{2}\leq\frac{200\gamma\beta^{2}\ln(2T)}{\Delta^{2}}$.
Therefore, we can bound

$\mathbf{E}[\text{Reg}_{T}(\pi)\ |\ \mathcal{E}]\leq\Delta
T^{(r)}_{2}\leq\frac{200\gamma\beta^{2}\ln(2T)}{\Delta}.$ (10)

Plugging (10) to (2) we get
$\mathbf{E}[\text{Reg}_{T}(\pi)]=O\left(\frac{T^{1/M}\ln T}{\Delta}\right)$
(recall that we have set $\beta=100$ and $\gamma=T^{1/M}$).

##  3 Instance-Independent Algorithm

In this section, we present a batched TS-based algorithm whose regret is
independent of the input instance. We will reuse the notations
$T^{(r)},T^{(r)}_{i}$, and $\mu^{(r)}_{i}$ defined in Section 2. The algorithm
is described in Algorithm 2.

Let us describe Algorithm 2 briefly in words. Same as Algorithm 1, at the
beginning of each batch $r$, we compute for each $i\in[N]$ the probability
$q^{(r)}_{i}$ such that the sample from distribution
$\mathcal{N}\left(\mu^{(r)}_{i},\alpha/T^{(r)}_{i}\right)$ is larger than
samples from $\mathcal{N}\left(\mu^{(r)}_{j},\alpha/T^{(r)}_{j}\right)$ for
$j\in I^{(r)},j\neq i$. We then prune all arms $i$ whose corresponding
$q^{(r)}_{i}$ is smaller than $q^{(r)}$, where $q^{(r)}$ is the maximum value
among all $q^{(r)}_{i}\ (i\in[N])$. The main difference between Algorithm 2
and Algorithm 1 lies in the number of pulls on each surviving arm in each
batch: In Algorithm 2, the values $T^{(r)}$ are chosen such that the lengths
of batches grow much faster. In each batch of Algorithm 2, the number of pulls
on each arm $i$ is again proportional to $q^{(r)}_{i}$.

Input: A set of $N$ arms $\\{1,\ldots,N\\}$, time horizon $T$, #batches $M$,
parameters $\alpha,\beta$

1

2Initialize $I^{(1)}\leftarrow I$;

3 Pull each arm once; For each $i\in[N]$, $T^{(1)}_{i}\leftarrow 1$, and
$\mu^{(1)}_{i}\leftarrow\text{reward of pulling arm $i$}$ ;

4 Let $a\leftarrow(T-N)^{\frac{1}{2-2^{1-M}}}$ ;

5 Set $u_{1}\leftarrow a$, and $u_{r}\leftarrow a\sqrt{u_{r-1}}$ for
$r=2,\dotsc,M$ ;

6 Set $T^{(1)}\leftarrow N$, and $T^{(r)}\leftarrow\lfloor u_{r-1}\rfloor+N$
for $r=2,\dotsc,M+1$;

7 for  _$r=1,\dotsc,M$_ do

8 $\forall i\in I^{(r)}$, let $X^{(r)}_{i}$ denote the random variable
distributed according to
$\mathcal{N}\left(\mu^{(r)}_{i},\alpha/T^{(r)}_{i}\right)$ ;

9 foreach  _$i\in I^{(r)}$_ do
$q^{(r)}_{i}\leftarrow\Pr\left[X^{(r)}_{i}>\max\limits_{j\in I^{(r)},j\neq
i}X^{(r)}_{j}\right]$;

10 $q^{(r)}\leftarrow\max\limits_{i\in I^{(r)}}q^{(r)}_{i}$ ;

11 $I^{(r+1)}\leftarrow\left\\{q^{(r)}_{i}\geq q^{(r)}/\beta\mid i\in
I^{(r)}\right\\}$ ;

12 foreach  _$i\in I^{(r+1)}$_ do
$\hat{q}^{(r)}_{i}=q^{(r)}_{i}/\sum\limits_{j\in I^{(r+1)}}q^{(r)}_{j}$;

13 foreach  _$i\in I^{(r+1)}$_ do

14 pull arm $i$ for $\hat{q}^{(r)}_{i}\cdot(T^{(r+1)}-T^{(r)})$ times; set
$T_{i}^{(r+1)}\leftarrow
T^{(r)}_{i}+\hat{q}^{(r)}_{i}\cdot(T^{(r+1)}-T^{(r)})$ ;

15 compute $\mu^{(r+1)}_{i}$ using $\mu^{(r)}_{i}$, $T^{(r)}_{i}$ and the pull
outcomes on arm $i$ in the current batch ;

16

17

Algorithm 2 Batched-TS-I$(N,T,\alpha,\beta,M)$

Analysis.  Our theoretical analysis for Algorithm 2 is again for the case when
$N=2$.

######  Theorem 7.

Setting $\alpha=\ln(2T)$ and $\beta=100$, Batched-TS-I$(2,T,\alpha,\beta,M)$
(Algorithm 2) has the expected regret at most
$O\left(T^{1/(2-2^{1-M})}\sqrt{\ln T}\right)$ and uses at most $M+1$ batches.

###### Proof.

The proof for Theorem 7 is similar to that for Theorem 1, and we will reuse
some notations and lemmas.

We again condition on the event $\mathcal{E}$ defined in (2), and focus on the
quantity $\mathbf{E}[\text{Reg}_{T}(\pi)\mid\mathcal{E}]$. W.l.o.g., we still
assume arm $1$ is the best arm. By the pruning step at Line 2 of Algorithm 2,
we again have that in any batch $r$ when there are still two arms left, we
have $T_{1}^{(r)}/T_{2}^{(r)}\in[1/\beta,\beta]$.

Recall that $\Delta\triangleq\Delta_{2}$ is defined to be the gap between the
means of the two arms. In the case when
$\Delta<\sqrt{\frac{100\beta\ln(2T)}{T}}$, the regret can be bounded by

$\displaystyle\text{Reg}_{T}(\pi)$ $\displaystyle\leq$ $\displaystyle
T\Delta\leq\sqrt{100\beta T\ln(2T)}$ $\displaystyle=$ $\displaystyle
O\left(T^{1/(2-2^{1-M})}\sqrt{\ln T}\right)$

for any integer $M\geq 1$.

We next consider the case when $\Delta\geq\sqrt{\frac{100\beta\ln(2T)}{T}}$.
Consider the number of pulls on arm $2$. If
$T_{2}^{(r)}\leq\frac{100\beta\ln(2T)}{\Delta^{2}}$ for any batch $r$, then
the regret is bounded by

$\displaystyle\Delta T^{(r)}_{2}$ $\displaystyle\leq$
$\displaystyle\frac{100\beta\ln(2T)}{\Delta}\leq\sqrt{100\beta T\ln(2T)}$
$\displaystyle=$ $\displaystyle O\left(T^{1/(2-2^{1-M})}\sqrt{\ln T}\right)$

for any integer $M\geq 1$.

Otherwise, let $m$ be the smallest index such that
$T^{(m)}_{2}>\frac{100\beta\ln(2T)}{\Delta^{2}}$. We thus have
$T^{(m-1)}_{2}\leq\frac{100\beta\ln(2T)}{\Delta^{2}}$, and consequently,

$\displaystyle T^{(m-1)}$ $\displaystyle=$ $\displaystyle
T^{(m-1)}_{1}+T^{(m-1)}_{2}$ $\displaystyle\leq$
$\displaystyle(1+\beta)\frac{100\beta\ln(2T)}{\Delta^{2}}$ $\displaystyle\leq$
$\displaystyle\frac{200\beta^{2}\ln(2T)}{\Delta^{2}}.$

By our choices of $T^{(r)}$ we have

$\displaystyle T^{(m)}$ $\displaystyle\leq$ $\displaystyle
a\sqrt{T^{(m-1)}}\leq a\cdot\frac{20\beta\sqrt{\ln(2T)}}{\Delta}$
$\displaystyle\leq$ $\displaystyle 20\beta
T^{{1}/{(2-2^{1-M})}}\cdot\frac{\sqrt{\ln(2T)}}{\Delta}.$

It is easy to see that Lemma 5 still holds in the setting of Algorithm 2. We
thus have that arm $1$ will never be pruned. Next, by Lemma 6, after the
$m$-th batch, arm $2$ will be pruned. Therefore, the total regret of Algorithm
2 can be bounded by

$\Delta\cdot 20\beta
T^{\frac{1}{2-2^{1-M}}}\cdot\sqrt{\ln(2T)}\cdot{1}/{\Delta}=O\left(T^{{1}/{(2-2^{1-M})}}\sqrt{\ln
T}\right).$

Finally, it is clear that the total number of batches used by Algorithm 2 is
$(M+1)$ where the extra batch is due to the initialization step (Line 2). ∎

Setting $M=\log\log T-1$, we have the following corollary.

######  Corollary 8.

Batched-TS-I$(2,T,\ln(2T),100,\log\log T-1)$ has the expected regret at most
$O(\sqrt{T\ln T})$ and uses at most $\log\log T$ batches.

##  4 Experiments

We have implemented and tested Batched-TS-D (Algorithm 1, BTSD for short) and
Batched-TS-I (Algorithm 2, BTSI for short). By default, we set parameters
$\alpha=1$, $\beta=100$, and round parameter $M=20$. We slightly modified BTSI
by removing the initialization batch and perform the same number of pulls on
each arm in the subsequent batch. The motivation for such a modification is
that the information about empirical means of the arms collected by the
initialization batch (one pull on each arm) is very limited, and thus the
subsequent first Thompson sampling batch is close to a uniform pull. With this
modification we can save one batch of computation.

We note that in Theorem 1 and 7 we have set $\alpha=\ln(NT)$ for the two
algorithms to facilitate the theoretical analysis (more precisely, to use the
union bound in Lemma 4), but in the experimental study we found that
$\alpha=1$, which is also the parameter used in the standard Thompson
sampling, already gives good performance. A more careful tuning of the
parameters $\alpha,\beta$ will give better performance for BTSD and BTSI on
individual datasets, but we choose not to optimize it for the sake of
demonstrating the robustness of our proposed algorithms.

As mentioned previously, we also test the performance of the two algorithms if
we remove their pruning steps. We denote the two corresponding algorithms
BTSD- and BTSI-.

We compare BTSD and BTSI with two sets of existing algorithms. The first set
is two fully sequential algorithms. (1) TS(Agrawal and Goyal 2012): the
standard Thompson sampling algorithm for multi-armed bandits. (2) UCB(Auer,
Cesa-Bianchi, and Fischer 2002): the standard upper bound confidence algorithm
for multi-armed bandits.

The second set is four batched algorithms. For all these algorithms, we set
the parameters such that the maximum number of batches is $20$. (1) BSE(Gao et
al. 2019): an elimination based algorithm with instance-dependent bounds using
$\Theta(\log T)$ batches. (2) BAE(Gao et al. 2019): an elimination based
algorithm with instance-independent bounds using $\Theta(\log\log T)$ batches.
(3) UCBI(Auer and Ortner 2010): the improved-UCB algorithm in (Auer and Ortner
2010) which can naturally be implemented in the batched setting with
$\Theta(\log T)$ batches. (4) KMS (Karbasi, Mirrokni, and Shadravan 2021): a
batched Thompson sampling algorithm with Gaussian prior using $\Theta(N\log
T)$ batches.

For all the tested algorithms, once there is only one arm left after some
batch (that is, the algorithm “converges” to the best arm), we make the rest
pulls a single batch.

Datasets and Experimental Environments.  We use a combination of synthetic and
real datasets. In all datasets we have a set of arms under Bernoulli
distributions with means $\mu_{i}\ (i\in[N])$. In the first three datasets we
have two arms ($N=2$) with the following means.

  * DS1: $\mu_{1}=0.9$ and $\mu_{2}=0.6$;

  * DS2: $\mu_{1}=0.9$ and $\mu_{2}=0.8$;

  * DS3: $\mu_{1}=0.55$ and $\mu_{2}=0.45$.

In the next three datasets we have ten arms ($N=10$) with the following means.

  * DS4 (one-shot): $\mu_{1}=0.9$, and for $\forall{i}\neq 1:\mu_{i}=0.8$;

  * DS5 (uniform): $\mu_{i}=0.9-(i-1)/20$;

  * DS6 (clustered): $\mu_{1}=0.9$, $\mu_{2}=\mu_{3}=\mu_{4}=0.8$, $\mu_{5}=\mu_{6}=\mu_{7}=0.7$, $\mu_{8}=\mu_{9}=\mu_{10}=0.6$.

We also test on a real-world dataset MovieLens (Harper and Konstan 2016).

  * MOVIE: We select the movies scored by at least $20,000$ users; there are 588 such movies. For the $i$-th movie, we set $\mu_{i}\in[0,1]$ as the average rating divided by $5$.

Figure 1: Regret on DS1 – DS6. Curves for BTSD- and TS almost overlap; curves
for BTSI and BTSI- almost overlap.

Figure 2: Regret and #batch on DS1 – DS3. Curves for batch costs of BTSI and
BSE almost overlap

We measure the regret and the number of batches used by the aforementioned
algorithms over a sequence of arm pulls on these datasets. The results are
average over $100$ runs. Error bars measure the standard deviation.

All algorithms were implemented using the Kotlin programming language. All
experiments were conducted in PowerEdge R740 server equipped with
$2\times$Intel Xeon Gold 6248R 3.0GHz (24-core/48-thread per CPU) and 256GB
RAM.

Experiments and Results.  Our experiments consist of three parts. We first
compare our algorithms BTSI/BTSI- and BTSD/BTSD- with TS and UCB in the
sequential setting on datasets DS1-DS6. The results are described in Figure 1.
We have the following assumptions. The performance of BTSD- is close to BTSD,
and is almost identical with the standard fully adaptive Thompson sampling TS.
The performance of BTSD is even better than TS, and is much better than UCB;
the former may due to the active pruning step in BTSD. The performance of
BTSI- is almost identical with BTSI; both are worse than BTSD. This is mainly
because BTSI uses fewer batches and larger batch sizes at the beginning; we
will present their batch costs in the next set of experiments.

Figure 3: Regret and #batch on DS4 – DS6. Curves for batch costs of BTSI and
BSE almost overlap

We next compare our algorithms BTSI and BTSD with BSE, BAE, UCBI, and KMS in
the batched setting on DS1-DS6. The results are described in Figure 2 and 3.
We observe that in terms of regret, both BTSI and BTSD significantly
outperform BSE, BAE, and UCBI. Similar to that in Figure 1, BTSD outperforms
BTSI in regret. The performance of KMS is between BTSD and BTSI. Regarding the
batch cost, we observe that BTSI performs almost the same as BSE; the two have
the smallest batch costs. BTSD performs similarly to BAE. These phenomena are
not surprising since in both BTSD and BAE the batch size increases single
exponentially, while in both BTSI and BSE the batch sizes are designed
essentially the same and increase much faster than single exponential. The
performance of UCBI is always in the middle, and have the same trend as BTSD
and BSE. This is because the batch size of UCBI also grows single
exponentially but with different constant parameters. The batch complexity of
KMS is much larger than others.

Figure 4: Regret and #batch on MOVIE. In the left figure, curves for BTSD ,
BTSD- and TS almost overlap; in the middle figure, curves for BTSI and UCBI
almost overlap, and curves for BTSD and KMS almost overlap; in the right
figure, curves for BTSI and BSE overlap

Finally, we compare the algorithms on the real world dataset MOVIE. The
results are described in Figure 4. In the sequential setting (left subfigure),
BTSD performs similarly to TS, and outperforms UCB and BTSI. Again, BTSD-
performs similarly to BTSD, and BTSI- perform similarly (except for the last
point) to BTSI. In the batched setting (middle and right subfigures), BTSD and
KMS significantly outperforms competitors in regret. But like that on
synthetic datasets, the batch cost of KMS is much larger than BTSD and other
competitors BTSI performs similarly to UCBI in regret, and does better than
BSE and BAE. The batch cost of BTSI is still similar to BSE, and is better
than other competitors.

Conclusion.  We have observed the followings from our experiments: (1) Our
proposed algorithm BTSD slightly outperforms KMS, and significantly
outperforms all other state-of-the-art batched algorithms. But KMS has a
significant larger batch cost than all competitors. BTSD also performs
similarly to (or better than) the standard, fully adaptive, Thompson sampling
algorithm TS in regret. (2) BTSI and the existing algorithm BSE have the
smallest batch cost, but BTSI significantly outperforms BSE in regret.

##  5 Concluding Remarks

In this paper, we study batched Thompson sampling for regret minimization in
stochastic multi-armed bandits. We propose two algorithms and demonstrate
experimentally their superior performance compared with state-of-the-art in
the batched setting. We provide rigorous theoretical analysis for the special
case when there are two arms, and show that our algorithms achieve almost
optimal (up to a logarithmic factor) regret-batches tradeoffs. Due to some
technical challenges, we are not able to prove tight bounds for general $N$,
though we believe this is achievable (by properly choosing the parameters
$\alpha,\beta$); we leave it as future work.

## References

  * Agarwal et al. [2017] Agarwal, A.; Agarwal, S.; Assadi, S.; and Khanna, S. 2017.  Learning with Limited Rounds of Adaptivity: Coin Tossing, Multi-Armed Bandits, and Ranking from Pairwise Comparisons.  In _COLT_ , 39–75.
  * Agrawal and Goyal [2012] Agrawal, S.; and Goyal, N. 2012.  Analysis of Thompson Sampling for the Multi-armed Bandit Problem.  In _COLT_ , volume 23 of _JMLR Proceedings_ , 39.1–39.26. JMLR.org.
  * Agrawal and Goyal [2017] Agrawal, S.; and Goyal, N. 2017.  Near-Optimal Regret Bounds for Thompson Sampling.  _J. ACM_ 64(5): 30:1–30:24.
  * Auer, Cesa-Bianchi, and Fischer [2002] Auer, P.; Cesa-Bianchi, N.; and Fischer, P. 2002.  Finite-time Analysis of the Multiarmed Bandit Problem.  _Mach. Learn._ 47(2-3): 235–256.
  * Auer and Ortner [2010] Auer, P.; and Ortner, R. 2010.  UCB revisited: Improved regret bounds for the stochastic multi-armed bandit problem.  _Period. Math. Hung._ 61(1-2): 55–65.
  * Bai, Wu, and Chen [2013] Bai, A.; Wu, F.; and Chen, X. 2013.  Bayesian Mixture Modelling and Inference based Thompson Sampling in Monte-Carlo Tree Search.  In _NIPS_ , 1646–1654.
  * Bai et al. [2019] Bai, Y.; Xie, T.; Jiang, N.; and Wang, Y. 2019.  Provably Efficient Q-Learning with Low Switching Cost.  In _NeurIPS_ , 8002–8011.
  * Cesa-Bianchi, Dekel, and Shamir [2013] Cesa-Bianchi, N.; Dekel, O.; and Shamir, O. 2013.  Online Learning with Switching Costs and Other Adaptive Adversaries.  In _NIPS_ , 1160–1168.
  * Chapelle and Li [2011] Chapelle, O.; and Li, L. 2011.  An Empirical Evaluation of Thompson Sampling.  In _NIPS_ , 2249–2257.
  * Dong et al. [2020] Dong, K.; Li, Y.; Zhang, Q.; and Zhou, Y. 2020.  Multinomial Logit Bandit with Low Switching Cost.  In _ICML_ , volume 119 of _Proceedings of Machine Learning Research_ , 2607–2615. PMLR.
  * Duchi, Ruan, and Yun [2018] Duchi, J. C.; Ruan, F.; and Yun, C. 2018.  Minimax Bounds on Stochastic Batched Convex Optimization.  In _COLT_ , 3065–3162.
  * Esfandiari et al. [2019] Esfandiari, H.; Karbasi, A.; Mehrabian, A.; and Mirrokni, V. S. 2019.  Batched Multi-Armed Bandits with Optimal Regret.  _CoRR_ abs/1910.04959.
  * Ferreira, Simchi-Levi, and Wang [2018] Ferreira, K. J.; Simchi-Levi, D.; and Wang, H. 2018.  Online Network Revenue Management Using Thompson Sampling.  _Oper. Res._ 66(6): 1586–1602.
  * Gao et al. [2019] Gao, Z.; Han, Y.; Ren, Z.; and Zhou, Z. 2019.  Batched Multi-armed Bandits Problem.  In _NeurIPS_.
  * Graepel et al. [2010] Graepel, T.; Candela, J. Q.; Borchert, T.; and Herbrich, R. 2010.  Web-Scale Bayesian Click-Through rate Prediction for Sponsored Search Advertising in Microsoft’s Bing Search Engine.  In _Proceedings of the 27th International Conference on Machine Learning (ICML-10), June 21-24, 2010, Haifa, Israel_ , 13–20. Omnipress.
  * Harper and Konstan [2016] Harper, F. M.; and Konstan, J. A. 2016.  The MovieLens Datasets: History and Context.  _TiiS_ 5(4): 19:1–19:19.  URL https://doi.org/10.1145/2827872.
  * Hill et al. [2017] Hill, D. N.; Nassif, H.; Liu, Y.; Iyer, A.; and Vishwanathan, S. V. N. 2017.  KDD.  1813–1821. ACM.
  * Jin et al. [2019] Jin, T.; Shi, J.; Xiao, X.; and Chen, E. 2019.  Efficient Pure Exploration in Adaptive Round model.  In _NeurIPS_ , 6605–6614.
  * Jin et al. [2020] Jin, T.; Xu, P.; Shi, J.; Xiao, X.; and Gu, Q. 2020.  MOTS: Minimax Optimal Thompson Sampling.  _CoRR_ abs/2003.01803.
  * Jun et al. [2016] Jun, K.; Jamieson, K. G.; Nowak, R. D.; and Zhu, X. 2016.  Top Arm Identification in Multi-Armed Bandits with Batch Arm Pulls.  In _AISTATS_ , 139–148.
  * Karbasi, Mirrokni, and Shadravan [2021] Karbasi, A.; Mirrokni, V. S.; and Shadravan, M. 2021.  Parallelizing Thompson Sampling.  _CoRR_ abs/2106.01420.  URL https://arxiv.org/abs/2106.01420.
  * Kaufmann, Korda, and Munos [2012] Kaufmann, E.; Korda, N.; and Munos, R. 2012.  Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis.  In _ALT_ , volume 7568 of _Lecture Notes in Computer Science_ , 199–213. Springer.
  * Kawale et al. [2015] Kawale, J.; Bui, H. H.; Kveton, B.; Tran-Thanh, L.; and Chawla, S. 2015.  Efficient Thompson Sampling for Online Matrix-Factorization Recommendation.  In _NIPS_ , 1297–1305.
  * Perchet et al. [2015] Perchet, V.; Rigollet, P.; Chassang, S.; and Snowberg, E. 2015.  Batched Bandit Problems.  In _COLT_ , 1456.
  * Scott [2010] Scott, S. L. 2010.  A Modern Bayesian Look at the Multi-Armed Bandit.  _Applied Stochastic Models in Business and Industry_ 26(6): 639–658.
  * Thompson [1933] Thompson, W. R. 1933.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  _Biometrika_ 25(3/4): 285–294.


# A Deep Learning System for
Sentiment Analysis of Service Calls

Yanan Jia
Businessolver / Bellevue, WA
<EMAIL_ADDRESS>
&Sony SungChu
Businessolver / Bellevue, WA
<EMAIL_ADDRESS>

###### Abstract

Sentiment analysis is crucial for the advancement of artificial intelligence
(AI). Sentiment understanding can help AI to replicate human language and
discourse. Studying the formation and response of sentiment state from well-
trained Customer Service Representatives (CSRs) can help make the interaction
between humans and AI more intelligent.

In this paper, a sentiment analysis pipeline is first carried out with respect
to real-world multi-party conversations–that is, service calls. Based on the
acoustic and linguistic features extracted from the source information, a
novel aggregated method for voice sentiment recognition framework is built.
Each party’s sentiment pattern during the communication is investigated along
with the interaction sentiment pattern between all parties.

##  1 Introduction

The natural reference for AI systems is human behavior. In human social life,
emotional intelligence is important for successful and effective
communication. A human has the natural ability to comprehend and react to the
emotion of their communication partners through vocal and facial expressions
[14, 30]. A long-standing goal of AI has been to create affective agents that
can recognize, interpret and express emotions.

Early-stage research in affective computing and sentiment analysis has mainly
focused on understanding affect towards entities such as movie, product,
service, candidacy, organization, action and so on in monologues, which
involves only one person’s opinion. However, with the advent of Human-Robot
Interaction (HRI) such as voice assistants and customer service chatbots,
researchers have started to build empathetic dialogue systems to improve the
overall HRI experience by adapting to customers’ sentiment.

Sentiment study of Human-Human Interactions (HHI) can help machines identify
and react to human non-verbal communication which makes the HRI experience
more natural. The call center is a rich resource of communication data. A
large number of calls are recorded daily in order to assess the quality of
interactions between CSRs and customers. Learning the sentiment expressions
from well-trained CSRs during communication can help AI understand not only
what the user says, but also how he/she says it so that the interaction feels
more human.

In this paper, we target and use real-world data – service calls, which poses
additional challenges with respect to the artificial datasets that have been
typically used in the past in multimodal sentiment researches, such as
variability and noises. The basic ‘sentiment’ can be described on a scale of
approval or disapproval, good or bad, positive or negative, and termed
polarity [31].

In the service industry, the key task is to enhance the quality of services by
identifying issues that may be caused by systems, rules, or service qualities.
These issues are usually expressed by a caller’s anger or disappointment on a
call. In addition, service chatbots are widely used to answer customer calls.
If customers get angry during HRI, the system should be able to transfer the
customers to a live agent. In this study, we mainly focused on identifying
‘negative’ sentiment, especially ‘angry’ customers. Given the non-homogeneous
nature of full call recordings, which typically include a mixture of negative,
and nonnegative statements, sentiment analysis is addressed at the sentence
level. Call segments are explored in both acoustic and linguistic modalities.
The temporal sentiment patterns between customers and CSRs appearing in calls
are described.

The paper is organized as follows: Section 2 covers a brief literature review
on sentiment recognition from different modalities; Section 3 proposes a
pipeline which features our novelties in training data creation using real-
world multi-party conversations, including a description of the data
acquisition, speaker diarization, transcription, and semi-supervised learning
annotation; the methodology for acoustic and linguistic sentiment analysis are
presented in Section 4; Section 5 illustrates the methodology adopted for
fusing different modalities; Section 6 presents experimental results including
the evaluation measures and temporal sentiment patterns; finally, Section 7
concludes the paper and outlines future work.

##  2 Related Work

In this section, we provide a brief overview of related work about text-based
and audio-based sentiment analysis.

###  2.1 Text-based Sentiment Analysis

Sentiment analysis has focused primarily on the processing of text and mainly
consists of either rule-based classifiers that make use of large sentiment
lexicons, or data-driven methods that assume the availability of a large
annotated corpora.

Sentiment lexicon is a list of lexical features (e.g. words) which are
generally labeled according to their semantic orientation as either positive
or negative [15]. Widely used lexicons include binary polarity-based lexicons
such as Harvard General Inquirer [36], Linguistic Inquiry and Word Count
(LIWC, pronounced ‘Luke’) [27, 26], Bing [16], and valence-based lexicons,
such as AFINN [22], SentiWordNet [2], and SnticNet [6]. Employing these
lexical, researchers can apply their own rules or use existing rule-based
modeling, such as VADER [12] to do sentiment analysis.

One big advantage for the rule-based model is that these approaches require no
training data and generalizes to multiple domains. However, since words are
annotated based on their context-free semantic orientation, word-sense
disambiguation [12] may occur when the word has multiple meanings. For
example, words like ‘defeated’, ‘envious’, and ‘stunned’ are classified as
‘positive’ in Bing, but ‘-2’ (negative) in AFINN. Although the rule-based
algorithm is known to be noisy and limited, a sentiment lexicon is a useful
component for any sophisticated sentiment detection algorithm and is one of
the main resources to start from [31].

Another major line of work in sentiment analysis consists of data-driven
methods based on a large dataset annotated for polarity. The most widely used
datasets include the MPQA corpus which is a collection of manually annotated
news articles [39, 40], movie reviews with two polarity [25], a collection of
newspaper headlines annotated for polarity [37]. With a large annotated
datasets, supervised classifiers have been applied [10, 35]. Such approaches
step away from blind use of keywords and word co-occurrence count, but rather
rely on the implicit features associated with large semantic knowledge bases
[4].

###  2.2 Audio-based Sentiment Analysis

Vocal expression is a primary carrier of affective signals in human
communication. Speech as signals contains several features that can extract
linguistic, speaker-specific information, and emotional. Related work about
audio-based sentiment analysis along with multimodal fusion is reviewed in
this section.

Studies on speech-based sentiment analysis have focused on identifying
relevant acoustic features. Use open source software such as OpenEAR [9],
openSMILE [8], JAudio toolkit [18] or library packages [19, 38] to extract
features. Those features along with some of their statistical derivates are
closely related to the vocal prosodic characteristics, such as a tone, a
volume, a pitch, an intonation, an inflection, a duration, etc.

Supervised or unsupervised classifiers can be fitted based on the statistical
derivates of those features [13, 24]. Sequence models can be fitted based on
filter banks, Mel-frequency cepstral coefficients (MFCCs), or other low-level
descriptors extracted from raw speech without feature engineering [1].
However, this approach usually requires highly efficient computation and large
annotated audio files.

Multimodal sentiment analysis has started to draw attention recently because
of the unlimited multimodality source of information online, such as videos
and audios [28, 29, 5]. Most of the multimodal sentiment analysis today is
focused on monologue videos. In the last few years, sentiment recognition in
conversation has started to gain research interest, since reproducing human
interaction requires a deep understanding of the conversation, and sentiment
plays a pivotal role in conversations. The existing conversation datasets are
usually recorded in a controlled environment, such as a lab, and segmented
into utterances, transcribe to text and annotated with emotion or sentiment
labels manually. Widely used dataset includes AMI Meeting Corpus [7], IEMOCAP
[3], SEMAINE [21] and AVEC [33].

Recently, a few recurrent neural network (RNN) models are developed for
emotion detection in conversations, e.g. DialogueRNN [17] or ICON[11]. However
they are less accurate in emotion detection for the utterances with emotional
shift [32] and the training data requires the speaker information. The
conversation models are not employed in our polarity sentiment analysis
because of the quality of the data and the approach used to gain the training
data. More detailed explanations can be found in Section 3.4.

At the heart of any multimodal sentiment analysis engine is the multimodal
fusion. The multimodal fusion integrates all single modalities into a combined
single representation. Features are extracted from the data from each modality
independently. Decision-level fusion feeds the features of each modality into
separate classifiers and then combines their decisions. Feature-level fusion
concatenates the feature vectors obtained from all modalities and feeds the
resulting long vector into a supervised classifier. Recent research on multi-
modal fusion for sentiment recognition has been conducted at either the
feature level or decision level.

##  3 Dataset and Pipeline

The data resources used for our experiments are described in Section 3.1. Data
preparation including speech transcription and speaker diarization is
discussed in Section 3.2. The sentiment annotation guideline is introduced in
Section 3.3. Section 3.4 presents a semi-supervised learning annotation
pipeline that chains data preparation, model training, model deploying and
data monitor.

###  3.1 BSCD: Benefits Service Call Dataset

The main dataset we created in this paper consists of service calls collected
from a health care benefits Call Center (named BSCD). Calls are focused on
customers looking for help or support with company provided benefits such as
health insurance.

500 calls are collected from the call center database covering diverse topics,
such as insurance plan information, insurance id card, dependent coverage,
etc. The call data set had female and male speakers randomly selected with
their age ranging approximately from 16-80. Calls involving translators are
eliminated to keep only speakers expressing themselves in English. All the
calls are presented in Wave format with a sample rate of 8000 Hertz and
duration varying from 4 minutes to 26 minutes. All calls are pre-processed to
eliminate repetitive introductions. The beginning of each call contains an
introduction of the users’ company name by a robot. To address this issue, the
segment before the first pause (silence duration $>$ 1 second) is removed from
each call.

A robust computational model of sentiment analysis needs to be able to handle
real-world variability and noises. While the previous research on multimodal
sentiment or emotion analysis used audio and visual recorded in laboratory
settings [3, 20, 21]; the BSCD gathered real-world calls contains ambient
noise present in most audio recordings, as well as diversity in person-to-
person communication patterns. Both of these conditions result in difficulties
that need to be addressed in order to effectively extract useful data from
these sources.

###  3.2 Data Preparation

To discard noise and long pauses (silence duration $>$ 5 seconds) in calls,
Voice Activity Detection (VAD) is applied, followed by the application of
Automatic Speech Recognition (ASR) and Automatic Speaker Diarization (ASD) to
transcribe the verbal statements, extract the start and end time of each
utterance, and identify the speaker of each utterance. Each call is segmented
into an average of 69 utterances. The duration of the utterances is right-
skewed with a median of 2.9 seconds; first and third quantiles 1.6 and 5.1
seconds.

By searching keywords such as ‘How can I help’ in the content of each
utterance, speakers are labeled as CSR or customer. Each utterance is linked
to the corresponding audio stream, auto transcription, as well as speaker
label. The workflow and corresponding results for the first 23 seconds of one
selected call are shown in Figure 1, where the original input is a call audio
sample. After data preparation, segments of noise and silence are discarded.
This call sample is segmented into 4 utterances. The audio streams are from
the original audio and split based on the start and end time of each
utterance. Auto transcriptions are more likely to be ungrammatical if the
recording quality is bad or the conversation contains words that ASR cannot
identify or the speakers do not express themselves clearly. The ungrammatical
transcriptions usually occur in customer parts and the frequency of
ungrammaticality varies from case to case. Although the sentiment recognition
of a whole call tends to be robust with respect to speech recognition errors,
the sensitivity of each utterance analysis to ASR errors is not reparable
given our study. The Speaker labels are from ASD output which can be
misclassified because of the occurrence of speakers overlapping or speakers
with similar acoustic features. Conversation sentiment pattern study can be
misleading due to the misclassified ASD output, although misclassified ASD is
rare.

Figure 1: Data preparation workflow

This process allows us to study features from both modalities: transcribed
words and acoustics. Distinguishing different parties gives us the ability to
study the temporal sentiment transitions of individual speakers and
interactions among speakers in a conversation. However, since the data
preparation is part of the pipeline described in section 3.4, which runs in
real-time, sentiment analysis must rely on error-prone ASR and ASD outputs.

###  3.3 Sentiment Annotation

Sentiment annotation is a challenging task as the label depends on the
annotators’ perspective, and the differences inherent in the way people
express emotions. The sentiment is opinion-based, not fact-based. This study
aims at identifying negative expressions in calls, especially angry customers
who are not satisfied with the services and the business or system rules. By
identifying and studying those types of cases, the business can improve call
center services and fix the possible business or system issues.

Guidelines are set up for the annotation. The customer negative tag is for
negative emotions (e.g. “I hate the system”), attitudes (e.g. “I am not
following you”), evaluations (e.g. “your service is the worst”), and negative
facts caused by other parties (e.g. “I never received my card”). Other
negative facts are not considered as negative (e.g. “My wife died, I need to
remove her from my dependents”). The guidelines for CSRs are different. Well
trained CSRs usually do not respond negatively, but there are cases that they
cannot help the customers. We identify those cases as negative. Cases where a
CSR cannot help the customer usually involve business process or system
issues.

The sentiment is not always explicit in the text. Borderline linguistic
utterances stated loudly and quickly are usually identified as ‘negative’.
E.g. the utterance “Trust me, it could be done” is classified as negative,
since it is in the context that the representative fails to help the customer
to enroll in the health plan, and in the audio, the customer is irritated. In
all the multimodal sentiment analysis, the labels of all modalities are kept
consistent for the same utterance. In our data annotation process, we also
keep both text and audio labels that agree with each other and the annotation
is based on the audio segments.

###  3.4 Semi-supervised Learning Annotation Pipeline

Figure 2: Semi-supervised learning annotation pipeline

To successfully run and train analytical models, massive quantities of stored
data are needed. Creating large annotated datasets can be a very time
consuming and labor-intensive process. To keep the human annotation effort to
a minimum, a semi-supervised learning annotation scheme is applied to tag the
polarity of utterances as negative, or nonnegative. Figure 2 illustrates the
process which is similar to active learning annotation. It takes as input a
set of labeled examples $D_{L}$ including text $D_{LT}$ and audio $D_{LA}$, as
well as a larger set of unlabeled examples $D_{U}=\\{D_{UT},D_{UA}\\}$, and
produces committee classifiers $C=\\{C_{T},C_{A}\\}$ and a relatively small
set of newly labeled data $D_{U}^{\prime}(I)$ and $D_{U}^{\prime}(M)$ [23].

Semi-supervised learning annotation cooperates with humans and machines and
combines both semi-supervised learning and multiple classifiers approach for
corpus annotation. This pipeline consists of several steps: data generation to
obtain $D_{U}$ (Section 3.2), model training for both modalities to obtain
$C_{T}$ and $C_{A}$ (Section 4), model deployment to get machine label
$D_{U}^{\prime}=\\{D_{UT}^{\prime},D_{UA}^{\prime}\\}$, model fusion (Section
5) and results evaluation to decide whether to accept machine label
$D_{U}^{\prime}(M)$ or ask a human annotator for classifications of the
utterances to obtain $D_{U}^{\prime}(I)$, then move $D_{U}^{\prime}(I)$ and
$D_{U}^{\prime}(M)$ from $D_{U}^{\prime}$ to $D_{L}$. It is cyclical and
iterative as every step is repeated to continuously improve the accuracy of
the classifier and achieve a successful algorithm.

Note, the classifiers in committee $C=\\{C_{T},C_{A}\\}$ are modified based on
$D_{L}$ in each iteration. The annotation process starts with 20 calls
selected from the service center by human domain experts, 20 calls are chunked
to 1410 segments via data preparation processing and annotated by three
annotators manually as $D_{L}$. For the first three iterations, set
$C_{T}$={Support Vector Machine (SVM), VADER, AWSSA111AWS Comprehend Sentiment
Analysis API, AWSCC222AWS Custom Classification API, GoogleSA333Google
Language Sentiment Analysis API} requires a small size of training data or no
extra training data. As the size of $D_{LT}$ increases, we form a new
committee $C_{T}$ = {SVM, Long Short-Term Memory (LSTM), Bidirectional Long
Short-Term Memory (BLSTM)}. These classifiers are described in Section 4.1.
Section 4.2 introduced $C_{A}$ = {Elastic-Net Regularized Generalized Linear
Models (Elastic-Net), K-Nearest Neighbors (KNN), Random Forest (RF), Gaussian
Mixture Model (unsupervised GMM) }. In the later iterations, Recurrent Neural
Networks (RNN) such as LSTM and BLSTM are applied.

If one call has a long duration ($T>10$ minutes) and a high percentage of
negative utterances based on $D_{U}^{\prime}$ ($>40\%$ for customer or $>20\%$
for CSR), then we say this call is potentially negative and informative. We
then ask an annotator to manually correct the annotated tags $D_{U}^{\prime}$
by listening to the call, and move the results $D_{U}^{\prime}(I)$ to $D_{L}$.
For all the other calls, we only keep the utterances where classifiers all
agree as $D_{U}^{\prime}(M)$. We then remove chunks that are too short
(duration $<$ 1s) or too long (duration $>$20s). Finally, we discard chunks
where the annotator cannot discern classification.

Using the pipeline, 6,565 negative and 10,322 nonnegative call clips were
annotated as the training dataset. The training data $D_{LT}$ still include
transcription errors, even though the threshold discussed in the above
paragraph is set to eliminate those utterances to add to the training dataset.
In addition, 18,705 cleaned text chat data collected from chat windows are
also added to $D_{LT}$ via the annotation pipeline to improve the $C_{T}$
accuracy, the details are shown in Section 6.1.

Because of the quality of the calls, the poor performance of the ASR for some
cases, and the threshold used to annotate the utterances, more than half of
the original call segments are discarded***The accuracy on the test data
decreases 8% by including all the call segments in the training dataset and
18,705 text chat data are added to $D_{LT}$={transcription data, _chat data_}
without the corresponding audio files in $D_{LA}$. It is hard to consider the
context of the conversation since the segments are not continuing in the
training dataset. Therefore, conversation models are not considered in our
committee classifiers $C$.

##  4 Bimodal Sentiment Analysis

To model information for sentiment analysis from calls, we first obtain the
streams corresponding to each modality via the methods described in Section
3.2, followed by the extraction of a representative set of features for each
modality. These features are then used as cues to build a classifier of binary
sentiment.

###  4.1 Sentiment Analysis of Textual Data

General approaches such as sentiment lexical and sentiment APIs are easy to
apply. Both approaches are employed in $C_{T}$ to monitor the utterance
prediction labels in the early stage of semi-supervised learning annotation to
extend training data.

VADER [12] is a simple rule-based model for general sentiment analysis. The
results have four categories: compound, negative, neutral, and positive. We
classify utterances with negative output as negative, neutral and positive as
nonnegative†††. Utterances with compound or mixed class are very few, and they
are discarded to keep the training data clear so that it is consistent with
BSCD annotation. This model has many advantages, such as being less
computationally expensive and easily interpretable. However, one of the main
issues with only using lexicons is that most utterances do not contain
polarized words. The utterances without polarized words are usually classified
as neutral or nonnegative‡‡‡The high Rec(+) and low Rec(-) shown in table 1
verifies this conclusion..

Sentiment analysis API is another way to classify sentiment without extra
training data. Amazon offers Sentiment Analysis in Amazon Comprehend (AWSSA),
which uses machine learning to find insights and relationships in a text. The
result returns Mixed, Negative, Neutral, or Positive classification. To be
consistent with the BSCD we created, Neutral and Positive are combined as one
classifier: nonnegative. Another sentiment analysis on Google Cloud Natural
Language API (GoogleSA) also performs sentiment analysis on text. Sentiment
analysis attempts to determine the overall attitude and is represented by
numerical score and magnitude values. We simply set utterances with negative
scores as negative and nonnegative otherwise.

For machine learning-oriented techniques by linguistic features, we evaluated
well-known SVM, LSTM, and BLSTM models. Since the data is unbalanced and we
want the model to focus more on the negative class, we apply weighted loss
functions during the training. Hyperparameters are tuned for each model, and
ensemble models are also developed by taking the weighted majority vote.

Methods | Text | Audio
---|---|---
SVM | LSTM | BLSTM | Vader | AWS | Google | Elastic-Net | KNN | RF | GMM | BLSTM
Acc. | 0.814 | 0.853 | 0.843 | 0.498 | 0.651 | 0.637 | 0.570 | 0.544 | 0.585 | 0.546 | 0.601
F1 (w) | 0.814 | 0.852 | 0.842 | 0.347 | 0.628 | 0.615 | 0.500 | 0.534 | 0.549 | 0.500 | 0.584
Prec.(+) | 0.770 | 0.802 | 0.781 | 0.494 | 0.594 | 0.586 | 0.528 | 0.518 | 0.541 | 0.513 | 0.561
Prec.(-) | 0.871 | 0.92 | 0.934 | 0.742 | 0.821 | 0.779 | 0.860 | 0.589 | 0.741 | 0.685 | 0.693
Rec. (+) | 0.886 | 0.929 | 0.946 | 0.991 | 0.908 | 0.881 | 0.964 | 0.697 | 0.883 | 0.872 | 0.811
Rec. (-) | 0.746 | 0.779 | 0.745 | 0.024 | 0.404 | 0.402 | 0.205 | 0.402 | 0.309 | 0.252 | 0.402

Table 1: Binary classification of sentiment polarity on test data: Accuracy
(Acc.), weighted F1-score (F1 (w)), precision (Prec.) and recall (Rec.) for
the nonnegative (+) and negative (-) classes.

###  4.2 Sentiment Analysis of Acoustic Data

Feature engineering heavily relies on expert knowledge about data features. To
better understand the human hearing process, we study the acoustic features
based on human perception. Three perceptual categories are described in this
section. Their corresponding features are usually short-term based features
that are extracted from every short-term window (or frame). Long-term features
can be generated by aggregating the short-term features extracted from several
consecutive frames within a time window. For each short-term acoustic feature,
we calculated nine statistical aggregations: mean, standard deviation,
quantiles (5%, 25%, 50%, 75%, 95%), range (95%-5% quantile), and interquartile
range (75%-25% quantile) to get the long-term features of each segment.

  * •

Loudness is the subjective perception of sound pressure which is related to
sound intensity. Amplitude and mean frequency spectrum features are extracted
to measure loudness. The greater the amplitude of the vibrations, the greater
the amount of energy carried by the wave, and the more intense the sound will
be.

  * •

Sharpness is a measure of the high-frequency content of a sound, the greater
the proportion of high frequencies the ‘sharper’ the sound. Fundamental
frequency (pitch) and dominant frequency are extracted.

  * •

Speaking rate is normally defined as the number of words spoken per minute. In
general, the speaking rate is characterized by different parameters of speech
such as pause and vowel durations. In our study, speaking rate is measured by
pause duration, character per second (CPS), and word per second (WPS) which
are calculated as following for the $i$th segment:

$\text{Pause duration}_{i}=\frac{T^{silence}_{i}}{T^{total}_{i}}$
$\text{CPS}_{i}=\frac{N^{character}_{i}}{T^{total}_{i}},\hskip
28.45274pt\text{WPS}_{i}=\frac{N^{word}_{i}}{T^{total}_{i}}$

where for segment $i$, $T_{i}$ denotes the time, and $N_{i}$ denotes the
number of characters or words in the corresponding transcription. Pause
duration can be interpreted as the percentage of the time where the speaker
was silent. The three variables are aggregated statistics, long-term features.

In nonnegative cases, speakers are in a relaxed and normal emotional state. An
agitated or angry emotional state speaker will typically be characterized by
increased vocal loudness, sharpness, and speaking rate. $C_{A}$ ={Elastic-Net,
KNN, RF, GMM} are built based on the 39 selected features.

“Hand-crafted” features are generally very successful for specificity sound
analysis tasks. One of the main drawbacks of feature engineering is that it
relies on transformations that are defined beforehand and ignore some
particularities of the signals observed at runtime such as recording
conditions and recording devices. A more common approach is to select and
adapt features initially introduced for other tasks. A now well-established
example of this trend is the popularity of MFCC features [34]. In our
experiments, MFCC is extracted from each segment and fed to RNN models in
later iterations with $|D_{LA}|>10,000$.

Methods | Ensemble | Fusion
---|---|---
Text | Audio | T+A | Fus1 | Fus2
Acc. | 0.851 | 0.586 | 0.846 | 0.858 | 0.871
F1 (w) | 0.851 | 0.525 | 0.846 | 0.858 | 0.871
Prec.(+) | 0.779 | 0.531 | 0.800 | 0.790 | 0.818
Prec.(-) | 0.949 | 0.927 | 0.896 | 0.946 | 0.933
Rec. (+) | 0.953 | 0.979 | 0.894 | 0.950 | 0.933
Rec. (-) | 0.761 | 0.240 | 0.804 | 0.777 | 0.817

Table 2: Binary classification of sentiment polarity on both linguistic and
acoustic modalities.

##  5 Fusion

There are two main fusion techniques: feature-level fusion and decision-level
fusion. In our experiments, we employ decision-level fusion. Decision-level
fusion has many advantages [29]. One benefit of the decision-level fusion is
we can use classifiers for text and audio features separately. The unimodal
classifier can use data from another communication channel of the same type to
improve its accuracy, e.g. text data from the chat window is borrowed to
improve the $C_{T}$ accuracy in our study. Separating modalities permit us to
use any learner suitable for the particular problem at hand. Another benefit
of the decision-level fusion is its processing speed since fewer features are
used for each classifier and separate classifiers can be run in parallel.

Decision-level fusion usually adds probabilities or summarized prediction from
each unimodal classifier with weights or takes the majority voting among the
predicted class labels by unimodal classifiers.

In this paper, various fusion methods are evaluated, including a novel
approach that uses linguistic ensemble results as the baseline, while then
checking acoustic results to modify classification decisions. In Fus1, if the
audio ensemble classifies negative and one or more text models classifies
negative, we then reclassify the result to negative. In Fus2, if the audio
ensemble classifies a sample as negative, we then reclassify the result to
negative directly without checking the linguistic modality.

##  6 Experiment Results

The test dataset consists of 21 calls with 1,890 utterances, which are
manually annotated for negative (848) and nonnegative (1,042).

Figure 3: The (cumulative) negative score pattern between customers and CSRs

###  6.1 Evaluation Measures

As evaluation measures, we rely on accuracy and weighted F1-score, which is
the weighted harmonic mean of precision and recall. Precision is the
probability of returning values that were correct. Recall, also known as
sensitivity is the probability of relevant values that the algorithm outputs.

As shown in Table 1, general approaches in $C_{T}$, Vader and APIs, tend to
have a low negative recall. The semantic knowledge based classifiers have more
than 20% higher F1-score than the general approaches. The classifiers are
trained on $D_{LT}$={transcription data, chat data}. The overall F1-score is
more than 10% higher than the classifiers trained on call transcription only
data.

BLSTM on MFCC performs better than $C_{A}$ = {Elastic-Net (penalty
$0.2||\beta||_{1}+0.4||\beta||_{2}^{2}$), KNN ($k=3$), RF, GMM} on acoustic
features. Using audio features alone, an F1-score of 0.584 can be reached,
which is acceptable considering that the real world audio-only system
exclusively analyzes the tone of the speaker’s voice and doesn’t consider any
language information.

The acoustic modality is significantly weaker than the linguistic modality. In
most cases, text already includes enough information to judge the sentiment. A
few observed typical situations leading to linguistic modality
misclassification are the presence of misleading linguistic cues, ambiguous
linguistic utterances whose sentiment polarity are highly dependent on the
context described in earlier or later part of the call, or nonnegative
linguistic utterances stated angrily. In order to achieve better accuracy, we
combine the two modalities together to exploit complementary information.

We simply combine results of the three semantic knowledge based classifiers
and all the five audio classifiers by taking the weighted majority vote. The
T+A ensemble results are shown in Table 2 and they do not improve when
compared to the unimodal text ensemble results.

Since the unimodal performance of linguistic modality is notably better than
acoustic modality, our decision-level fusion methods use linguistic ensemble
results as the base-line, while acoustic results are used as supplemental
information to calibrate each classification. The Fus2 bimodal system
discussed in Section 5 yields a 2% improvement in F1-score than the text
unimodal system.

The acoustic modality provides important cues to identify negative emotions.
It can help correct misclassified nonnegative/ambiguous linguistic utterances.
Our results show that relying on the joint use of linguistic and acoustic
modalities allows us to better sense the sentiment being expressed as compared
to the use of only one modality at a time. The acoustic feature analysis helps
us to better understand the spoken intention of the speaker, which is not
normally expressed through text.

###  6.2 Tempo Sentiment Pattern

The sentiment is not only regarded as an internal psychological phenomena but
also interpreted and processed communicatively through social interactions.
Conversations exemplify such a scenario where inter-personal sentiment
influences persist.

The left panel in Figure 3 shows the negative scores of CRSs and customers in
the 21 test calls. The negative score, a weighted negative segment percentage,
is calculated to analyze the overall sentiment. Weights 0.8, 1, and 1.2 are
assigned to the first third, second third and last third of each call. The
negative scores of CRSs are usually lower than customers’, and usually high
negative scores for customers correspond to high negative scores for CSRs. We
can conclude from the figure that sentiment can be affected by other parties
during a conversation.

To further analyze the interactions between customers and CSRs, the cumulative
negative scores for call 6, 15, and 16 are drawn on the right panel of Figure
3. Call 6 shows the sentiment patterns of a typical bad call, which is
characterized by long duration and long hold. The customer has a high negative
score from beginning to end, and the CSR fails to help the customer during the
call. Call 15 is a typical good call. The overall negative score is low and
the negative score pattern goes down for both the customer and the CSR, which
means the problem is resolved by the end of the call. Call 16 is another type
of call, in which the customer does not get angry even though the CSR is
unable to solve his/her issues.

##  7 Discussion and Future Work

A new dataset BSCD consisting of real-world conversation, the service calls,
is introduced. Human communication is a dynamic process, our eventual goal is
to develop a bimodal sentiment analysis engine with the ability to learn the
temporal interaction sentiment patterns among conversation parties. In the
process of fusion, we have approached the study of audio sentiment analysis
from an angle that is somewhat different from most people’s.

Future research will concentrate on evaluations using larger data sets,
exploring more acoustic feature relevance analysis, and striving to improve
the decision-level fusion process.

A call is constituent of a group of utterances that have contextual
dependencies among them. However, in our semi-supervised learning annotation
pipeline, about half of the segments in calls are discarded. Therefore the
interdependent modeling is out of the scope of this paper and we include it as
future work.

## References

  * Aguilar et al. [2019] Gustavo Aguilar, Viktor Rozgic, Weiran Wang, and Chao Wang. 2019.  Multimodal and multi-view models for emotion recognition.
  * Alhazmi et al. [2013] Samah Alhazmi, Bill Black, and J McNaught. 2013.  Arabic sentiwordnet in relation to sentiwordnet 3.0.  _International Journal of Computational Linguistics_ , 4:1–11.
  * Busso et al. [2008] Carlos Busso, Murtaza Bulut, Chi-Chun Lee, Abe Kazemzadeh, Emily Mower Provost, Samuel Kim, Jeannette Chang, Sungbok Lee, and Shrikanth Narayanan. 2008.  Iemocap: Interactive emotional dyadic motion capture database.  _Language Resources and Evaluation_ , 42:335–359.
  * Cambria et al. [2015] Erik Cambria, J. Fu, Federica Bisio, and Soujanya Poria. 2015.  Affectivespace 2: Enabling affective intuition for concept-level sentiment analysis.  _Proc. AAAI_ , pages 508–514.
  * Cambria et al. [2017] Erik Cambria, Devamanyu Hazarika, Soujanya Poria, Amir Hussain, and Rbv Subramanyam. 2017.  Benchmarking multimodal sentiment analysis.  arXiv:1707.09538.  Version 1.
  * Cambria et al. [2010] Erik Cambria, Robyn Speer, C. Havasi, and Amir Hussain. 2010.  Senticnet: A publicly available semantic resource for opinion mining.  _AAAI Fall Symposium - Technical Report_ , pages 14–18.
  * Carletta et al. [2006] Jean Carletta, Simone Ashby, Sebastien Bourban, Mike Flynn, Mael Guillemot, Thomas Hain, Jaroslav Kadlec, Vasilis Karaiskos, Wessel Kraaij, Melissa Kronenthal, Guillaume Lathoud, Mike Lincoln, Agnes Lisowska, Iain McCowan, Wilfried Post, Dennis Reidsma, and Pierre Wellner. 2006.  The ami meeting corpus: A pre-announcement.  In _Proceedings of the Second International Conference on Machine Learning for Multimodal Interaction_ , pages 28–39, Berlin, Heidelberg. Springer-Verlag.
  * Eyben et al. [2010] Florian Eyben, Martin Wöllmer, and Björn Schuller. 2010.  opensmile – the munich versatile and fast open-source audio feature extractor.  _MM’10 - Proceedings of the ACM Multimedia 2010 International Conference_ , pages 1459–1462.
  * Eyben et al. [2009] Florian Eyben, Martin Wöllmer, and Björn Schuller. 2009.  Openear - introducing the munich open-source emotion and affect recognition toolkit.  _Affective Computing and Intelligent Interaction and Workshops, 2009\. ACII 2009. 3rd International Conference_ , pages 1 – 6.
  * Go et al. [2009] Alec Go, Richa Bhayani, and Lei Huang. 2009.  Twitter sentiment classification using distant supervision.  _CS224N Project Report_ , 150.
  * Hazarika et al. [2018] Devamanyu Hazarika, Soujanya Poria, Rada Mihalcea, Erik Cambria, and Roger Zimmermann. 2018.  Icon: Interactive conversational memory network for multimodal emotion detection.  pages 2594–2604.
  * Hutto and Gilbert [2015] C.J. Hutto and Eric Gilbert. 2015.  Vader: A parsimonious rule-based model for sentiment analysis of social media text.  _Proceedings of the 8th International Conference on Weblogs and Social Media, ICWSM 2014_.
  * Jain et al. [2018] Manas Jain, Shruthi Narayan, Pratibha Balaji, Abhijit Bhowmick, and Rajesh Muthu. 2018.  Speech emotion recognition using support vector machine.
  * Kotti and Paternò [2012] Margarita Kotti and Fabio Paternò. 2012.  Speaker-independent emotion recognition exploiting a psychologically-inspired binary cascade classification schema.  _Int J Speech Technol_ , 15.
  * Liu [2010] Bing Liu. 2010.  Sentiment analysis and subjectivity.  _Handbook of Natural Language Processing, Second Edition_.
  * Liu [2012] Bing Liu. 2012.  Sentiment analysis and opinion mining.  In _Synthesis Lectures on Human Language Technologies_.
  * Majumder et al. [2019] Navonil Majumder, Soujanya Poria, Devamanyu Hazarika, Rada Mihalcea, Alexander Gelbukh, and Erik Cambria. 2019.  Dialoguernn: An attentive rnn for emotion detection in conversations.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 33:6818–6825.
  * McEnnis et al. [2005] Daniel McEnnis, Cory McKay, Ichiro Fujinaga, and Philippe Depalle. 2005.  jaudio: An feature extraction library.  _Proceedings of the International Conference on Music Information Retrieval_ , pages 600–603.
  * McFee et al. [2015] Brian McFee, Colin Raffel, Dawen Liang, Daniel Ellis, Matt Mcvicar, Eric Battenberg, and Oriol Nieto. 2015.  librosa: Audio and music signal analysis in python.  _in Proceedings of the 14th Python in Science Conference_ , 8:18–24.
  * Mckeown et al. [2010] Gary Mckeown, Michel Valstar, Roddy Cowie, and Maja Pantic. 2010.  The semaine corpus of emotionally coloured character interactions.  _2010 IEEE International Conference on Multimedia and Expo, ICME 2010_ , pages 1079–1084.
  * Mckeown et al. [2013] Gary Mckeown, Michel Valstar, Roddy Cowie, Maja Pantic, and M. Schroder. 2013.  The semaine database: Annotated multimodal records of emotionally colored conversations between a person and a limited agent.  _Affective Computing, IEEE Transactions on_ , 3:5–17.
  * Nielsen [2011] Finn Nielsen. 2011.  A new anew: Evaluation of a word list for sentiment analysis in microblogs.  _CoRR_.
  * Olsson [2008] Fredrik Olsson. 2008.  Bootstrapping named entity annotation by means of active machine learning: a method for creating corpora.
  * Pan et al. [2012] Y Pan, P Shen, and L Shen. 2012.  Speech emotion recognition using support vector machine.  _Int. J. Smart Home_ , 6:101–108.
  * Pang and Lee [2004] Bo Pang and Lillian Lee. 2004.  A sentimental education: Sentiment analysis using subjectivity summarization based on minimum cuts.  _Computing Research Repository - CORR_ , 271-278:271–278.
  * Pennebaker et al. [2007] James Pennebaker, Cindy Chung, Molly Ireland, Amy Gonzales, and Roger Booth. 2007\.  The development and psychometric properties of liwc2007.
  * Pennebaker et al. [2001] James Pennebaker, M. Francis, and R. Booth. 2001.  Linguistic inquiry and word count (liwc): Liwc2001.  71\.
  * Poria [2016] Soujanya Poria. 2016.  Fusing audio, visual and textual clues for sentiment analysis from multimodal content.  _Neurocomputing_ , 174:50–59.
  * Poria et al. [2015] Soujanya Poria, Erik Cambria, and Alexander Gelbukh. 2015.  Deep convolutional neural network textual features and multiple kernel learning for utterance-level multimodal sentiment analysis.  In _Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing_ , pages 2539–2544, Lisbon, Portugal. Association for Computational Linguistics.
  * Poria et al. [2014a] Soujanya Poria, Erik Cambria, Amir Hussain, and Guang-Bin Huang. 2014a.  Towards an intelligent framework for multimodal affective data analysis.  _Neural Networks_ , 63.
  * Poria et al. [2014b] Soujanya Poria, Alexander Gelbukh, Erik Cambria, Amir Hussain, and Guang-Bin Huang. 2014b.  Emosenticspace: A novel framework for affective common-sense reasoning.  _Knowledge-Based Systems_ , 69.
  * Poria et al. [2019] Soujanya Poria, Navonil Majumder, Rada Mihalcea, and Eduard Hovy. 2019.  Emotion recognition in conversation: Research challenges, datasets, and recent advances.
  * Schuller et al. [2012] Björn Schuller, Michel Valstar, Roddy Cowie, and Maja Pantic. 2012.  Avec 2012 – the continuous audio/visual emotion challenge.  _ICMI’12 - Proceedings of the ACM International Conference on Multimodal Interaction_.
  * Serizel et al. [2018] Romain Serizel, Victor Bisot, Slim Essid, and Gaël Richard. 2018.  Acoustic features for environmental sound analysis.  _Computational Analysis of Sound Scenes and Events_ , pages 71–101.
  * Socher et al. [2013] Richard Socher, Alex Perelygin, Jean Y. Wu, Jason Chuang, Christopher D. Manning, Andrew .Y. Ng, and Christopher Potts. 2013.  Recursive deep models for semantic compositionality over a sentiment treebank.  _EMNLP_ , 1631:1631–1642.
  * Stone et al. [1966] Philip Stone, Dexter Dunphy, Marshall Smith, and Daniel Ogilvie. 1966.  _The General Inquirer: A Computer Approach to Content Analysis_, volume 4.
  * Strapparava and Mihalcea [2007] Carlo Strapparava and Rada Mihalcea. 2007.  Semeval-2007 task 14: Affective text.  _Proceedings of the 4th International Workshop on the Semantic Evaluations (SemEval 2007)_.
  * Sueur et al. [2008] Jerome Sueur, Thierry Aubin, and Caroline Simonis. 2008.  Seewave: a free modular tool for sound analysis and synthesis.  _Bioacoustics_ , 18:213–226.
  * Wiebe et al. [2005] Janyce Wiebe, Theresa Wilson, and Claire Cardie. 2005.  Annotating expressions of opinions and emotions in language.  _Language Resources and Evaluation (formerly Computers and the Humanities)_ , 39:164–210.
  * Wilson et al. [2005] Theresa Wilson, Janyce Wiebe, and Paul Hoffmann. 2005.  Recognizing contextual polarity in phrase-level sentiment analysis.  _Proceedings of HLT/EMNLP_.