11institutetext: Department of Computer Science and Engineering, Chittagong
University of Engineering and Technology,Chittagong 4349, Bangladesh,
22institutetext: Brac University, Dhaka, Bangladesh, 33institutetext: Pioneer
Alpha, 33email<EMAIL_ADDRESS>
# Incongruity Detection between Bangla News Headline and Body Content through
Graph Neural Network

Md Aminul Haque Palash0000-0002-4794-8531 11 Akib Khan0000-0002-1517-5319 22
Kawsarul Islam0000-0003-2466-834X 11 MD Abdullah Al Nasim0000-0001-5594-607X
33 Ryan Mohammad Bin Shahjahan 33

###### Abstract

Incongruity between news headlines and the body content is a common method of
deception used to attract readers. Profitable headlines pique readers’
interest and encourage them to visit a specific website. This is usually done
by adding an element of dishonesty, using enticements that do not precisely
reflect the content being delivered. As a result, automatic detection of
incongruent news between headline and body content using language analysis has
gained the research community’s attention. However, various solutions are
primarily being developed for English to address this problem, leaving low-
resource languages out of the picture. Bangla is ranked 7th among the top 100
most widely spoken languages, which motivates us to pay special attention to
the Bangla language. Furthermore, Bangla has a more complex syntactic
structure and fewer natural language processing resources, so it becomes
challenging to perform NLP tasks like incongruity detection and stance
detection. To tackle this problem, for the Bangla language, we offer a graph-
based hierarchical dual encoder (BGHDE) model that learns the content
similarity and contradiction between Bangla news headlines and content
paragraphs effectively. The experimental results show that the proposed Bangla
graph-based neural network model achieves above 90% accuracy on various Bangla
news datasets.

###### keywords:

Graph neural network, Low Resource Language Bangla news headline incongruity.

##  1 Introduction

News that is misleading or deceptive has become a major social issue. Much of
the information published online is unverifiable, exposing our civilization to
unknown dangers. Every day, the amount of news content produced skyrockets.
However, unlike newspapers, which only print a certain amount of content each
day, making articles online is relatively inexpensive. Additionally, many of
these news stories are generated by automated algorithms[5], lowering the cost
of news production even more. Several news organizations aim to attract
readers’ focus by employing news headlines unrelated to the main content to
draw traffic to news stories among the competition. News headlines are well-
known for forming first impressions on readers and, as a result, determining
the contagious potential of news stories on social media. People in
information-overloaded digital surroundings are less inclined to read or click
on the entire content, preferring to read news headlines. As a result,
deceptive headlines may contribute to inaccurate views of events and obstruct
their distribution. The headline incongruity problem in Bangla news is
addressed in this study, which involves determining if news headlines are
unrelated to or distinct from the main body text. Fig. 1 depicts a scenario in
which readers could expect to learn precise information about picnic places
and picnic spot traders based solely on the headline; however, the news
content comprises a Bangla movie advertisement. Because the body text is only
accessible after a click, many readers will ignore the discrepancy if they
only read the news headlines. Inconsistency in content is becoming more of a
concern, lowering the quality of news reading.

Researchers have suggested a number of realistic techniques to address the
detection problem as a binary classification utilizing deep learning based on
manual annotation (i.e., incongruent or not). A neural network technique is
used to learn the features of news headlines and body text in a new way [6].
These techniques, however, face two significant obstacles.For starters,
current models focus on recognizing the link between a short headline and a
lengthy body text that can be thousands of words long, which makes neural
network-based learning difficult.

Second, the lack of a large-scale dataset makes training a deep learning model
for detecting headline inconsistencies, which involve a variety of factors,
more difficult. The headline incongruity problem is solved using a Bangla
graph-based hierarchical dual encoder (BGHDE) in this study. It captures the
linguistic interaction between a Bangla news headline and any size of body
text. By integrating the headline and body paragraph text content as nodes, it
makes use of the hierarchical architecture of news stories. On one hand, this
method builds a network with nodes for headlines, and on the other hand, it
creates a graph with nodes for body paragraphs. Then, between these nodes, we
link undirected edges.

The BGHDE is trained to calculate edge weights on a large number of headline
and paragraph nodes, with the more relevant edge weight being given. Then, by
aggregating information from surrounding nodes, BGHDE updates each node
representation. The iterative update technique propagates relevant data from
paragraph nodes to the headline node, which is important for spotting content
inconsistencies. In this paper we basically followed the data preparation and
modeling part from the paper [21] and tried to reproduce the work for Bangla.
However, our contribution can be summarized as below:

  1. 1.

We propose a graph-based architecture for the first time to detect incongruity
between Bangla’s new headline and body text.

  2. 2.

We provide an approach for synthetic data generation and made all the code and
pre-processed dataset publicly available111https://github.com/aminul-
palash/bangla-news-incongruity-detection.

  3. 3.

We have analyzed and presented our model performance both on synthetic dataset
and real-world datasets. Apart from news dataset we also tested our model
performance, how it can detect irrelevant comments on manually collected
comments from social networking cites like Facebook and YouTube.

The findings demonstrate that the proposed method can be utilized to detect
inconsistencies in real-world Bangla news reports. As shown in Figure-1, even
for new themes like picnic locations and traders, BGHDE can successfully
detect anomalies in headlines and body content. The remainder of this article
will be discussed in the following manner: Section 2 begins with a summary of
the research on headline incongruity detection and the use of neural graph
networks with text. The data creation procedure is then introduced in section
3. Finally, Section 4 discusses the baseline models that were tested in this
work. The proposed model is then thoroughly discussed. In Section 5, we give
the experimental setup for model evaluation, as well as a discussion of the
results obtained from various kinds of Bangla news and empirical study in the
field. Finally, we consider the study’s implications in terms of combating
online infodemics and news fatigue. Finally, Sections 6 and 7 conclude the
paper with a discussion of the study’s shortcomings as well as future research
opportunities in the field of news incongruence detection.

Figure 1: A graph illustration of an incongruent headline problem between the
headline and the body paragraphs The inconsistency between paragraph 3 and
other texts is represented by a separate color node in the graph.

##  2 Related Works

In the present era of the digital world, people are more likely to skim
through the headlines and perceive information using both direct memory
measures and more indirect reasoning measures[3]. Thus, misleading information
can lead to cause more harm. There have been a lot of machine learning
algorithms used. Despite the lack of a large-scale realistic dataset being the
main issue with this challenge, some studies were able to obtain good results
by utilizing manually annotated small-scale datasets. An attention-based
hierarchical dual encoder model is used to detect incongruity between the
headline and the news body[22]. They have also published a million-scale
dataset and introduced augmentation techniques to enhance the training data.

Both incongruity detection and stance detection are related as they share a
common basis: to identify the relationship between a brief piece of content
and a long piece of content. The goal of the 2019 Fake News Challenge was to
encourage the development of stance detection models. For false news
identification, a multi-layer perceptron model with one hidden layer[14]
propagated lexical and similarity features such as bag-of-words (BOW), term
frequency (TF), and term frequency-inverse document frequency (TF-IDF).
However, the winner of the contest for Fake News Challenge 2019 used the
XGBoost[2] algorithm with extracted hand-crafted features. One of the recent
studies used semantic matching[10] dependent on inter-mutual attention by
generating synthetic headlines that corresponded to the news body content and
original news headline to detect the incongruities. However, for low-resource
languages like Bengali, this kind of work is rare due to a lack of well-
developed datasets. In the paper[6] , they explored neural network models and
pre-trained transformer models to detect fake news for fake news detection in
Bangladesh. They’ve also released an annotated Bangla news dataset that can be
used to create an automated fake news detector.

Graph neural network (GNN) is semi-supervised learning which utilizes graph-
structured data [8]. GNN models can learn hidden layer representations by
encoding local graphs and features of vertices while maintaining the linear
model scales of graph edges. The fundamental advantage of GNN models over
traditional models such as recurrent neural networks (RNN) and convolutional
neural networks (CNN) is that GNN models embed relational information and pass
it on to neighbor nodes during training. As a result, GNN models have
succeeded miraculously in NLP tasks like question-answering [17, 20] ,
relationship extraction [24] and knowledge base completion [16].

Fake news detection using GNN models has become a common practice nowadays.
The paper [23] introduced FAKEDETECTOR, an automatic fake news detector model
based on explicit and hidden text features that constructs a deep diffusive
network model to simultaneously learn the representations of news articles,
producers, and subjects.The Hierarchical Graph Attention Network was also used
by the researchers, which use a hierarchical attention method to identify node
representation learning and then employs a classifier to detect bogus news.
[13].

To the best of our knowledge, our work is the first to detect incongruity
between news headline and body for Bangla. In our work, we proposed a Bangla
graph-based hierarchical dual encoder (BGHDE) model for automatic detection of
Bangla news headline and body.

##  3 Datasets for detecting Headline In-congruence Problem

We propose an approach for detecting incongruity between Bangla news headlines
and content where we specifically tackle three significant challenges for
preparing the dataset. We followed the same approach from this paper [21] for
preparing our dataset for bangla language. The first is the scarcity of
manually annotated training datasets, as well as the high expense of creating
them. The second is the length of news stories, which can often be long and
arbitrary, making them challenging to model for machine learning. The last one
is the paragraph creation from the Bangla news corpus, as our news dataset
doesn’t contain any paragraph separation. In the sections below, we’ll go over
each obstacle in detail.

There are millions of news articles over the internet, and previously, the
ground truth was manually annotated in earlier investigations [19], [1].
However, it is almost impossible to annotate ground truth for each news
manually. Therefore, although some previous studies created manually annotated
datasets, we adopt an automated approach for creating the annotations.

To begin with, we gather news stories from reputable target news sources. Then
we pick a collection of target news articles at random to manipulate, i.e.,
change them to look like incongruent news sources.

For the news pieces chosen for alteration, we replace some paragraphs with
paragraphs obtained from other news sources. This collection of parts is
created individually and is not used for training or testing. We carefully
monitor the alteration process to ensure that no news stories are duplicated.

Figure 2: An illustration of how news items with incongruent headlines are
created. Paragraphs from samples articles mixed with target news articles
randomly. Total five types of data mix-up processes shown (Type I, Type II,
Type III, and Type IV).

The news corpus that we use in this paper comes from a renowned The news
corpus that we employ in this paper comes from the famous Bangla news site
Prothom Alo222https://www.kaggle.com/furcifer/bangla-newspaper-dataset, which
consists of over 400k authentic Bengali news articles.

The figure 2 shows The overall workflow of incongruent level data preparation
[21]. There is one target news article and one sample news article. In our
case, we select sample news articles randomly from the real news corpus. The
sample news content paragraphs are then blended in with the intended news
content. The maximum number of paragraphs that can be switched is determined
by the number of paragraphs in the target news article. We randomly manipulate
paragraph swapping processes that address different difficulty levels on the
target news article.

From Figure 2, there is a total of four types of samples that can be generated
by the generation process. But we don’t pick the first two types (I and II)
for preparing our training datasets so that we can keep consistent same
distribution with the original and generated news content in length. So we
keep types three and four (III and IV) for preparing our synthetic training
datasets.

Table 1: Statistics of our Bangla data

|  | Headline | Content
---|---|---|---
Dataset | Samples | Avg. | Std | Avg. | Std
Train | 228000 | 5.58 | 1.45 | 319.35 | 205.41
Dev | 120000 | 5.58 | 1.43 | 319.01 | 241.06
Test | 120000 | 5.57 | 1.43 | 323.55 | 214.124

As there was no paragraph separation on our collected dataset, we had to
separate paragraphs synthetically based on the number of sentences on the news
content. Thus, we split the news article by paragraph, where each paragraph
contains five, ten, twenty, and so on sentences based on the length of news
content.

Furthermore, we preprocessed the data by removing unnecessary punctuation from
both headline and body content. We also discarded the news data that contains
small body content.

##  4 Methodology

Our goal is to determine if the content of the news article matches the news
headline. First of all we extracted semantic information from the data as the
distributed representation of words and sub-word tags has proven effective for
text classification problems. Therefore, we used pre-trained bangl word
embedding, where an article is represented by the mean and the standard
deviation of the word vector representation. For this experiment we used
Bengali GloVe 300-dimensional word vectors pre-trained
embedding333https://github.com/sagorbrur/GloVe-Bengali, and our coverage rate
was 43.34%.

For detecting news incongruities, we adopt a Graph Neural Network (GNN) based
architecture following [21]. GNN is a type of deep learning method that can be
used for processing data represented as a graph [15] for making node-level,
edge-level, and graph-level analyses.

Our proposed Bangla graph-based hierarchical dual encoder (BGHDE) illustrated
in figure 3 takes the headline and paragraph contents into account to detect
incongruency in an end-to-end manner. Our proposed architecture is followed
from this paper [21] which implement an incongruity detection method for
english dataset.The architecture consists broadly of four steps which we
describe briefly below.

First of all, the BGHDE creates a graph that is undirected representing its
innate structure for each news article, After that, it was utilized to train
the neural network with graph structure. Finally, a hierarchical Gated
Recurrent Unit (GRU)-based bidirectional Recurrent Neural Network(RNN)
framework is utilized to generate a representation with node structure of each
headline text and paragraph text, as well as context-aware paragraph
representation.

A group of nodes called vertex represents the headlines text and each
corresponding paragraph of the Bangla news material. The edge of the graph
represents the link between headlines and its corresponding paragraphs of the
Bangla news.

Figure 3: An overview of our proposed model for Bangla news incongruity
detection.

Secondly, to avoid undesirable flattening of the node representation between
the congruent and incongruent paragraphs during GNN propagation, the next step
is to learn the edge weights of the input graph representation.

We employ the paragraph congruity value as a label to supervise the edge
weights during the cross-entropy loss.

Because of this edge-level monitoring, the BGHDE can assign larger weights to
congruent paragraphs and lower weights to incongruent paragraphs, allowing
congruent paragraphs to communicate more information to the headline node than
incongruent paragraphs alone.

Later, the node characteristics are transmitted into surrounding nodes in the
third phase using the established graph structure and trainable edge weights
from the GNN framework. In an edge-weighted form, BGHDE uses the convolutional
graph network (GCN) aggregation function. [9]

Finally, the incongruity of scores of news pieces is predicted for the last
stage. The GNN graph classification problem is the same as this. The global-
level graph representation and the local-level node representation must be
fused together, BGHDE adapts a fusion block presented in[18]

##  5 Experiments

The title and the appropriate paragraphs of the subsequent body text are
encoded using a single-layer GRU with 200 hidden units. In contrast, a single-
layer bidirectional GRU with 100 hidden units is used to encode the paragraph-
level RNN. There are three GNN layers, each with 200 hidden units. Hidden unit
dimensions of 200, 200, and 100 for the FC layers applied after feature
propagation on the graphs, respectively. We use the Adam optimization
algorithm [7] to train the model, starting with an initial learning rate of
0.001, which is decayed every three epochs by a factor of 10. We use 120
samples for each mini-batch during training. We clip the gradients with a
threshold of 1.0. The hyperparameter for tradeoffs for edge loss is set to
0.1. We use pre-trained Bangla444https://github.com/sagorbrur/GloVe-Bengali
GloVe [12] embedding consisting of 300-dimensional vectors to initialize the
word embeddings.The number of words that appear at least eight times in the
training dataset determines the size of the embedding matrix’s vocabulary. The
model has 1,214,702 total trainable parameters. We obtained an accuracy of
0.9560 and an AUC score of 0.9860 on the validation set. We show the loss and
paragraph and document accuracy obtained during training in Figure 4.

We use PyTorch [11] and PyTorch Geometric [4] frameworks to implement the
model and Google colab to run the experiments.

Figure 4: Left plot represents training and validation loss and the right plot
represents accuracy of the validation data during training.

##  6 Results and Discussion

To validate our process, we conduct rigorous quantitative and qualitative
analyses. We conducted a large-scale experimental analysis to evaluate our
proposed Bangla graph-based hierarchical dual encoder (BGHDE). We performed an
evaluation based on criteria like accuracy on both paragraph-wise and whole
document or news article calculated while all types of a common evaluation
matrix for the predictive model also added.

Figure 5: Examples of some partial representation of news articles that
contains incongruity between headline and content paragraphs, colored
paragraph are the in-congruence paragraph Figure 6: Incongruity detection on
comments data

###  6.1 Performance Evaluation on Synthetic Dataset

Figure 5 illustrates some examples of incongruent data detected by our
proposed model on synthetic test datasets. Our tested dataset contains news
from both Bangladeshi555https://www.kaggle.com/ebiswas/bangla-largest-
newspaper-dataset and West
Bengal666https://www.kaggle.com/csoham/classification-bengali-news-articles-
indicnlp news articles which helps to analyze the model performs better Table
2 shows the model’s performance on different datasets when it was used to
detect headline inconsistencies.

Table 2: Second table

Dataset | Size | Acc(para) | Acc(doc) | Evaluation
---|---|---|---|---
Precision | Recall | F1 Scr | Support
Prothom alo | 6000 | 0.9658 | 0.9918 | 0.98.80 | 0.9956 | 0.9918 | [3000 3000]
bdnews24 | 2000 | 0.9175 | 0.94.50 | 0.7554 | 0.913 | 0.9431 | [1000 1000]
Ananda bazar | 1000 | 0.9175 | 0.9450 | 0.9623 | 0.97 | 0.9431 | [500 500]
ebela | 5000 | 0.9192 | 0.9702 | 0.970 | 0.9704 | 0.9702 | [2500 2500]
zeenews | 5000 | 0.9026 | 0.9542 | 0.9511 | 0.9576 | 0.9543 | [2500 2500]
Ittefaq | 8000 | 0.9445 | 0.9866 | 0.9812 | 0.9922 | 0.9866 | [4000 4000]
Jugantor | 6999 | 0.9494 | 0.9862 | 0.9830 | 0.9893 | 0.9861 | [3458 3477]

###  6.2 Evaluation on Real world Dataset

To see how effective our dataset and proposed models are in detecting
incongruent headlines in the real world. We’ve conducted this process by
collecting data containing actual articles in which any form of the generation
process has not modified the body text. It is difficult to annotate read news
containing incongruity manually, and we perform inference on a real news
dataset without annotations. After that, we evaluated our model performance
manually. But we achieved very poor performance. For example, the datasets we
used have no paragraph separation, and we need to separate the articles into
paragraphs randomly. Another one is that we only train our model on synthetic
datasets.

We also evaluated our proposed model on detecting incongruent comments Figure
6 on different sites like YouTube, Facebook, and various Bangla news sites. As
a result, we collected more than two hundred comments data containing relevant
and irrelevant comments with corresponding news articles. We achieved an
accuracy of 0.73 on the Bangla comments dataset.

##  7 Conclusion and Future Work

For the first time, a graph neural network was used to handle the headline
incongruity problem in Bangla news stories. We discovered a few false-positive
scenarios when a model misinterpreted a coherent article for an incongruent
headline using manual annotations. Although the computer accurately predicted
the label, according to the idea of headline incongruity, such a ”briefing”
item does not mislead readers by delivering false information. Our findings
suggest that more research is needed in the future to improve data generation
and gathering processes. The findings of the evaluation experiments, however,
reveal that the proposed technique accurately detects such deception. We hope
that our research helps to create more trustworthy online news ecosystems in
Bangla.

## References

  * [1] Chakraborty, A., Paranjape, B., Kakarla, S., Ganguly, N.: Stop clickbait: Detecting and preventing clickbaits in online news media. pp. 9–16 (08 2016). 10.1109/ASONAM.2016.7752207
  * [2] Chen, T., Guestrin, C.: Xgboost: A scalable tree boosting system. In: Krishnapuram, B., Shah, M., Smola, A.J., Aggarwal, C.C., Shen, D., Rastogi, R. (eds.) Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Francisco, CA, USA, August 13-17, 2016\. pp. 785–794. ACM (2016). 10.1145/2939672.2939785, https://doi.org/10.1145/2939672.2939785
  * [3] Ecker, U.K.H., Lewandowsky, S., Chang, E.P., Pillai, R.: The effects of subtle misinformation in news headlines. Journal of experimental psychology. Applied 20 4, 323–35 (2014)
  * [4] Fey, M., Lenssen, J.E.: Fast graph representation learning with pytorch geometric. ArXiv abs/1903.02428 (2019)
  * [5] Guzman, A.L., Lewis, S.C.: Artificial intelligence and communication: A human–machine communication research agenda. New Media & Society 22(1), 70–86 (2020). 10.1177/1461444819858691
  * [6] Hossain, M.Z., Rahman, M.A., Islam, M.S., Kar, S.: Banfakenews: A dataset for detecting fake news in bangla. In: Calzolari, N., Béchet, F., Blache, P., Choukri, K., Cieri, C., Declerck, T., Goggi, S., Isahara, H., Maegaard, B., Mariani, J., Mazo, H., Moreno, A., Odijk, J., Piperidis, S. (eds.) Proceedings of The 12th Language Resources and Evaluation Conference, LREC 2020, Marseille, France, May 11-16, 2020. pp. 2862–2871. European Language Resources Association (2020), https://aclanthology.org/2020.lrec-1.349/
  * [7] Kingma, D.P., Ba, J.: Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6980 (2014)
  * [8] Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks. CoRR abs/1609.02907 (2016), http://arxiv.org/abs/1609.02907
  * [9] Kipf, T.N., Welling, M.: Semi-supervised classification with graph convolutional networks (2017)
  * [10] Mishra, R., Yadav, P., Calizzano, R., Leippold, M.: Musem: Detecting incongruent news headlines using mutual attentive semantic matching. In: Wani, M.A., Luo, F., Li, X.A., Dou, D., Bonchi, F. (eds.) 19th IEEE International Conference on Machine Learning and Applications, ICMLA 2020, Miami, FL, USA, December 14-17, 2020. pp. 709–716. IEEE (2020). 10.1109/ICMLA51294.2020.00116, https://doi.org/10.1109/ICMLA51294.2020.00116
  * [11] Paszke, A., Gross, S., Massa, F., Lerer, A., Bradbury, J., Chanan, G., Killeen, T., Lin, Z., Gimelshein, N., Antiga, L., Desmaison, A., Köpf, A., Yang, E., DeVito, Z., Raison, M., Tejani, A., Chilamkurthy, S., Steiner, B., Fang, L., Bai, J., Chintala, S.: Pytorch: An imperative style, high-performance deep learning library. ArXiv abs/1912.01703 (2019)
  * [12] Pennington, J., Socher, R., Manning, C.D.: Glove: Global vectors for word representation. In: Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP). pp. 1532–1543 (2014)
  * [13] Ren, Y., Zhang, J.: Fake news detection on news-oriented heterogeneous information networks through hierarchical graph attention. In: International Joint Conference on Neural Networks, IJCNN 2021, Shenzhen, China, July 18-22, 2021. pp. 1–8. IEEE (2021). 10.1109/IJCNN52387.2021.9534362, https://doi.org/10.1109/IJCNN52387.2021.9534362
  * [14] Riedel, B., Augenstein, I., Spithourakis, G.P., Riedel, S.: A simple but tough-to-beat baseline for the fake news challenge stance detection task. CoRR abs/1707.03264 (2017), http://arxiv.org/abs/1707.03264
  * [15] Scarselli, F., Gori, M., Tsoi, A.C., Hagenbuchner, M., Monfardini, G.: The graph neural network model. IEEE transactions on neural networks 20(1), 61–80 (2008)
  * [16] Schlichtkrull, M.S., Kipf, T.N., Bloem, P., van den Berg, R., Titov, I., Welling, M.: Modeling relational data with graph convolutional networks. In: Gangemi, A., Navigli, R., Vidal, M., Hitzler, P., Troncy, R., Hollink, L., Tordai, A., Alam, M. (eds.) The Semantic Web - 15th International Conference, ESWC 2018, Heraklion, Crete, Greece, June 3-7, 2018, Proceedings. Lecture Notes in Computer Science, vol. 10843, pp. 593–607. Springer (2018). 10.1007/978-3-319-93417-4_38, https://doi.org/10.1007/978-3-319-93417-4_38
  * [17] Song, L., Wang, Z., Yu, M., Zhang, Y., Florian, R., Gildea, D.: Exploring graph-structured passage representation for multi-hop reading comprehension with graph neural networks. CoRR abs/1809.02040 (2018), http://arxiv.org/abs/1809.02040
  * [18] Wang, Y., Sun, Y., Liu, Z., Sarma, S.E., Bronstein, M.M., Solomon, J.M.: Dynamic graph cnn for learning on point clouds (2019)
  * [19] Wei, W., Wan, X.: Learning to identify ambiguous and misleading news headlines. pp. 4172–4178 (08 2017). 10.24963/ijcai.2017/583
  * [20] Xiao, Y., Qu, Y., Qiu, L., Zhou, H., Li, L., Zhang, W., Yu, Y.: Dynamically fused graph network for multi-hop reasoning. CoRR abs/1905.06933 (2019), http://arxiv.org/abs/1905.06933
  * [21] Yoon, S., Park, K., Lee, M., Kim, T., Cha, M., Jung, K.: Learning to detect incongruence in news headline and body text via a graph neural network. IEEE Access 9, 36195–36206 (2021). 10.1109/ACCESS.2021.3062029
  * [22] Yoon, S., Park, K., Shin, J., Lim, H., Won, S., Cha, M., Jung, K.: Detecting incongruity between news headline and body text via a deep hierarchical encoder. CoRR abs/1811.07066 (2018), http://arxiv.org/abs/1811.07066
  * [23] Zhang, J., Dong, B., Yu, P.S.: Fakedetector: Effective fake news detection with deep diffusive neural network. In: 36th IEEE International Conference on Data Engineering, ICDE 2020, Dallas, TX, USA, April 20-24, 2020. pp. 1826–1829. IEEE (2020). 10.1109/ICDE48307.2020.00180, https://doi.org/10.1109/ICDE48307.2020.00180
  * [24] Zhang, Y., Qi, P., Manning, C.D.: Graph convolution over pruned dependency trees improves relation extraction. In: Riloff, E., Chiang, D., Hockenmaier, J., Tsujii, J. (eds.) Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 - November 4, 2018\. pp. 2205–2215. Association for Computational Linguistics (2018). 10.18653/v1/d18-1244, https://doi.org/10.18653/v1/d18-1244


$\displaystyle=\alpha\log\sum_{a\in\mathcal{A}}\exp(Q^{\max}(s_{t},a)/\alpha),$
(87) $\displaystyle Q^{\max}(s_{t},a_{t})$
$\displaystyle=R(s_{t},a_{t})+\max_{s_{t+1}\in\textnormal{Succ}(s_{t},a_{t})}V^{\max}(s_{t+1}).$
(88)

Via induction, it is possible to show that
$Q^{\min}(s_{t},a_{t})\leq\hat{Q}^{N(s_{t},a_{t})}_{\textnormal{sft}}(s_{t},a_{t})$
and $V^{\max}(s_{t})\geq\hat{V}^{N(s_{t})}_{\textnormal{sft}}(s_{t})$. Now,
define $\pi^{\min}$ as:

$\displaystyle\pi^{\min}=\inf_{\lambda\in[0,1]}\min_{(s,a)\in\mathcal{S}\times\mathcal{A}}(1-\lambda)\exp\left(\left(Q^{\min}(s,a)-V^{\max}(s)\right)/\alpha\right)+\frac{\lambda}{|\mathcal{A}|}.$
(89)

Because the value of an exponential is positive, as is $1/|\mathcal{A}|$, it
follows that $\pi^{\min}>0.$ Recall the MENTS policy (Equation (73)). By the
monotonicity of the exponential function, it follows that for any
$s_{t}\in\mathcal{S},a_{t}\in\mathcal{A},n\in\mathbb{N}$:

$\displaystyle\pi^{n}(a_{t}|s_{t})=$
$\displaystyle(1-\lambda_{s_{t}})\exp\left(\left(\hat{Q}^{N(s_{t},a_{t})}_{\textnormal{sft}}(s_{t},a_{t})-\hat{V}^{N(s_{t})}_{\textnormal{sft}}(s_{t})\right)/\alpha\right)+\frac{\lambda_{s_{t}}}{|\mathcal{A}|}$
(90) $\displaystyle\geq$
$\displaystyle(1-\lambda_{s_{t}})\exp\left(\left(Q^{\min}(s_{t},a_{t})-V^{\max}(s_{t})\right)/\alpha\right)+\frac{\lambda_{s_{t}}}{|\mathcal{A}|}$
(91) $\displaystyle\geq$ $\displaystyle\pi^{\min}.$ (92)

Now we consider the DENTS process.

For the DENTS process we can use similar reasoning, but need to update the
definition of $V^{\max}$ from Equation (87) to:

$\displaystyle V^{\max}(s_{t})$
$\displaystyle=\alpha\log\sum_{a\in\mathcal{A}}\exp\left(\left(Q^{\max}(s_{t},a)+H\beta_{\max}\log|\mathcal{A}|\right)/\alpha\right),$
(93)

where $\beta_{\max}=\sup_{x\in\mathbb{R}}\beta(x)$. Similarly to the MENTS
process case, we can show that
$Q^{\min}(s_{t},a_{t})\leq\hat{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})$ and
$V^{\max}(s_{t})\geq V_{\rho}^{N(s_{t})}$, which implicitly uses that
$0\leq\mathcal{H}_{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})\leq(H-t)\log|\mathcal{A}|\leq
H\log|\mathcal{A}|$, which can be shown with an inductive argument, and using
well-known properties of entropy. Defining $\pi^{\min}$ in the same way as
Equation (89), with the updated definition of $V^{\max}$. Recalling the DENTS
policy (Equation (85)), and using similar reasoning to before, we have:

$\displaystyle\pi^{n}(a_{t}|s_{t})=$
$\displaystyle(1-\lambda_{s})\exp\left(\frac{1}{\alpha}\left(\hat{Q}^{N(s,a)}(s,a)+\beta(N(s))\mathcal{H}_{Q}^{N(s,a)}(s,a)-V_{\rho}^{N(s)}(s)\right)\right)+\frac{\lambda_{s}}{|\mathcal{A}|}$
(94) $\displaystyle\geq$
$\displaystyle(1-\lambda_{s})\exp\left(\frac{1}{\alpha}\left(\hat{Q}^{N(s,a)}(s,a)-V_{\rho}^{N(s)}(s)\right)\right)+\frac{\lambda_{s}}{|\mathcal{A}|}$
(95) $\displaystyle\geq$
$\displaystyle(1-\lambda_{s_{t}})\exp\left(\left(Q^{\min}(s_{t},a_{t})-V^{\max}(s_{t})\right)/\alpha\right)+\frac{\lambda_{s_{t}}}{|\mathcal{A}|}$
(96) $\displaystyle\geq$ $\displaystyle\pi^{\min}.$ (97)

∎

It will also be useful in the following that the union of exponentially
unlikely events is also exponentially unlikely, and that the intersection of
exponentially likely events is exponentially likely:

######  Lemma E.2.

Let $A_{1},...,A_{\ell}$ be some events that satisfy for $1\leq i\leq\ell$ the
inequality $\Pr(\lnot A_{i})\leq C_{i}\exp(-k_{i})$ then:

$\displaystyle\Pr\left(\bigcup_{i=1}^{\ell}\lnot A_{i}\right)$
$\displaystyle\leq C\exp(-k),$ (98)
$\displaystyle\Pr\left(\bigcap_{i=1}^{\ell}A_{i}\right)=1-\Pr\left(\bigcup_{i=1}^{\ell}\lnot
A_{i}\right)$ $\displaystyle\geq 1-C\exp(-k),$ (99)

where $C=\sum_{i=1}^{\ell}C_{i}$ and $k=\min_{i}k_{i}$.

###### Proof outline.

Lemma E.2 is a consequence of the union bound, rearranging and simplifying.
Inequality (99) is a consequence from Inequality (98) by negating the events.
∎

Additionally, Hoeffding’s inequality will be useful to bound the difference
between a sum of indicator random variables and its expectation.

######  Theorem E.3.

Let $\\{X_{i}\\}_{i=1}^{m}$ be indicator random variables (i.e.
$X_{i}\in\\{0,1\\}$), and $S_{m}=\sum_{i=1}^{m}X_{i}$. Then Hoeffding’s
inequality for indicator random variables states for any $\varepsilon>0$ that:

$\displaystyle\Pr(|S_{m}-\mathbb{E}S_{m}|>\varepsilon)\leq
2\exp\left(-\frac{2\varepsilon^{2}}{m}\right).$ (100)

###### Proof.

This is a specific case of Hoeffding’s inequality. See
hoeffding1994probability for proof. ∎

It will also be convenient to be able to ‘translate’ bounds that depend on
some $N(s,a)$ to a corresponding bound on $N(s)$:

######  Lemma E.4.

Consider any Boltzmann MCTS process. Suppose that every action $a_{t}$ has
some minimum probability $\eta$ of being chosen from some state $s_{t}$
(irrespective of the number of trials), i.e.
$\Pr(a^{i}_{t}=a_{t}|s^{i}_{t}=s_{t})>\eta$. And suppose for some
$C^{\prime},k^{\prime}>0$ that some event $E$ admits a bound:

$\displaystyle\Pr(E)\leq C^{\prime}\exp(-k^{\prime}N(s_{t},a_{t})).$ (101)

Then, there exists $C,k>0$ such that:

$\displaystyle\Pr(E)\leq C\exp(-kN(s_{t})).$ (102)

###### Proof.

Recall from Equation (67) that $N(s_{t},a_{t})=\sum_{i\in
T(s_{t})}\mathbbm{1}[a^{i}_{t}=a_{t}]=\sum_{i\in
T(s_{t})}\mathbbm{1}[a^{i}_{t}=a_{t}|s^{i}_{t}=s_{t}]$. By taking expectations
and using the assumed $\Pr(a^{i}_{t}=a_{t}|s^{i}_{t}=s_{t})\geq\eta$ we have
$\mathbb{E}N(s_{t},a_{t})\geq\eta N(s_{t})$ (and more specifically as a
consequence $\mathbb{E}N(s_{t},a_{t})-\eta N(s_{t})/2\geq\eta N(s_{t})/2$).
The probability of $N(s_{t},a_{t})$ being below a multiplicative ratio of
$N(s_{t})$ is bounded as follows:

$\displaystyle\Pr\left(N(s_{t},a_{t})<\frac{1}{2}\eta N(s_{t})\right)$
$\displaystyle\leq\Pr\left(N(s_{t},a_{t})<\mathbb{E}N(s_{t},a_{T})-\frac{1}{2}\eta
N(s_{t})\right)$ (103)
$\displaystyle=\Pr\left(\mathbb{E}N(s_{t},a_{t})-N(s_{t},a_{t})>\frac{1}{2}\eta
N(s_{t})\right)$ (104)
$\displaystyle\leq\Pr\left(|\mathbb{E}N(s_{t},a_{t})-N(s_{t},a_{t})|>\frac{1}{2}\eta
N(s)\right)$ (105) $\displaystyle\leq
2\exp\left(-\frac{1}{2}\eta^{2}N(s_{t})\right).$ (106)

The first line follows from $\mathbb{E}N(s_{t},a_{t})-\eta N(s_{t})/2\geq\eta
N(s_{t})/2$, the second line is a rearrangement, the third line comes from the
inequality in (104) implying the inequality in (105), and the final line uses
Theorem E.3, a Hoeffding bound for the sum of indicator random variables.

Finally, the bound using $N(s_{t},a_{t})$ can be converted into one depending
on $N(s_{t})$ as follows:

$\displaystyle\Pr\left(E\right)=$
$\displaystyle\Pr\left(E\bigg{|}N(s_{t},a_{t})\geq\frac{1}{2}\eta
N(s_{t})\right)\Pr\left(N(s_{t},a_{t})\geq\frac{1}{2}\eta N(s_{t})\right)$
(107) $\displaystyle+\Pr\left(E\bigg{|}N(s_{t},a_{t})<\frac{1}{2}\eta
N(s_{t})\right)\Pr\left(N(s_{t},a_{t})<\frac{1}{2}\eta N(s_{t})\right)$ (108)
$\displaystyle\leq$
$\displaystyle\Pr\left(E\bigg{|}N(s_{t},a_{t})\geq\frac{1}{2}\eta
N(s_{t})\right)\cdot 1$ (109)
$\displaystyle+1\cdot\Pr\left(N(s_{t},a_{t})<\frac{1}{2}\eta N(s_{t})\right)$
(110) $\displaystyle\leq$ $\displaystyle
C^{\prime}\exp\left(-\frac{1}{2}k^{\prime}\eta
N(s_{t})\right)+2\exp\left(-\frac{1}{2}\eta^{2}N(s_{t})\right)$ (111)
$\displaystyle\leq$ $\displaystyle C\exp(-kN(s_{t})),$ (112)

where (111) uses the assumed Inequality (101) with the condition
$N(s_{t},a_{t})\geq\eta N(s_{t})/2$, and also uses the bound from (106). On
the last line there is an appropriate $C,k>0$, similar to Lemma E.2. ∎

Similar to Lemma E.4, if we have some $s^{\prime}\in\textnormal{Succ}(s,a)$,
it will also be convenient to be able to translate bounds that depend on
$N(s^{\prime})$ into bounds that depend on $N(s,a)$:

######  Lemma E.5.

Consider any Boltzmann MCTS process. For some state action pair
$(s_{t},a_{t})$, and for some
$s^{\prime}_{t+1}\in\textnormal{Succ}(s_{t},a_{t})$, suppose for some
$C^{\prime},k^{\prime}>0$ that some event $E$ admits a bound:

$\displaystyle\Pr(E)\leq C^{\prime}\exp(-k^{\prime}N(s^{\prime}_{t})).$ (113)

Then, there exists $C,k>0$ such that:

$\displaystyle\Pr(E)\leq C\exp(-kN(s_{t},a_{t})).$ (114)

###### Proof outline.

Proof is similar to Lemma E.4. Instead of having a minimum probability of
selecting an action $\eta$, replace it with the corresponding probability from
the transition distribution $p(s_{t+1}|s_{t},a_{t})$. Then swapping any
$N(s_{t})$ with $N(s_{t},a_{t})$, any $N(s_{t},a_{t})$ with
$N(s^{\prime}_{t})$, and using $N(s_{t+1})=\sum_{i\in
T(s_{t},a_{t})}\mathbbm{1}[s^{i}_{t+1}=s_{t+1}]$ (Equation (68)) as the sum of
indicator random variables will give the result. ∎

###  E.3 Soft learning

For this subsection we will temporarily reintroduce the time-step parameter
into our value functions to simplify other notation. We will show two results
about soft Q-values: that the optimal standard Q-value is less than the
optimal soft Q-value, and, that given a sufficiently small temperature, the
optimal soft Q-values will preserve any strict ordering over actions given by
the optimal standard Q-values.

For some policy $\pi$, the definition of $V^{\pi}_{\text{sft}}$ (Equation (3))
can be re-arranged, to give a relation between the soft Q-value, the standard
Q-value and the entropy of the policy:

$\displaystyle Q^{\pi}_{\text{sft}}(s,a,t)$
$\displaystyle=Q^{\pi}(s,a,t)+\alpha\mathbb{E}_{\pi}\left[\sum_{i=t+1}^{H}\mathcal{H}\left(\pi(\cdot|s_{i})\right)\Bigg{|}s_{t}=s,a_{t}=a\right],$
(115)
$\displaystyle=Q^{\pi}(s,a,t)+\alpha\mathcal{H}_{t+1}(\pi|s_{t}=s,a_{t}=a),$
(116)

where $\mathcal{H}_{t+1}$ is used as a shorthand for the entropy term. By
using this relation, it can be shown that the optimal soft Q-value will always
be at least as large as the optimal standard Q-value:

######  Lemma E.6.

$Q^{*}(s,a,t)\leq Q_{\textnormal{sft}}^{*}(s,a,t).$

###### Proof.

Taking a maximum over policies in Equation (115), and considering that
$\pi^{*}$, the optimal standard policy, is one of the possible policies
considered in the maximisation, gives the result:

$\displaystyle Q_{\text{sft}}^{*}(s,a,t)$
$\displaystyle=\max_{\pi}\left(Q^{\pi}(s,a,t)+\alpha\mathcal{H}_{t+1}(\pi|s_{t}=s,a_{t}=a)\right)$
(117) $\displaystyle\geq
Q^{\pi^{*}}(s,a,t)+\alpha\mathcal{H}_{t+1}(\pi^{*}|s_{t}=s,a_{t}=a)$ (118)
$\displaystyle\geq Q^{*}(s,a,t).$ (119)

Noting that the entropy function is non-negative function. ∎

The optimal soft and standard values can be ‘tied together’ by picking a very
low temperature. Let $\delta(s,t)$ be the set of actions that have different
optimal standard Q-values, that is
$\delta(s,t)=\\{(a,a^{\prime})|Q^{*}(s,a,t)\neq Q^{*}(s,a^{\prime},t)\\}$. Now
define $\Delta_{\mathcal{M}}$ as follows:

$\displaystyle\Delta_{s,t}$
$\displaystyle=\min_{(a,a^{\prime})\in\delta(s,t)}|Q^{*}(s,a,t)-Q^{*}(s,a^{\prime},t)|,$
(120) $\displaystyle\Delta_{\mathcal{M}}$
$\displaystyle=\min_{s,t}\Delta_{s,t}.$ (121)

Note in particular, for some $(a,a^{\prime})\in\delta(s,t)$ that the
definition of $\Delta_{\mathcal{M}}$ implies that if
$Q^{*}(s,a,t)<Q^{*}(s,a^{\prime},t)$ then

$\displaystyle Q^{*}(s,a,t)+\Delta_{\mathcal{M}}\leq Q^{*}(s,a^{\prime},t).$
(122)

######  Lemma E.7.

If $\alpha<\Delta_{\mathcal{M}}/H\log|\mathcal{A}|$, then for all $t=1,...,H$,
for all $s\in\mathcal{S}$ and for all $(a,a^{\prime})\in\delta(s,t)$ we have
$Q_{\textnormal{sft}}^{*}(s,a,t)<Q_{\textnormal{sft}}^{*}(s,a^{\prime},t)$ iff
$Q^{*}(s,a,t)<Q^{*}(s,a^{\prime},t)$.

###### Proof.

$(\Leftarrow)$ First consider that the optimal soft Q-value is less than or
equal to the optimal standard Q-value and maximum possible entropy:

$\displaystyle Q_{\textnormal{sft}}^{*}(s,a,t)$
$\displaystyle=\max_{\pi}\left(Q^{\pi}(s,a,t)+\alpha\mathcal{H}_{t+1}(\pi)\right)$
(123)
$\displaystyle\leq\max_{\pi}Q^{\pi}(s,a,t)+\max_{\pi}\alpha\mathcal{H}_{t+1}(\pi)$
(124) $\displaystyle=Q^{*}(s,a,t)+\alpha(H-t)\log|\mathcal{A}|$ (125)
$\displaystyle\leq Q^{*}(s,a,t)+\alpha H\log|\mathcal{A}|.$ (126)

By using the assumed $\alpha<\Delta_{\mathcal{M}}/H\log|\mathcal{A}|$, using
$Q^{*}(s,a,t)+\Delta_{\mathcal{M}}\leq Q^{*}(s,a^{\prime},t)$ and that
$Q^{*}(s,a^{\prime},t)\leq Q^{*}_{\textnormal{sft}}(s,a^{\prime},t)$ from
Lemma E.6 we get:

$\displaystyle Q_{\text{sft}}^{*}(s,a,t)$ $\displaystyle\leq
Q^{*}(s,a,t)+\alpha H\log|\mathcal{A}|$ (127)
$\displaystyle<Q^{*}(s,a,t)+\Delta_{\mathcal{M}}$ (128) $\displaystyle\leq
Q^{*}(s,a^{\prime},t)$ (129) $\displaystyle\leq
Q_{\text{sft}}^{*}(s,a^{\prime},t).$ (130)

($\Rightarrow$) To show that given the assumptions that
$Q_{\text{sft}}^{*}(s,a,t)<Q_{\text{sft}}^{*}(s,a^{\prime},t)\Rightarrow
Q^{*}(s,a,t)<Q^{*}(s,a^{\prime},t)$ we will show the contrapostive instead,
which is $Q^{*}(s,a,t)\geq Q^{*}(s,a^{\prime},t)\Rightarrow
Q_{\text{sft}}^{*}(s,a,t)\geq Q_{\text{sft}}^{*}(s,a^{\prime},t)$. Given that
it is assumed that $(a,a^{\prime})\in\delta(s,t)$, the following implications
hold:

$\displaystyle Q^{*}(s,a,t)$ $\displaystyle\geq Q^{*}(s,a^{\prime},t)$ (131)
$\displaystyle\Rightarrow Q^{*}(s,a,t)$ $\displaystyle>Q^{*}(s,a^{\prime},t)$
(132) $\displaystyle\Rightarrow Q_{\text{sft}}^{*}(s,a,t)$
$\displaystyle>Q_{\text{sft}}^{*}(s,a^{\prime},t)$ (133)
$\displaystyle\Rightarrow Q_{\text{sft}}^{*}(s,a,t)$ $\displaystyle\geq
Q_{\text{sft}}^{*}(s,a^{\prime},t),$ (134)

where the first implication uses that $(a,a^{\prime})\in\delta(s)$, the second
reuses the ($\Leftarrow$) proof, and the final implication holds generally. ∎

###  E.4 Simple regret

In this section we will revisit simple regret in more detail. Recall that our
definition of simple regret is:

$\displaystyle\textnormal{reg}(s_{t},\psi^{n})$
$\displaystyle=V^{*}(s_{t})-V^{\psi^{n}}(s_{t}),$ (135)

where $\psi^{n}$ is the policy recommended by a forecaster after $n$ rounds or
trials. This definition is different to what has been considered by the tree
search literature so far mcts_simple_regret,brue1. However, we feel that this
definition is a more natural extension to the simple regret considered for
multi-armed bandit problems simple_regret_short,simple_regret_long, as it
stems from a more general MDP planning problem that does not necessarily have
to be solved using a tree search (for example, consider if we want to reason
about a non-tree search algorithm’s simple regret, that only outputs full
policies). Moreover, we can reconcile the difference by defining the simple
regret of an action (or immediate simple regret) as:

$\displaystyle\textnormal{reg}_{I}(s_{t},\psi^{n})=$ $\displaystyle
V^{*}(s)-\mathbb{E}_{a_{t}\sim\psi^{n}(s_{t})}[Q^{*}(s_{t},a_{t})],$ (136)

and we show that any asymptotic upper bounds provided on the two definitions
are equivalent up to a multiplicative factor.

######  Lemma E.8.

$\mathbb{E}\textnormal{reg}(s_{t},\psi^{n})=O(f(n))$ for all
$s_{t}\in\mathcal{S}$ iff
$\mathbb{E}\textnormal{reg}_{I}(s_{t},\psi^{n})=O(f(n))$ for all
$s_{t}\in\mathcal{S}$.

###### Proof.

Firstly, notice that the simple regret can be written recursively in terms of
the immediate simple regret:

$\displaystyle\textnormal{reg}(s_{t},\psi^{n})=$ $\displaystyle
V^{*}(s_{t})-V^{\psi^{n}}(s_{t})$ (137) $\displaystyle=$ $\displaystyle
V^{*}(s_{t})-\mathbb{E}_{a_{t}\sim\psi^{n}(s)}[Q^{\psi^{n}}(s_{t},a_{t})]$
(138) $\displaystyle=$ $\displaystyle
V^{*}(s_{t})-\mathbb{E}_{a_{t}\sim\psi^{n}(s)}[R(s_{t},a_{t})+\mathbb{E}_{s_{t+1}\sim\Pr(\cdot|s_{t},a_{t})}[V^{\psi^{n}}(s_{t+1})]]$
(139) $\displaystyle=$ $\displaystyle
V^{*}(s_{t})-\mathbb{E}_{a_{t}\sim\psi^{n}(s)}\big{[}Q^{*}(s,a)-\mathbb{E}_{s_{t+1}\sim\Pr(\cdot|s_{t},a_{t})}[V^{*}(s_{t+1})]$
$\displaystyle+\mathbb{E}_{s_{t+1}\sim\Pr(\cdot|s_{t},a_{t})}[V^{\psi^{n}}(s_{t+1})]\big{]}$
(140) $\displaystyle=$ $\displaystyle
V^{*}(s_{t})-\mathbb{E}_{a_{t}\sim\psi^{n}(s_{t})}[Q^{*}(s_{t},a_{t})]$
$\displaystyle+\mathbb{E}_{a_{t}\sim\psi_{n}(s_{t}),s_{t+1}\sim\Pr(\cdot|s_{t},a_{t})}[V^{*}(s_{t+1})-V^{\psi^{n}}(s_{t+1})]$
(141) $\displaystyle=$
$\displaystyle\textnormal{reg}_{I}(s,\psi^{n})+\mathbb{E}_{a_{t}\sim\psi^{n}(s_{t}),s^{\prime}\sim\Pr(\cdot|s_{t},a_{t})}[\textnormal{reg}(s_{t+1},\psi^{n})],$
(142)

where in line (140) we used
$R(s,a)=Q^{*}(s,a)-\mathbb{E}_{s^{\prime}\sim\Pr(\cdot|s,a)}[V^{*}(s^{\prime})]$,
a rearrangement of the Bellman optimality equation for $Q^{*}(s,a)$.

This shows that if $\mathbb{E}\textnormal{reg}(s_{t},\psi^{n})=O(f(n))$ then
$\mathbb{E}\textnormal{reg}_{I}(s_{t},\psi^{n})\leq\mathbb{E}\textnormal{reg}(s_{t},\psi^{n})=O(f(n))$.
Now suppose that $\mathbb{E}\textnormal{reg}_{I}(s_{t},\psi^{n})=O(f(n))$ and
assume an inductive hypothesis that
$\mathbb{E}\textnormal{reg}(s_{t+1},\psi^{n})=O(f(n))$ for all
$s_{t+1}\in\cup_{a\in\mathcal{A}}\textnormal{Succ}(s_{t},a)$, then:

$\displaystyle\mathbb{E}\textnormal{reg}(s_{t},\psi^{n})=\mathbb{E}\left[O(f(n))+\mathbb{E}_{a_{t}\sim\psi^{n}(s_{t}),s_{t+1}\sim\Pr(\cdot|s_{t},a_{t})}[O(f(n))]\right]=O(f(n)),$
(143)

where the outer expectation is with respect $\psi^{n}$ (as the relevant MENTS
process is a stochastic one). ∎

It is useful to specialise Lemma E.8 specifically for the form of bounds used
later. I.e. the simple regret at $s_{t}$ admits a regret bound exponential in
$N(s_{t})$, if and only if, the immediate simple regret admits a bound
exponential in $N(s_{t})$.

######  Corollary E.8.1.

Consider any Boltzmann MCTS process. There exists $C_{1},k_{1}>0$ such that
$\mathbb{E}\textnormal{reg}(s_{t},\psi^{n})\leq C_{1}\exp(-k_{1}N(s_{t}))$ iff
there exists $C_{2},k_{2}>0$ such that
$\mathbb{E}\textnormal{reg}_{I}(s_{t},\psi^{n})\leq
C_{2}\exp(-k_{2}N(s_{t}))$.

###### Proof outline.

The proof follows similarly to Lemma E.8. The additional nuance is that we
need to apply Lemmas E.4 and E.5. Note that the assumption of a minimum action
probability in Lemma E.4 is satisfied, because there is a minimum positive
probability of selecting an action in any Boltzmann MCTS process (Lemma E.1).
The inductive hypothesis for
$s_{t+1}\in\cup_{a\in\mathcal{A}}\textnormal{Succ}(s_{t},a)$ would give a
bound with respect to $N(s_{t+1})$, and the lemmas are required to ‘translate’
the bound into one with respect to $N(s_{t})$. ∎

###  E.5 General Q-value convergence result

Recall the (soft) Q-value backups used by Boltzmann MCTS processes (Equations
(75) and (78)). Considering that the backups for MENTS and DENTS processes are
of similar form, we will show that generally, backups of that form converge
(exponentially), given that the values at any child nodes also converge
(exponentially). However, towards showing this, we first need to consider the
concentration of the empirical transition distribution around the true
transition distribution.

######  Theorem E.9.

Let $\\{X_{i}\\}_{i=1}^{m}$ be random variables drawn from a probability
distribution with a cumulative distribution function of $F$. Let the empirical
cumulative distribution function be
$F_{m}(x)=\frac{1}{m}\sum_{i=1}^{m}\mathbbm{1}[X_{i}<x]$. Then the Dvoretzky-
Kiefer-Wolfowitz inequality is:

$\displaystyle\Pr\left(\sup_{x}|F_{m}(x)-F(x)|>\varepsilon\right)\leq
2\exp\left(-2m\varepsilon^{2}\right).$ (144)

###### Proof.

See dvoretzky1956asymptotic. ∎

The Dvoretzky-Kiefer-Wolfowitz inequality is of interest because it allows us
to tightly bound the empirical transition probability
$N(s_{t+1})/N(s_{t},a_{t})$ with the true transition probability
$p(s_{t+1}|s_{t},a_{t})$.

######  Corollary E.9.1.

Consider any Boltzmann MCTS process. For all
$(s_{t},a_{t})\in\mathcal{S}\times\mathcal{A}$ and for all $\varepsilon>0$ we
have:

$\displaystyle\Pr\left(\max_{s_{t+1}\in\textnormal{Succ}(s_{t},a_{t})}\left|\frac{N(s_{t+1})}{N(s_{t},a_{t})}-p(s_{t+1}|s_{t},a_{t})\right|>\varepsilon\right)\leq
2\exp\left(-\frac{1}{2}\varepsilon^{2}N(s_{t},a_{t})\right).$ (145)

###### Proof outline.

Recall Equation (68) that allows $N(s_{t+1})$ to be written as a sum of
$N(s_{t},a_{t})$ indicator random variables: $N(s_{t+1})=\sum_{i\in
T(s_{t},a_{t})}\mathbbm{1}[s^{i}_{t+1}=s_{t+1}]$. Consider mapping the
empirical transition distribution, with $N(s_{t},a_{t})=|T(s_{t},a_{t})|$
samples, to an appropriate catagorical distribution. Applying Theorem E.9 with
$\varepsilon/2$ gives the result. In the constructed cumulative distribution
function we need to account for an error of $\varepsilon/2$ before any
$s_{t+1}$, and another error of $\varepsilon/2$ after the same $s_{t+1}$, to
account for an error of $\varepsilon$ in the probability mass function (see
Figure 31). ∎

Figure 31: Example cdfs for the transition distribution (black solid line) and
empirical transition distribution (red dashed line) around the successor state
$s_{t+1}$. An error of $\varepsilon/2$ between the empirical and true cdfs is
shown, and the probability mass for $s_{t+1}$ for the empirical and true
transition distributions are shown to indicate how the constructed
distribution gives Corollary E.9.1.

Now that Corollary E.9.1 can be used to bound the empirical transition
distribution to the true transition distribution, we can provide a general
purpose concentration inequality for Q-values to use in later proofs.

######  Lemma E.10.

Consider any Boltzmann MCTS process, and some state action pair
$(s_{t},a_{t})\in\mathcal{S}\times\mathcal{A}$. Let
$\dot{V}^{N(s)}(s):\mathcal{S}\rightarrow\mathbb{R}$,
$\dot{V}^{*}(s):\mathcal{S}\rightarrow\mathbb{R}$ be some estimated and
optimal value functions respectively and suppose that for all
$s_{t+1}\in\textnormal{Succ}(s_{t},a_{t})$ that:

$\displaystyle\Pr\left(\left|\dot{V}^{N(s_{t+1})}(s_{t+1})-\dot{V}^{*}(s_{t+1})\right|>\varepsilon_{1}\right)\leq
C_{s_{t+1}}\exp(-k_{s_{t+1}}\varepsilon_{1}^{2}N(s^{\prime})).$ (146)

If we have optimal and estimated Q-values defined as follows:

$\displaystyle\dot{Q}^{*}(s,a)$
$\displaystyle=R(s,a)+\mathbb{E}_{s^{\prime}\sim
p(\cdot|s,a)}\left[\dot{V}^{*}(s^{\prime})\right],$ (147)
$\displaystyle\dot{Q}^{N(s,a)}(s,a)$
$\displaystyle=R(s,a)+\sum_{s^{\prime}\in\textnormal{Succ}(s,a)}\left[\frac{N(s^{\prime})}{N(s,a)}\dot{V}^{N(s^{\prime})}(s^{\prime})\right].$
(148)

Then for some $C,k>0$, and for all $\varepsilon>0$:

$\displaystyle\Pr\left(\left|\dot{Q}^{N(s,a)}(s,a)-\dot{Q}^{*}(s,a)\right|>\varepsilon\right)\leq
C\exp(-k\varepsilon^{2}N(s,a)).$ (149)

###### Proof.

By the assumed bounds, Lemma E.2 and Lemma E.5, there is some $C_{1},k_{1}>0$,
such that for any $\varepsilon_{1}>0$:

$\displaystyle\Pr\left(\forall
s_{t+1}.\left|\dot{V}^{N(s_{t+1})}(s_{t+1})-\dot{V}^{*}(s_{t+1})\right|\leq\varepsilon_{1}\right)>1-C_{1}\exp(-k_{1}\varepsilon_{1}^{2}N(s_{t},a_{t})),$
(150)

and recall using Corollary E.9.1 that for any
$p(s_{t+1}|s_{t},a_{t})>\varepsilon_{2}>0$ we must have:

$\displaystyle\Pr\left(\max_{s_{t+1}\in\textnormal{Succ}(s_{t},a_{t})}\left|\frac{N(s_{t+1})}{N(s_{t},a_{t})}-p(s_{t},a_{t},s_{t+1})\right|\leq\varepsilon_{2}\right)>1-2\exp\left(-\frac{1}{2}\varepsilon_{2}^{2}N(s_{t},a_{t})\right).$
(151)

If the events in Inequalities (150) and (151) hold, then
$\dot{V}^{*}(s_{t+1})-\varepsilon_{1}\leq\dot{V}^{N_{n}(s_{t+1})}(s_{t+1})\leq\dot{V}^{*}(s_{t+1})+\varepsilon_{1}$
and $p(s_{t+1}|s_{t},a_{t})-\varepsilon_{2}\leq N(s_{t+1})/N(s_{t},a_{t})\leq
p(s_{t+1}|s_{t},a_{t})+\varepsilon_{2}$. The upper bounds on
$\dot{V}^{N_{n}(s_{t+1})}(s_{t+1})$ and $N(s_{t+1})/N(s_{t},a_{t})$ can be
used to obtain an upper bound on $\dot{Q}^{N(s_{t},a_{t})}$:

$\displaystyle\dot{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})$ (152) $\displaystyle=$
$\displaystyle
R(s_{t},a_{t})+\sum_{s_{t+1}\in\textnormal{Succ}(s_{t},a_{t})}\frac{N_{n}(s_{t+1})}{N_{n}(s_{t},a_{t})}\dot{V}^{N_{n}(s_{t+1})}(s_{t+1})$
(153) $\displaystyle\leq$ $\displaystyle
R(s_{t},a_{t})+\sum_{s_{t+1}\in\textnormal{Succ}(s_{t},a_{t})}(p(s_{t+1}|s_{t},a_{t})+\varepsilon_{2})(\dot{V}^{*}(s^{\prime})+\varepsilon_{1})$
(154) $\displaystyle=$ $\displaystyle R(s_{t},a_{t})+\mathbb{E}_{s_{t+1}\sim
p(\cdot|s_{t},a_{t})}[\dot{V}^{*}(s_{t+1})]+\varepsilon_{1}+\varepsilon_{2}\sum_{s_{t+1}\in\textnormal{Succ}(s_{t},a_{t})}\dot{V}^{*}(s_{t+1})+\varepsilon_{1}\varepsilon_{2}$
(155) $\displaystyle\leq$ $\displaystyle
R(s_{t},a_{t})+\mathbb{E}_{s_{t+1}\sim
p(\cdot|s_{t},a_{t})}[\dot{V}^{*}(s_{t+1})]+\varepsilon_{1}\left|\sum_{s_{t+1}\in\textnormal{Succ}(s_{t},a_{t})}\dot{V}^{*}(s_{t+1})\right|+\varepsilon_{2}+\varepsilon_{1}\varepsilon_{2}$
(156) $\displaystyle=$
$\displaystyle\dot{Q}^{*}(s_{t},a_{t})+\varepsilon_{1}\left|\sum_{s_{t+1}\in\textnormal{Succ}(s_{t},a_{t})}\dot{V}^{*}(s_{t+1})\right|+\varepsilon_{2}+\varepsilon_{1}\varepsilon_{2}.$
(157)

Following the same reasoning but using the lower bounds on
$\dot{V}^{N_{n}(s_{t+1})}(s_{t+1})$ and $N(s_{t+1})/N(s_{t},a_{t})$ gives:

$\displaystyle\dot{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})$
$\displaystyle\geq\dot{Q}^{*}(s_{t},a_{t})-\varepsilon_{1}\left|\sum_{s_{t+1}\in\textnormal{Succ}(s_{t},a_{t})}\dot{V}^{*}(s_{t+1})\right|-\varepsilon_{2}+\varepsilon_{1}\varepsilon_{2}.$
(158)

For any $\varepsilon>0$, setting
$\varepsilon_{1}=\min(\varepsilon/3,\varepsilon/3|\sum_{s_{t+1}}\dot{V}^{*}(s_{t+1})|)$
and $\varepsilon_{2}=\min(\varepsilon/3,p(s_{t+1}|s_{t},a_{t}))$ then gives:

$\displaystyle\dot{Q}^{*}(s_{t},a_{t})-\varepsilon\leq\dot{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})\leq\dot{Q}^{*}(s_{t},a_{t})+\varepsilon.$
(159)

Using Lemma E.2 liberally, there is some $C_{2},C_{3},k_{2},k_{3}>0$ such
that:

$\displaystyle\Pr\left(\left|\dot{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})-\dot{Q}^{*}(s_{t},a_{t})\right|\leq\varepsilon\right)$
(160) $\displaystyle>$
$\displaystyle\left(1-C_{1}\exp(-k_{1}\varepsilon_{1}^{2}N(s_{t},a_{t}))\right)\left(1-2\exp\left(-\frac{1}{2}\varepsilon_{2}^{2}N(s_{t},a_{t})\right)\right)$
(161) $\displaystyle=$
$\displaystyle\left(1-C_{2}\exp(-k_{2}\varepsilon^{2}N(s_{t},a_{t})\right)\cdot\left(1-C_{3}\exp(-k_{3}\varepsilon^{2}N(s_{t},a_{t})\right)$
(162) $\displaystyle=$ $\displaystyle
1-C_{2}\exp(-k_{2}\varepsilon^{2}N(s_{t},a_{t}))-C_{3}\exp(-k_{3}\varepsilon^{2}N(s_{t},a_{t}))$
$\displaystyle+C_{2}C_{3}\exp(-(k_{2}+k_{3})\varepsilon^{2}N(s_{t},a_{t}))$
(163) $\displaystyle>$ $\displaystyle
1-C_{2}\exp(-k_{2}\varepsilon^{2}N(s_{t},a_{t}))-C_{3}\exp(-k_{3}\varepsilon^{2}N(s_{t},a_{t})),$
(164)

and then by negating, with $C=C_{1}+C_{2}$ and $k=\min(k_{1},k_{2})$ the
result follows:

$\displaystyle\Pr\left(\left|\dot{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})-\dot{Q}^{*}(s_{t},a_{t})\right|>\varepsilon\right)\leq
C\exp(-k\varepsilon^{2}N(s_{t},a_{t})).$ (165)

∎

###  E.6 MENTS results

In this subsection we provide results related to MENTS. We begin by providing
concentration inequalities for the estimated soft values at each node, around
the optimal soft value. Note that this result is similar to some of the
results provided in xiao2019maximum, however to keep this paper more self
contained we still provide a proof in our particular flavour. After, the
concentration inequalities are then used to show bounds on the simple regret
of MENTS, given constraints on the temperature.

To prove the concentration inequality around the optimal soft values, start by
showing an inductive step.

######  Lemma E.11.

Consider a MENTS process. Let $s_{t}\in\mathcal{S}$, with $1\leq t\leq H$. If
for all $s_{t+1}\in\cup_{a\in\mathcal{A}}\textnormal{Succ}(s_{t},a)$ there is
some $C_{s_{t+1}},k_{s_{t+1}}>0$ for any $\varepsilon_{s_{t+1}}>0$:

$\displaystyle\Pr\left(\left|\hat{V}^{N(s_{t+1})}_{\textnormal{sft}}(s_{t+1})-V^{*}_{\textnormal{sft}}(s_{t+1})\right|>\varepsilon_{s_{t+1}}\right)$
$\displaystyle\leq
C_{s_{t+1}}\exp\left(-k_{s_{t+1}}\varepsilon_{s_{t+1}}^{2}N(s_{t+1})\right),$
(166)

then there is some $C,k>0$, for any $\varepsilon>0$:

$\displaystyle\Pr\left(\left|\hat{V}^{N(s_{t})}_{\textnormal{sft}}(s_{t})-V^{*}_{\textnormal{sft}}(s_{t})\right|>\varepsilon\right)$
$\displaystyle\leq C\exp\left(-k\varepsilon^{2}N(s_{t})\right).$ (167)

###### Proof.

Given the assumptions and by Lemmas E.10, E.4 and E.2, there is some $C,k>0$
such that for any $\varepsilon>0$:

$\displaystyle\Pr\left(\forall
a_{t}\in\mathcal{A}.\left|\hat{Q}^{N(s_{t},a_{t})}_{\textnormal{sft}}(s_{t},a_{t})-Q^{*}_{\textnormal{sft}}(s_{t},a_{t})\right|\leq\varepsilon\right)$
$\displaystyle>1-C\exp(-k\varepsilon^{2}N(s_{t})).$ (168)

So with probability at least $1-C\exp(-k\varepsilon^{2}N(s_{t}))$, for any
$a_{t}$, the following holds:

$\displaystyle
Q^{*}_{\textnormal{sft}}(s_{t},a_{t})-\varepsilon\leq\hat{Q}^{N(s_{t},a_{t})}_{\textnormal{sft}}(s_{t},a_{t})\leq
Q^{*}_{\textnormal{sft}}(s_{t},a_{t})+\varepsilon.$ (169)

Using the upper bound on
$\hat{Q}^{N(s_{t},a_{t})}_{\textnormal{sft}}(s_{t},a_{t})$ in the soft backup
equation for $\hat{V}^{N(s_{t})}_{\textnormal{sft}}(s_{t})$ (Equation (74)
gives:

$\displaystyle\hat{V}^{N(s_{t})}_{\textnormal{sft}}(s_{t})$
$\displaystyle=\alpha\log\sum_{a\in\mathcal{A}}\exp\left(\frac{\hat{Q}^{N(s_{t},a_{t})}_{\textnormal{sft}}(s_{t},a)}{\alpha}\right)$
(170)
$\displaystyle\leq\alpha\log\sum_{a\in\mathcal{A}}\exp\left(\frac{Q^{*}_{\textnormal{sft}}(s_{t},a)+\varepsilon}{\alpha}\right)$
(171)
$\displaystyle=\alpha\log\sum_{a\in\mathcal{A}}\exp\left(\frac{Q^{*}_{\textnormal{sft}}(s_{t},a)}{\alpha}\right)+\varepsilon$
(172) $\displaystyle=V^{*}_{\textnormal{sft}}(s_{t})+\varepsilon,$ (173)

noting that the softmax function monotonically increases in its arguments.
Then with similar reasoning using the lower bound on
$\hat{Q}^{N(s_{t},a_{t})}_{\textnormal{sft}}(s_{t},a_{t})$ gives:

$\displaystyle\hat{V}^{N(s_{t})}_{\textnormal{sft}}(s_{t})\geq
V^{*}_{\textnormal{sft}}(s_{t})-\varepsilon,$ (174)

and hence:

$\displaystyle|\hat{V}^{N(s_{t})}_{\textnormal{sft}}(s_{t})-V^{*}_{\textnormal{sft}}(s_{t})|\leq\varepsilon.$
(175)

This therefore shows:

$\displaystyle\Pr\left(\left|\hat{V}^{N(s_{t})}_{\textnormal{sft}}(s_{t})-V^{*}_{\textnormal{sft}}(s_{t})\right|\leq\varepsilon_{1}\right)>1-C\exp(-k\varepsilon^{2}N(s_{t})),$
(176)

and negating probabilities gives the result. ∎

Then completing the induction gives the concentration inequalities desired for
any state that MENTS might visit.

######  Theorem E.12.

Consider a MENTS process, let $s_{t}\in\mathcal{S}$ then there is some $C,k>0$
for any $\varepsilon>0$:

$\displaystyle\Pr\left(\left|\hat{V}^{N(s_{t})}_{\textnormal{sft}}(s_{t})-V^{*}_{\textnormal{sft}}(s_{t})\right|>\varepsilon\right)$
$\displaystyle\leq C\exp\left(-k\varepsilon^{2}N(s_{t})\right).$ (177)

Moreover, at the root node $s_{0}$ we have:

$\displaystyle\Pr\left(\left|\hat{V}^{N(s_{0})}_{\textnormal{sft}}(s_{0})-V^{*}_{\textnormal{sft}}(s_{0})\right|>\varepsilon\right)$
$\displaystyle\leq C\exp\left(-k\varepsilon^{2}n\right).$ (178)

###### Proof.

Consider that the result holds for $t=H+1$, because
$\hat{V}^{N(s_{H+1})}_{\textnormal{sft}}(s_{H+1})=V^{*}_{\textnormal{sft}}(s_{H+1})=0$.
Therefore the result holds for any $t=1,...,H+1$ by induction using Lemma
E.11. Noting that $N(s_{0})=n$ gives (178). ∎

Note that all of our concentration inequalities imply a convergence in
probability. For example, we explicitly demonstrate this in Corollary E.12.1.

######  Corollary E.12.1.

$\hat{Q}^{N(s_{t},a_{t})}_{\textnormal{sft}}(s_{t},a_{t})\overset{p}{\to}Q^{*}_{\textnormal{sft}}(s_{t},a_{t})$

###### Proof.

This follows from the concentration inequalities shown in Lemma E.10 and
Theorem E.12. As the RHS of the bound tend to zero as $n\rightarrow\infty$,
these concentration inequalities follow by taking the limit
$n\rightarrow\infty$:

$\displaystyle\lim_{n\rightarrow\infty}\Pr\left(\left|\hat{Q}^{N(s_{t},a_{t})}_{\textnormal{sft}}(s_{t},a_{t})-Q^{*}_{\textnormal{sft}}(s_{t},a_{t})\right|>\varepsilon\right)$
$\displaystyle\leq\lim_{n\rightarrow\infty}C\exp\left(-k\varepsilon^{2}N(s_{t})\right)$
(179) $\displaystyle=0.$ (180)

∎

Now we use the concentration inequalities to show that we are exponentially
unlikely to recommend a suboptimal action with respect to the standard values
(i.e. the simple regret tends to zero exponentially), provided the temperature
parameter $\alpha$ is small enough.

######  Lemma E.13.

Consider a MENTS process with
$\alpha<\Delta_{\mathcal{M}}/3H\log|\mathcal{A}|$. Let $s_{t}\in\mathcal{S}$,
with $1\leq t\leq H$ then there is some $C^{\prime},k^{\prime}>0$ such that:

$\displaystyle\mathbb{E}\textnormal{reg}_{I}(s_{t},\psi^{n}_{\textnormal{MENTS}})$
$\displaystyle\leq C^{\prime}\exp\left(-k^{\prime}N(s_{t})\right).$ (181)

###### Proof.

Let $a^{*}$ be the optimal action with respect to the soft values, so
$a^{*}=\operatorname*{arg\,max}_{a\in\mathcal{A}}Q^{*}_{\textnormal{sft}}(s_{t},a)$.
Then by Lemma E.7 $a^{*}$ must also be the optimal action for the standard
Q-value function
$a^{*}=\operatorname*{arg\,max}_{a\in\mathcal{A}}Q^{*}(s_{t},a)$. By Theorem
E.12 and Lemmas E.10 and E.4 there exists $C_{1},k_{1}>0$ such that for all
$\varepsilon_{1}>0$:

$\displaystyle\Pr\left(\forall
a_{t}\in\mathcal{A}\left|\hat{Q}^{N(s_{t},a_{t})}_{\textnormal{sft}}(s_{t},a_{t})-Q^{*}_{\textnormal{sft}}(s_{t},a_{t})\right|\leq\varepsilon_{1}\right)$
$\displaystyle>1-C_{1}\exp(-k_{1}\varepsilon_{1}^{2}N(s_{t})).$ (182)

Setting $\varepsilon_{1}=\Delta_{\mathcal{M}}/3H\log|\mathcal{A}|$ then gives
with probability at least $1-C_{1}\exp(-k_{2}N(s_{t}))$ (where
$k_{2}=k_{1}(\Delta_{\mathcal{M}}/3H\log|\mathcal{A}|)^{2}$) that for all
actions $a_{t}\in\mathcal{A}$:

$\displaystyle
Q^{*}_{\textnormal{sft}}(s_{t},a_{t})-\Delta_{\mathcal{M}}/3\leq\hat{Q}^{N(s_{t},a_{t})}_{\textnormal{sft}}(s_{t},a_{t})\leq
Q^{*}_{\textnormal{sft}}(s_{t},a_{t})+\Delta_{\mathcal{M}}/3.$ (183)

And hence, with probability at least $1-C_{1}\exp(-k_{2}N(s_{t}))$, for all
$a\in\mathcal{A}-\\{a^{*}\\}$ we have:

$\displaystyle\hat{Q}^{N(s_{t},a)}_{\textnormal{sft}}(s_{t},a)\leq$
$\displaystyle Q^{*}_{\textnormal{sft}}(s_{t},a)+\Delta_{\mathcal{M}}/3$ (184)
$\displaystyle\leq$ $\displaystyle Q^{*}(s_{t},a)+\alpha
H\log|\mathcal{A}|+\Delta_{\mathcal{M}}/3$ (185) $\displaystyle\leq$
$\displaystyle Q^{*}(s_{t},a)+2\Delta_{\mathcal{M}}/3$ (186)
$\displaystyle\leq$ $\displaystyle Q^{*}(s_{t},a^{*})-\Delta_{\mathcal{M}}/3$
(187) $\displaystyle\leq$ $\displaystyle
Q^{*}_{\textnormal{sft}}(s_{t},a^{*})-\Delta_{\mathcal{M}}/3$ (188)
$\displaystyle\leq$
$\displaystyle\hat{Q}^{N(s_{t},a^{*})}_{\textnormal{sft}}(s_{t},a^{*}).$ (189)

Where in the above, the first line holds from the upper bound on
$\hat{Q}^{N(s_{t},a_{t})}_{\textnormal{sft}}(s_{t},a_{t})$; The second holds
from maximising the standard return and entropy portions of the soft value
seperately (recall Inequality (124) in Lemma E.7); The third holds from the
assumption on $\alpha$; The fourth holds from the definition of
$\Delta_{\mathcal{M}}$ (also see Inequality (122)); The fifth holds from the
optimal soft value being greater than the optimal standard value (Lemma E.6);
And the final line holds by using the lower bound on
$\hat{Q}^{N(s_{t},a_{t})}_{\textnormal{sft}}(s_{t},a_{t})$ given above with
$a_{t}=a^{*}$.

Negating the probability that (189) holds gives:

$\displaystyle\Pr\left(\exists
a_{t}\in\mathcal{A}-\\{a^{*}\\}.\left(\hat{Q}^{N(s_{t},a)}_{\textnormal{sft}}(s_{t},a)>\hat{Q}^{N(s_{t},a^{*})}_{\textnormal{sft}}(s_{t},a^{*})\right)\right)\leq
C_{1}\exp(-k_{2}N(s_{t})).$ (190)

Finally, we can bound our expected immediate regret as follows:

$\displaystyle\mathbb{E}\textnormal{reg}_{I}(s_{t},\psi^{n}_{\text{MENTS}})$
(191) $\displaystyle=$
$\displaystyle\sum_{a\in\mathcal{A}-\\{a^{*}\\}}\left(V^{*}(s_{t})-Q^{*}(s_{t},a)\right)\Pr\left(\psi^{n}_{\text{MENTS}}(s_{t})=a\right)$
(192) $\displaystyle=$
$\displaystyle\sum_{a\in\mathcal{A}-\\{a^{*}\\}}\left(V^{*}(s_{t})-Q^{*}(s_{t},a)\right)\Pr\left(a=\operatorname*{arg\,max}_{a^{\prime}}\hat{Q}^{N(s_{t},a)}_{\textnormal{sft}}(s_{t},a^{\prime})\right)$
(193) $\displaystyle\leq$
$\displaystyle\sum_{a\in\mathcal{A}-\\{a^{*}\\}}\left(V^{*}(s_{t})-Q^{*}(s_{t},a)\right)\Pr\left(\hat{Q}^{N(s_{t},a)}_{\textnormal{sft}}(s_{t},a)>\hat{Q}^{N(s_{t},a^{*})}_{\textnormal{sft}}(s_{t},a^{*})\right)$
(194) $\displaystyle\leq$
$\displaystyle\sum_{a\in\mathcal{A}-\\{a^{*}\\}}\left(V^{*}(s_{t})-Q^{*}(s_{t},a)\right)C_{1}\exp(-k_{2}N(s_{t})),$
(195)

and setting $k^{\prime}=k_{2}$ and
$C^{\prime}=C_{1}\sum_{a\in\mathcal{A}-\\{a^{*}\\}}\left(V^{*}(s_{t})-Q^{*}(s_{t},a)\right)$
gives the result. ∎

And finally, by using Lemma E.13, we can convert the bound on the immediate
simple regret to a bound on the simple regret.

######  Theorem E.14.

Consider a MENTS process with
$\alpha<\Delta_{\mathcal{M}}/3H\log|\mathcal{A}|$. Let $s_{t}\in\mathcal{S}$,
with $1\leq t\leq H$ then there is some $C^{\prime},k^{\prime}>0$ such that:

$\displaystyle\mathbb{E}\textnormal{reg}(s_{t},\psi^{n}_{\textnormal{MENTS}})$
$\displaystyle\leq C^{\prime}\exp\left(-k^{\prime}N(s_{t})\right).$ (196)

Moreover, at the root node $s_{0}$ we have:

$\displaystyle\mathbb{E}\textnormal{reg}(s_{0},\psi^{n}_{\textnormal{MENTS}})$
$\displaystyle\leq C^{\prime}\exp\left(-k^{\prime}n)\right).$ (197)

###### Proof.

This theorem holds as a consequence of Corollary E.8.1 and Lemma E.13, and
noting that at the root node $N(s_{0})=n$. ∎

We have now shown Theorem 3.2:

######  Theorem 3.2.

For any MDP $\mathcal{M}$, after running $n$ trials of the MENTS algorithm
with $\alpha\leq\Delta_{\mathcal{M}}/3H\log|\mathcal{A}|$, there exists
constants $C,k>0$ such that:
$\mathbb{E}[\textnormal{reg}(s_{0},\psi^{n}_{\textnormal{MENTS}})]\leq
C\exp(-kn)$, where
$\Delta_{\mathcal{M}}=\min\\{Q^{*}(s,a,t)-Q^{*}(s,a^{\prime},t)|Q^{*}(s,a,t)\neq
Q^{*}(s,a^{\prime},t),s\in\mathcal{S},a,a^{\prime}\in\mathcal{A},t\in\mathbb{N}\\}$.

###### Proof.

This is part of Theorem E.14. ∎

And to show Proposition 3.1 we will utilise Theorem E.12 and return to the
modified 10-chain problem, with illustration repeated in Figure 32 for
reference.

######  Proposition 3.1.

There exists an MDP $\mathcal{M}$ and temperature $\alpha$ such that
$\mathbb{E}[\textnormal{reg}(s_{0},\psi^{n}_{\textnormal{MENTS}})]\not\to 0$
as $n\to\infty$. That is, MENTS is not consistent.

###### Proof.

We give a proof by construction. Recall the modified 10-chain problem, with
$R_{f}=1/2$ in Figure 32, and consider a MENTS process (i.e. running MENTS)
with a temperature $\alpha=1$ for $n$ trials. By considering the optimal soft
Bellman equations (4) and (5), one can verify that
$Q^{*}_{\textnormal{sft}}(1,2)=0.9$ and
$Q^{*}_{\textnormal{sft}}(1,1)=\log\left(\exp(1/2)+\sum_{i=0}^{8}\exp(i/10)\right)\approx
2.74$.

Theorem E.12, Lemma E.10 and Lemma E.4 implies that there is some $C,k>0$ for
any $\varepsilon>0$:

$\displaystyle\Pr\left(\left|Q^{N(1,1)}_{\textnormal{sft}}(1,1)-Q^{*}_{\textnormal{sft}}(1,1)\right|>\varepsilon\right)\leq
C\exp(-k\varepsilon^{2}N(1))=C\exp(-k\varepsilon^{2}n).$ (198)

Letting $\varepsilon=1$ and using $Q^{*}_{\textnormal{sft}}(1,1)>5/2$ gives:

$\displaystyle\Pr\left(Q^{N(1,1)}_{\textnormal{sft}}(1,1)<3/2\right)\leq$
$\displaystyle\Pr\left(\left|Q^{N(1,1)}_{\textnormal{sft}}(1,1)-Q^{*}_{\textnormal{sft}}(1,1)\right|>1\right)$
(199) $\displaystyle\leq$ $\displaystyle C\exp(-kn).$ (200)

And hence:

$\displaystyle\Pr(\psi^{n}_{\text{MENTS}}(1)=1)>1-C\exp(-kn)$ (201)

Consider that the best simple regret an agent can achieve after selecting
action 1 from the starting state is $1/10$. Let $M=\log(2C)/k$, so that
$C\exp(-kM)=1/2$. Then, for all $n>M$ we have
$\Pr(\psi^{n}_{\text{MENTS}}(1)=1)>1/2$, and hence:

$\displaystyle\mathbb{E}\textnormal{reg}(1,\psi^{n}_{\text{MENTS}})$
$\displaystyle>\frac{1}{10}\cdot\Pr(\psi^{n}_{\text{MENTS}}(1)=1)$ (202)
$\displaystyle>\frac{1}{20}.$ (203)

Thus $\mathbb{E}r(1,\psi^{n}_{\text{MENTS}})\not\rightarrow 0$. ∎

Figure 32: An illustration of the (modified) D-chain problem, where 1 is the
starting state, all transitions are deterministic and values next to states
represents the reward for arriving in that state.

Additionally, we can show that there is an MDP such that for any $\alpha$
MENTS will either not be consistent, or will take exponentially long in the
size of the state space of the MDP. Below we state this formally and provide a
proof outline in Theorem E.15, which uses the MDP defined in Figure 33.

Figure 33: An illustration of the adapted-chain problem, where 1 is the
starting state, all transitions are deterministic and values next to states
represents the reward for arriving in that state. The MDP is split into two
sections, firstly, the UCT gauntlet refers to the D-chain part of the MDP,
which is difficult for UCT algorithms, and secondly, the entropy trap, where
the agent has to chose between states $E$ and $F$. The entropy trap consists
of two chains of $K$ states, all of which give a reward of $0$ for visiting,
but allows an agent to follow a policy with up to $\log(2)K$ entropy. So the
optimal values for $E$ and $F$ are $V^{*}_{\textnormal{sft}}(E)=\log(2)K$ and
$V^{*}_{\textnormal{sft}}(F)=1$ respectively.

######  Theorem E.15.

Consider a MENTS process with arbitrary temperature $\alpha$. There exists and
MDP such that for any $\alpha$ that MENTS is either not consistent, or
requires an exponential number of trials in the size of the state space. More
precisely, either
$\mathbb{E}\textnormal{reg}(s_{0},\psi^{n}_{\text{MENTS}})\not\rightarrow 0$
or $\mathbb{E}\textnormal{reg}(1,\psi^{n}_{\text{MENTS}})\geq
c(1-\frac{n}{k^{|S|}})$, which implies that
$\mathbb{E}\textnormal{reg}(s_{0},\psi^{n}_{MENTS})>0$ for $n<k^{|S|}$.

###### Proof outline.

Proof by construction. Consider the adapted-chain MDP defined in Figure 33,
which is parameterised by $D$ the length of the UCT gauntlet, and $K$ half the
number of states in the entropy trap. To show our claim, we split the analysis
into two cases.

Case 1: $\alpha>\frac{1}{\log(2)K}$

If $\alpha>\frac{1}{\log(2)K}$, the soft value of E is greater than one for
any policy over the actions, and $\phi$ is a uniform policy (note that because
there are no MDP rewards after $E$, $\phi$ is both the initial policy for
MENTS and the optimal soft policy):

$\displaystyle V^{*}_{\textnormal{sft}}(E)$
$\displaystyle=0+\alpha\cdot\mathcal{H}(\phi)$ (204)
$\displaystyle=\alpha\cdot\log(2)K$ (205) $\displaystyle>1$ (206)
$\displaystyle=V^{*}_{\textnormal{sft}}(F).$ (207)

Hence the optimal soft poilicy (which MENTS converges to) will recommend going
to state $E$ and gathering $0$ reward. Hence in this case the simple regret
will converge to $1$ as the optimal value is $V^{*}(1)=1$. That is
$\mathbb{E}\textnormal{reg}(1,\psi^{n}_{\text{MENTS}})\rightarrow 1>0$.

Case 2: $\alpha\leq\frac{1}{\log(2)K}$

In this case, we argue that with a low $\alpha$ that MENTS will only have a
low probability of hitting state $D$, that is, it requires a lot of trials to
garuntee that at least one trial has reached state $D$, which is necessary to
get the reward of $1$ (and simple regret of $0$).

First consider the composed and simplified soft backup on the adapted-chain
problem for any $0<i<D$ to get:

$\displaystyle\hat{V}^{N(i-1)}_{\textnormal{sft}}(i-1)$
$\displaystyle=\alpha\log\left(\frac{1}{\alpha}\left(\frac{D-i+1}{D}+\hat{V}^{N(i+1)}_{\textnormal{sft}}(i+1)\right)\right)$
(208)
$\displaystyle\leq\max\left(\frac{D-i+1}{D},\hat{V}^{N(i)}_{\textnormal{sft}}(i)\right)+\alpha\log(2)$
(209)
$\displaystyle\leq\max\left(\frac{D-i+1}{D},\hat{V}^{N(i)}_{\textnormal{sft}}(i)\right)+\frac{1}{K}$
(210)

where we used the property of log-sum-exp that
$\alpha\log\sum_{i=1}^{\ell}\exp(x_{i}/\alpha)\leq\max_{i}(x_{i})+\alpha\log(\ell)$.
Assume that $K\geq D$ and $\hat{V}^{N(D)}_{\textnormal{sft}}(D)=0$ (we will
check these assumptions are valid later). Then using an induction hypothesis
of $\hat{V}^{N(i)}_{\textnormal{sft}}(i)\leq\frac{D-i+1}{D}$ we have:

$\displaystyle\hat{V}^{N(i-1)}_{\textnormal{sft}}(i-1)$
$\displaystyle\leq\max(\frac{D-i+1}{D},\hat{V}^{N(i)}_{\textnormal{sft}}(i))+\frac{\log(2)}{\log(K)}$
(211) $\displaystyle=\frac{D-i+1}{D}+\frac{1}{K}$ (212)
$\displaystyle\leq\frac{D-i+1}{D}+\frac{1}{D}$ (213)
$\displaystyle=\frac{D-i+2}{D}=\frac{D-(i-1)+1}{D}$ (214)

We can then show that the probability the event $Y(n)$ that MENTS visits state
$D$ in its $n$th trial is less than $2^{-D}$, given
$\hat{V}^{N(D)}_{\textnormal{sft}}(D)=0$. Because we have just shown that
$\hat{V}^{N(i)}_{\textnormal{sft}}(i)\leq\frac{D-i+1}{D}=\hat{V}^{N(G_{i-1})}_{\textnormal{sft}}(G_{i-1})$,
using a symmetry argument we must have
$\psi^{n}_{\text{MENTS}}(a_{R}|i)<\frac{1}{2}$, and as such, we must have
$\Pr\left(Y(n)\middle|\hat{V}^{N(D)}_{\textnormal{sft}}(D)=0\right)<\frac{1}{2^{D}}$.

Then let $Z(n)=\neg\bigcup_{j=1}^{n}Y(j)$ be the event that no trial of MENTS
has visited state $D$ in any of the first $n$ trials. And note that $Z(n)$
implies that $\hat{V}^{N(D)}_{\textnormal{sft}}(D)=0$:

$\displaystyle\Pr(Z(n))$
$\displaystyle=\Pr\left(Z(n)\cap\hat{V}^{N(D)}_{\textnormal{sft}}(D)=0\right)$
(215) $\displaystyle=\Pr\left(\neg Y(n)\cap
Z(n-1)\cap\hat{V}^{N(D)}_{\textnormal{sft}}(D)=0\right)$ (216)
$\displaystyle=\Pr\left(\neg
Y(n)\middle|Z(n-1)\cap\hat{V}^{N(D)}_{\textnormal{sft}}(D)=0\right)\Pr\left(Z(n-1)\cap\hat{V}^{N(D)}_{\textnormal{sft}}(D)=0\right)$
(217)
$\displaystyle\geq(1-2^{-D})\Pr\left(Z(n-1)\cap\hat{V}^{N(D)}_{\textnormal{sft}}(D)=0\right)$
(218) $\displaystyle=...$ (219)
$\displaystyle\geq(1-2^{-D})^{n}\Pr\left(Z(0)\cap\hat{V}^{N(D)}_{\textnormal{sft}}(D)=0\right)$
(220) $\displaystyle=(1-2^{-D})^{n}$ (221) $\displaystyle\geq 1-n2^{-D},$
(222)

where in the penultimate line we used
$\Pr\left(Z(0)\cap\left(\hat{V}^{N(D)}_{\textnormal{sft}}(D)=0\right)\right)=1$,
as $Z(0)$ and $\hat{V}^{N(D)}_{\textnormal{sft}}(D)=0$ are vacuously true at
the start of running the algorithm, and in the final line we used Bernoulli’s
inequality.

Informally, $Z(n)$ implies that
$V^{\psi^{n}_{\text{MENTS}}}(1)\leq\frac{9}{10}$, as no trial has even reached
$D$ to be able to reach the reward of $1$ from $F$. And hence the expected
simple regret in this environment of MENTS can be bounded below as follows:

$\displaystyle\mathbb{E}\textnormal{reg}(1,\psi^{n}_{\text{MENTS}})$
$\displaystyle\geq\left(1-\frac{9}{10}\right)\Pr(Z(n))$ (223)
$\displaystyle\geq\frac{1}{10}\left(1-n2^{-D}\right).$ (224)

Finally, setting $K=D$, we must have that $D>\frac{|S|}{3}$ and so
$\mathbb{E}\textnormal{reg}(1,\psi^{n}_{\text{MENTS}})\geq
1-\frac{n}{\sqrt[3]{2}^{|S|}}$, which is greater than $0$ for
$n<\sqrt[3]{2}^{|S|}$. That is $c=0.1$ and $k=\sqrt[3]{2}$.

∎

###  E.7 DENTS results

In this subsection we provide results related to DENTS. Similarly to the MENTS
results, we begin by providing concentration inequalities for the estimated
soft values at each node, around the optimal soft value. And after, the
concentration inequalities are then used to show bounds on the simple regret
of DB-MENTS, however, this time no constraints on the temperature are
required.

######  Lemma E.16.

Consider a DENTS process. Let $s_{t}\in\mathcal{S}$, with $1\leq t\leq H$. If
for all $s_{t+1}\in\cup_{a\in\mathcal{A}}\textnormal{Succ}(s_{t},a)$ we have
some $C_{s_{t+1}},k_{s_{t+1}}>0$ for any $\varepsilon_{s_{t+1}}>0$:

$\displaystyle\Pr\left(\left|\hat{V}^{N(s_{t+1})}(s_{t+1})-V^{*}(s_{t+1})\right|>\varepsilon_{s_{t+1}}\right)$
$\displaystyle\leq
C_{s_{t+1}}\exp\left(-k_{s_{t+1}}\varepsilon_{s_{t+1}}^{2}N(s_{t+1})\right),$
(225)

then there is some $C,k>0$, for any $\varepsilon>0$:

$\displaystyle\Pr\left(\left|\hat{V}^{N(s_{t})}(s_{t})-V^{*}(s_{t})\right|>\varepsilon\right)$
$\displaystyle\leq C\exp\left(-k\varepsilon^{2}N(s_{t})\right).$ (226)

###### Proof.

Given the assumptions and by Lemmas E.10, E.2 and E.4, for some $C,k>0$ we
have for any $\varepsilon_{1}>0$:

$\displaystyle\Pr\left(\forall
a_{t}\in\mathcal{A}.\left|\hat{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})-Q^{*}(s_{t},a_{t})\right|\leq\varepsilon_{1}\right)$
$\displaystyle>1-C\exp(-k\varepsilon_{1}^{2}N(s_{t})).$ (227)

Let $\varepsilon>0$, and set
$\varepsilon_{1}=\min(\varepsilon,\Delta_{\mathcal{M}}/2)$. So with
probability at least $1-C_{1}\exp(-k_{1}\varepsilon_{1}^{2}N(s_{t}))$ we have
for any $a_{t}$ that:

$\displaystyle
Q^{*}(s_{t},a_{t})-\varepsilon_{1}\leq\hat{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})$
$\displaystyle\leq Q^{*}(s_{t},a_{t})+\varepsilon_{1}.$ (228)

Let $a^{*}=\max_{a\in\mathcal{A}}Q^{*}(s_{t},a)$. Using
$\varepsilon_{1}\leq\Delta_{\mathcal{M}}/2$ in (228), then for any
$a\in\mathcal{A}-\\{a^{*}\\}$:

$\displaystyle\hat{Q}^{N(s_{t},a)}(s_{t},a)\leq$ $\displaystyle
Q^{*}(s_{t},a)+\Delta_{\mathcal{M}}/2$ (229) $\displaystyle\leq$
$\displaystyle Q^{*}(s_{t},a^{*})-\Delta_{\mathcal{M}}/2$ (230)
$\displaystyle\leq$ $\displaystyle\hat{Q}^{N(s_{t},a^{*})}(s_{t},a^{*}),$
(231)

and hence
$\operatorname*{arg\,max}_{a\in\mathcal{A}}\hat{Q}^{N(s_{t},a)}(s_{t},a)=a^{*}$.
As a consequence:

$\displaystyle\hat{V}^{N(s_{t})}(s_{t})$
$\displaystyle=\max_{a}\hat{Q}^{N(s_{t},a)}(s_{t},a)=\hat{Q}^{N(s_{t},a^{*})}(s_{t},a^{*}).$
(232)

Then using (228) with $a_{t}=a^{*}$ (noting
$V^{*}(s_{t})=Q^{*}(s_{t},a^{*})$), using (232) and using
$\varepsilon_{1}\leq\varepsilon$ gives:

$\displaystyle V^{*}(s_{t})-\varepsilon\leq$ $\displaystyle
V^{*}(s_{t})-\varepsilon_{1}$ (233) $\displaystyle\leq$
$\displaystyle\hat{V}^{N(s_{t})}(s_{t})$ (234) $\displaystyle\leq$
$\displaystyle V^{*}(s_{t})+\varepsilon_{1}$ (235) $\displaystyle\leq$
$\displaystyle V^{*}(s_{t})+\varepsilon.$ (236)

Hence:

$\displaystyle\Pr\left(\left|\hat{V}^{N(s_{t})}(s_{t})-V^{*}(s_{t})\right|>\varepsilon\right)\leq
C\exp(-k\varepsilon_{1}^{2}N(s_{t}))\leq C\exp(-k\varepsilon^{2}N(s_{t})),$
(237)

which is the result. ∎

Similarly to the MENTS section, Lemma E.16 provides an inductive step, which
is used in Theorem E.17 to show concentration inequalities at all states that
DENTS visits.

######  Theorem E.17.

Consider a DENTS process, let $s_{t}\in\mathcal{S}$ then there is some $C,k>0$
for any $\varepsilon>0$:

$\displaystyle\Pr\left(\left|\hat{V}^{N(s_{t})}(s_{t})-V^{*}(s_{t})\right|>\varepsilon\right)$
$\displaystyle\leq C\exp\left(-k\varepsilon^{2}N(s_{t})\right).$ (238)

Moreover, at the root node $s_{0}$ we have:

$\displaystyle\Pr\left(\left|\hat{V}^{N(s_{0})}(s_{0})-V^{*}(s_{0})\right|>\varepsilon\right)$
$\displaystyle\leq C\exp\left(-k\varepsilon^{2}n\right).$ (239)

###### Proof.

The result holds for $t=H+1$ because
$\hat{V}^{N(s_{H+1})}(s_{H+1})=V^{*}(s_{H+1})=0$. Hence the result holds for
all $t=1,...,H+1$ by induction using Lemma E.16. Noting that $N(s_{0})=n$
gives (239). ∎

Again, the concentration inequalities are used to show that the simple regret
tends to zero exponentially, and therefore that DENTS will be exponentially
likely in the number of visits to recommend the optimal standard action at
every node.

######  Lemma E.18.

Consider a DENTS process. Let $s_{t}\in\mathcal{S}$, with $1\leq t\leq H$ then
there is some $C^{\prime},k^{\prime}>0$ such that:

$\displaystyle\mathbb{E}\textnormal{reg}_{I}(s_{t},\psi^{n}_{\textnormal{DENTS}})$
$\displaystyle\leq C^{\prime}\exp\left(-k^{\prime}N(s_{t})\right).$ (240)

###### Proof.

Let $a^{*}$ be the locally optimal standard action, so
$a^{*}=\operatorname*{arg\,max}_{a\in\mathcal{A}}Q^{*}(s_{t},a)$. By Theorem
E.17 and Lemmas E.10 and E.4 there exists $C_{1},k_{1}>0$ such that for all
$\varepsilon_{1}>0$:

$\displaystyle\Pr\left(\forall
a_{t}\in\mathcal{A}.\left|\hat{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})-Q^{*}(s_{t},a_{t})\right|\leq\varepsilon_{1}\right)$
$\displaystyle>1-C_{1}\exp(-k_{1}\varepsilon_{1}^{2}N(s_{t})).$ (241)

Setting $\varepsilon_{1}=\Delta_{\mathcal{M}}/2$ then gives with probability
$1-C_{1}\exp(-k_{2}N(s_{t}))$ (where $k_{2}=k_{1}\Delta_{\mathcal{M}}/2$) for
all actions $a\in\mathcal{A}$ that:

$\displaystyle
Q^{*}(s_{t},a)-\Delta_{\mathcal{M}}/2\leq\hat{Q}^{N(s_{t},a_{t})}(s_{t},a)\leq
Q^{*}(s_{t},a)+\Delta_{\mathcal{M}}/2.$ (242)

And hence, with probability $1-C_{1}\exp(-k_{2}N(s_{t}))$, for all
$a_{t}\in\mathcal{A}-\\{a^{*}\\}$ we have:

$\displaystyle\hat{Q}^{N(s_{t},a)}(s_{t},a_{t})\leq$ $\displaystyle
Q^{*}(s_{t},a_{t})+\Delta_{\mathcal{M}}/2$ (243) $\displaystyle\leq$
$\displaystyle Q^{*}(s_{t},a^{*})-\Delta_{\mathcal{M}}/2$ (244)
$\displaystyle\leq$ $\displaystyle\hat{Q}^{N(s_{t},a^{*})}(s_{t},a^{*}).$
(245)

Negating the probability of (245) then gives:

$\displaystyle\Pr\left(\hat{Q}^{N(s_{t},a)}_{\textnormal{sft}}(s_{t},a)>\hat{Q}^{N(s_{t},a^{*})}_{\textnormal{sft}}(s_{t},a^{*})\right)\leq
C_{1}\exp(-k_{2}N(s_{t}))$ (246)

Finally, the bound on the expected immediate regret follows:

$\displaystyle\mathbb{E}\textnormal{reg}_{I}(s_{t},\psi^{n}_{\text{DENTS}})$
(247) $\displaystyle=$
$\displaystyle\sum_{a\in\mathcal{A}-\\{a^{*}\\}}\left(V^{*}(s_{t})-Q^{*}(s_{t},a)\right)\Pr\left(\psi^{n}_{\text{DENTS}}(s_{t})=a\right)$
(248) $\displaystyle=$
$\displaystyle\sum_{a\in\mathcal{A}-\\{a^{*}\\}}\left(V^{*}(s_{t})-Q^{*}(s_{t},a)\right)\Pr\left(a=\operatorname*{arg\,max}_{a^{\prime}}\hat{Q}^{N(s_{t},a)}(s_{t},a^{\prime})\right)$
(249) $\displaystyle\leq$
$\displaystyle\sum_{a\in\mathcal{A}-\\{a^{*}\\}}\left(V^{*}(s_{t})-Q^{*}(s_{t},a)\right)\Pr\left(\hat{Q}^{N(s_{t},a)}(s_{t},a)>\hat{Q}^{N(s_{t},a^{*})}(s_{t},a^{*})\right)$
(250) $\displaystyle\leq$
$\displaystyle\sum_{a\in\mathcal{A}-\\{a^{*}\\}}\left(V^{*}(s_{t})-Q^{*}(s_{t},a)\right)C_{1}\exp(-k_{2}N(s_{t})),$
(251)

and setting $k^{\prime}=k_{2}$ and
$C^{\prime}=C_{1}\sum_{a\in\mathcal{A}-\\{a^{*}\\}}\left(V^{*}(s_{t})-Q^{*}(s_{t},a)\right)$
gives the result. ∎

Again similarly to before, by using Lemma E.18, we can convert the bound on
the immediate simple regret to a bound on the simple regret.

######  Theorem E.19.

Consider a DENTS process. Let $s_{t}\in\mathcal{S}$, with $1\leq t\leq H$ then
there is some $C^{\prime},k^{\prime}>0$ such that:

$\displaystyle\mathbb{E}\textnormal{reg}(s_{t},\psi^{n}_{\textnormal{DENTS}})$
$\displaystyle\leq C^{\prime}\exp\left(-k^{\prime}N(s_{t})\right).$ (252)

Moreover, at the root node $s_{0}$:

$\displaystyle\mathbb{E}\textnormal{reg}(s_{0},\psi^{n}_{\textnormal{DENTS}})$
$\displaystyle\leq C^{\prime}\exp\left(-k^{\prime}n)\right).$ (253)

###### Proof.

Theorem holds as a consequence of Corollary E.8.1 and Lemma E.18. To arrive at
(253) note that $N(s_{0})=n$. ∎

Finally, Theorem 4.2 follows from the results that we have just shown.

Finally, we have shown Theorem 4.2, as it is a subset of what we have already
shown.

######  Theorem 4.2.

For any MDP $\mathcal{M}$, after running $n$ trials of the DENTS algorithm
with a root node of $s_{0}$, if $\beta$ is bounded above and $\beta(m)\geq 0$
for all $m\in\mathbb{N}$, then there exists constants $C,k>0$ such that for
all $\varepsilon>0$ we have
$\mathbb{E}[\textnormal{reg}(s_{0},\psi^{n}_{\textnormal{DENTS}})]\leq
C\exp(-kn)$, and also $\hat{V}^{N(s_{0})}(s_{0})\overset{p}{\to}V^{*}(s_{0})$
as $n\rightarrow\infty$.

###### Proof.

The simple regret bound follows immediately from Theorem E.19. Using Theorem
E.17 we must have
$\Pr\left(\left|\hat{V}^{N(s_{0})}(s_{0})-V^{*}(s_{0})\right|>\varepsilon\right)\leq
C\exp\left(-k\varepsilon^{2}n\right)\rightarrow 0$ as $n\rightarrow\infty$,
and hence $\hat{V}^{N(s_{0})}(s_{0})$ converges in probability to
$V^{*}(s_{0})$. ∎

###  E.8 BTS results

Recall that the BTS process is a special case of the DENTS process, where the
decay function is set to $\beta(m)=0$. As such, all of the results for DENTS
processes also hold for BTS processes, and specifically Theorem 4.1 must hold.

######  Theorem 4.1.

For any MDP $\mathcal{M}$, after running $n$ trials of the BTS algorithm with
a root node of $s_{0}$, there exists constants $C,k>0$ such that for all
$\varepsilon>0$ we have
$\mathbb{E}[\textnormal{reg}(s_{0},\psi^{n}_{\textnormal{BTS}})]\leq
C\exp(-kn)$, and also $\hat{V}^{N(s_{0})}(s_{0})\overset{p}{\to}V^{*}(s_{0})$
as $n\rightarrow\infty$.

###### Proof.

Follows from setting $\beta(m)=0$ and using Theorem 4.2. ∎

###  E.9 Results for using average returns in Boltzmann MCTS processes

In this section we give informal proof outlines of our results for AR-BTS and
AR-DENTS. To begin with we define the average return $\bar{V}^{N(s)}(s)$ for a
decision node at $s$, and recall the definition of $\bar{Q}^{N(s,a)}(s,a)$:

$\displaystyle\bar{V}^{N(s_{t})+1}(s_{t})$
$\displaystyle=\bar{V}^{N(s_{t})}(s_{t})+\frac{\bar{R}(s_{t})-\bar{V}^{N(s_{t})}(s_{t})}{N(s_{t})+1},$
(254) $\displaystyle\bar{Q}^{N(s_{t},a_{t})+1}(s_{t},a_{t})$
$\displaystyle=\bar{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})+\frac{\bar{R}(s_{t},a_{t})-\bar{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})}{N(s_{t},a_{t})+1},$
(255)

where $\bar{R}(s_{t})=\sum_{i=t}^{H}R(s_{i},a_{i})$ and
$\bar{R}(s_{t},a_{t})=\sum_{i=t}^{H}R(s_{i},a_{i})$. Note that these average
return values also satisfy the equations:

$\displaystyle\bar{V}^{N(s_{t})}(s_{t})$
$\displaystyle=\sum_{a\in\mathcal{A}}\frac{N(s_{t},a)}{N(s_{t})}\bar{Q}^{N(s_{t},a_{t})}(s_{t},a_{t}),$
(256) $\displaystyle\bar{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})$
$\displaystyle=R(s_{t},a_{t})+\sum_{a\in\mathcal{A}}\frac{N(s^{\prime})}{N(s_{t},a_{t})}\bar{V}^{N(s^{\prime})}(s^{\prime}).$
(257)

Firstly, we show that using a non-decaying search temperature with AR-BTS is
not guaranteed to recommend the optimal policy.

######  Proposition B.1.

For any $\alpha_{\textnormal{fix}}>0$, there is an MDP $\mathcal{M}$ such that
AR-BTS with $\alpha(m)=\alpha_{\textnormal{fix}}$ is not consistent:
$\mathbb{E}[\textnormal{reg}(s_{0},\psi^{n}_{\textnormal{AR-BTS}})]\not\to 0$
as $n\to\infty$.

###### Proof outline.

Consider the MDP given in Figure 34. We can show inductively that (as
$n\rightarrow\infty$) the value of $\mathbb{E}\bar{V}^{N(k)}(k)\leq
2E^{D-k+1}<2$, where $E=e^{2}/(1+e^{2})$ for $2\leq k\leq D$. The inductive
step is as follows:

$\displaystyle\mathbb{E}\bar{V}^{N(k)}(k)=$
$\displaystyle\frac{\exp\left(\bar{V}^{N(k+1)}(k+1)\right)}{1+\exp\left(\bar{V}^{N(k+1)}(k+1)\right)}\mathbb{E}\bar{V}^{N(k+1)}(k+1)+\frac{1}{1+\exp\left(\bar{V}^{N(k+1)}(k+1)\right)}\cdot
0$ (258) $\displaystyle\leq$ $\displaystyle
E\mathbb{E}\cdot\bar{V}^{N(k+1)}(k+1)$ (259) $\displaystyle\leq$
$\displaystyle E\cdot 2E^{D-k}$ (260) $\displaystyle=$ $\displaystyle
2E^{D-k+1}.$ (261)

where we know that
$\exp\left(\bar{V}^{N(k+1)}(k+1)\right)/\left(1+\exp\left(\bar{V}^{N(k+1)}(k+1)\right)\right)<E$,
because the function $e^{x}/(1+e^{x})$ is monotonically increasing in $x$, and
$\bar{V}^{N(k+1)}(k+1)<2$. Hence, by choosing an integer $D$ such that
$D-1\geq\log(1/3)/\log(E)$, we have $\mathbb{E}\bar{V}^{N(2)}(2)=2E^{D-1}\leq
2/3<1=\mathbb{E}\bar{Q}^{N(1,a_{2})}(1,a_{2})$.

A full proof should show that AR-BTS does indeed converge to these expected
values, possibly through concentration bounds.

Hence, AR-BTS does not converge to a simple regret of zero, because the
expected Q-values as $n\rightarrow\infty$ are
$\mathbb{E}\bar{Q}^{N(1,a_{2})}(1,a_{2})=1$ and
$\mathbb{E}\bar{Q}^{N(1,a_{1})}(1,a_{1})<2/3$, so AR-BTS would incorrectly
recommend action $a_{2}$ from the root node. ∎

Figure 34: An MDP that AR-BTS will not converge to recommending the optimal
policy on, for a large enough value of $D$.

Because the search temperature is now decayed, we need to show that the
exploration term in the search policies leads to actions being sampled
infinitely often.

######  Lemma E.20.

Let $\rho^{k}$ be an arbitrary policy, and let a search policy be
$\pi^{k}(a)=(1-\lambda(k))\rho^{k}(a)+\lambda(k)/|\mathcal{A}|$, with
$\lambda(k)=\min(1,\epsilon/\log(e+k))$, where $\epsilon\in(0,\infty)$. Let
$a^{k}\sim\pi^{k}$, and let $M(a)$ be the number of times action $a$ was
sampled out of $m$ samples, i.e. $M(a)=\sum_{i=1}^{m}\mathbbm{1}[a^{i}=a]$.
Then for all $a\in\mathcal{A}$ we have $M(a)\rightarrow\infty$ as
$m\rightarrow\infty$.

###### Proof outline.

This lemma restated means that our search policies will select all actions
infinitely often. To show this, we argue by contradiction, and suppose that
there is some $b\in\mathcal{A}$ such that after $\ell$ samples that $b$ is
never sampled again. The probability of this happening at the $m$th sample is
then:

$\displaystyle\Pr\left(\bigcap_{i=\ell}^{m}a^{i}\neq b\right)$
$\displaystyle=\prod_{i=\ell}^{m}\Pr(a^{i}\neq b)$ (262)
$\displaystyle\leq\prod_{i=\ell}^{m}\left(1-\frac{\epsilon}{|\mathcal{A}|\log(e+i)}\right)$
(263)
$\displaystyle\leq\left(1-\frac{\epsilon}{|\mathcal{A}|\log(e+m)}\right)^{m-\ell}$
(264) $\displaystyle\rightarrow 0,$ (265)

as $m\rightarrow\infty$. Which is a contradiction. ∎

######  Theorem B.2.

For any MDP $\mathcal{M}$, if $\alpha(m)\rightarrow 0$ as $m\rightarrow\infty$
then $\mathbb{E}[\textnormal{reg}(s_{0},\psi^{n}_{\textnormal{AR-
BTS}})]\rightarrow 0$ as $n\rightarrow\infty$, where $n$ is the number of
trials.

###### Proof outline.

We can argue that average returns converge in probability by induction similar
to the previous proofs. Suppose that
$\bar{Q}^{N(s_{t},a_{t})}(s_{t},a_{t})\overset{p}{\to}Q^{*}(s_{t},a_{t})$ as
$N(s_{t},a_{t})\rightarrow\infty$. From Lemma E.20, we know that if
$N(s_{t})\rightarrow\infty$, then $N(s_{t},a_{t})\rightarrow\infty$.

All that remains to show that
$\bar{V}^{N(s_{t})}(s_{t})\overset{p}{\to}V^{*}(s_{t})$ as
$N(s_{t})\rightarrow\infty$ is that
$\frac{N(s_{t},a)}{N(s_{t})}\rightarrow\mathbbm{1}[a=a^{*}]$. If that is true,
then by considering Equation (256), we can see that in the limit
$\bar{V}^{N(s_{t})}(s_{t})$ tends to $\bar{Q}^{N(s_{t},a*)}(s_{t},a*)$.

Intuitively we can see that
$\frac{N(s_{t},a)}{N(s_{t})}\rightarrow\mathbbm{1}[a=a^{*}]$ as the AR-BTS
search policy converges to a greedy policy as $\alpha(m)\rightarrow 0$. ∎

######  Theorem B.3.

For any MDP $\mathcal{M}$, if $\alpha(m)\rightarrow 0$ and
$\beta(m)\rightarrow 0$ as $m\rightarrow\infty$ then
$\mathbb{E}[\textnormal{reg}(s_{0},\psi^{n}_{\textnormal{AR-
DENTS}})]\rightarrow 0$ as $n\rightarrow\infty$, where $n$ is the number of
trials.

###### Proof outline.

Proof is similar to the proof for Theorem B.2. ∎

As a final note, using BTS or DENTS with a decaying search temperature
$\alpha(m)$ will lead to a consistent algorithm, although they would not admit
an exponential regret bound. Proofs would be nearly identical to Theorems B.2
and B.3.

plain mybib