# Demo Alleviate: Demonstrating Artificial Intelligence Enabled Virtual
Assistance for Telehealth: The Mental Health Case

Kaushik Roy, Vedant Khandelwal, Raxit Goswami, Nathan Dolbir, Jinendra
Malekar, Amit Sheth

###### Abstract

After the pandemic, artificial intelligence (AI) powered support for mental
health care has become increasingly important. The breadth and complexity of
significant challenges required to provide adequate care involve: (a)
Personalized patient understanding, (b) Safety-constrained and medically
validated chatbot patient interactions, and (c) Support for continued
feedback-based refinements in design using chatbot-patient interactions. We
propose Alleviate, a chatbot designed to assist patients suffering from mental
health challenges with personalized care and assist clinicians with
understanding their patients better. Alleviate draws from an array of publicly
available clinically valid mental-health texts and databases, allowing
Alleviate to make medically sound and informed decisions. In addition,
Alleviate’s modular design and explainable decision-making lends itself to
robust and continued feedback-based refinements to its design. In this paper,
we explain the different modules of Alleviate and submit a short video
demonstrating Alleviate’s capabilities to help patients and clinicians
understand each other better to facilitate optimal care strategies.

## Introduction

The current pandemic has over-extended mental healthcare systems and caused
striking increases in mental health clinical services(WHO 2022; WCVB 2020).
With the severe shortage of mental health clinicians coupled with a decrease
in in-person visits at health care facilities, AI-powered chatbots offer a
promising solution in helping patients mitigate mental health symptoms early
on through active self-care for effective prevention and intervention. The
current standard of chatbots provides script-based screening tasks (e.g.,
reminding, scheduling) that assist patients with mental health self-management
through chatbot-patient interactions for their daily self-care(Jaimini et al.
2018).

Enabling more advanced capabilities in chatbots raises challenging core
algorithmic issues on: (a) Personalized patient understanding, (b) Safety-
constrained and medically validated chatbot-patient interactions, and (c)
support for continued feedback-based refinements in design using chatbot-
patient and chatbot-clinician interactions.

We propose Alleviate, a chatbot designed to assist patients suffering from
mental health challenges with personalized care. Alleviate represents
personalized patient knowledge as a graph that integrates knowledge from an
array of clinically valid mental-health texts and databases with patient-
specific information derived from provider notes and patient-chatbot
interactions (see Figure 1 (a))(Cameron et al. 2015; Roy et al. 2021a; Rawte
et al. 2022; Lokala et al. 2021; Gaur et al. 2021). Furthermore, alleviate
operates in strict conformance with medically established guidelines ensuring
safe interactions with the patient. The breadth and depth of medical knowledge
consolidated in the knowledge graph enable Alleviate to make medically sound
and informed decisions (see Figure 1 (b))(Roy et al. 2022; Sheth et al. 2022;
Gupta et al. 2022). In addition, Alleviate’s modular design and explainable
reinforcement learning algorithms allow continued development and refinement
using user and clinician feedback (see Figure 1 (c))(Roy et al. 2021b). We
explain the inner workings of the Alleviate functions:

  * •

Safe and Explainable Medication Reminder and Troubleshooting.

  * •

Patient Appraisal on Adherence to Medical Recommendations.

  * •

Behavior Detection Requiring Emergency Human Intervention.

. The functions cover Alleviate’s aim to assist care providers with safe and
explainable personalized patient care.

Figure 1: (a) Alleviate constructs a consolidated knowledge base by drawing
from knowledge databases that are mental health domain specific - Eg: Suicide
and Depression Rating scales, broader medical context based - Eg: Medication
interactions and side-effects. Alleviate integrates the extracted knowledge
with patient-specific information to form a personalized patient knowledge
graph. (b) Alleviate’s task executions conform strictly to clinically
established safety standards and medical guidelines provided to Alleviate’s AI
backend in the form of knowledge graph path constraints. (c) Alleviate’s
algorithms support constant feedback-based refinements through continued
patient and care-provider interactions in a reinforcement learning setup.

## Safe and Explainable Medication Reminder and Troubleshooting

Alleviate extracts personalized patient information from provider notes and
past patient interactions using ¡subject, predicate, object¿ triple extraction
techniques to bootstrap the patient knowledge graph. Further, Alleviate
integrates patient information with mental health information from knowledge
bases by connecting the entities and relationships in the initialized patient
knowledge graph with similar entities in the knowledge bases. Computing dense
representation-based distances are used to determine similar entities.
Finally, alleviate resolves connection conflicts during integration using
clinician-specified guidelines for conflict resolution. Figure 2 Illustrates
how Alleviate can also construct potential hypotheses utilizing the
information from its knowledge sources (stored on a back-end server and not
visible to the user). Alleviate’s theories provide valuable insight to the
clinician care provider.

Figure 2: Alleviate integrates the user’s personal medication information and
the information contained in medical knowledge databases such as the mayo
clinic and the Unified Medical Language System (UMLS) to perform medication
inquiries and troubleshooting.

## Patient Appraisal on Adherence to Medical Recommendations

Alleviate’s patient knowledge graph is utilized to perform inquiries about
adherence to medical recommendations obtained from the provider notes written
by the care provider during offline patient-provider interactions. Figure 3
shows Alleviate praising a user for completing the recommended amount of
weekly exercise.

Figure 3: Alleviate praises the user for adherence to medical recommendations
contained in the provider notes written by the care provider. Here, Alleviate
appreciates the user accomplishing five days of exercise that week.

## Behavior Detection Requiring Emergency Human Intervention

Alleviate continuously performs safety checks to detect conversation patterns
that require emergency human intervention. Alleviate computes dense
representation similarities matching with concepts from clinically established
alarming behavior detection questionnaires represented as trees to determine
the time for emergency intervention.

Figure 4: Alleviate constantly monitors patient conversation for patterns
requiring emergency human intervention. Here, Alleviate alerts emergency
services of the patient’s potential suicidal ideation.

## Conclusion

In this work, we propose Alleviate, a mental health chatbot designed to assist
care providers with safe and explainable personalized patient care.
Alleviate’s integrated use of personal information, medical knowledge, and
mental-health questionnaires encoded as graphs and trees allow easy modeling
of safety conformance using graph and tree path constraints. The structure of
the graphs and trees enables explanation of Alleviate’s functions.

Acknowledgements: This research is supported by National Science Foundation
(NSF) Award # 2133842 “EAGER: Advancing Neuro-symbolic AI with Deep Knowledge-
infused Learning,” (Sheth et al. 2019). Any opinions, findings, and
conclusions or recommendations expressed in this material are those of the
author(s) and do not necessarily reflect the views of the NSF. We want to
extend our thanks to the team of Dr. Meera Narasimhan and
SHAIP111https://www.shaip.com222https://doctors.prismahealth.org/provider/Meera+Narasimhan/992922
for providing us the data which was used for experimentation purpose in the
proposed system.

## References

  * Cameron et al. (2015) Cameron, D.; Kavuluru, R.; Rindflesch, T. C.; Sheth, A. P.; Thirunarayan, K.; and Bodenreider, O. 2015.  Context-driven automatic subgraph creation for literature-based discovery.  _Journal of biomedical informatics_ , 54: 141–157.
  * Gaur et al. (2021) Gaur, M.; Roy, K.; Sharma, A.; Srivastava, B.; and Sheth, A. 2021.  “Who can help me?”: Knowledge Infused Matching of Support Seekers and Support Providers during COVID-19 on Reddit.  In _2021 IEEE 9th International Conference on Healthcare Informatics (ICHI)_ , 265–269. IEEE.
  * Gupta et al. (2022) Gupta, S.; Agarwal, A.; Gaur, M.; Roy, K.; Narayanan, V.; Kumaraguru, P.; and Sheth, A. 2022.  Learning to automate follow-up question generation using process knowledge for depression triage on reddit posts.  _arXiv preprint arXiv:2205.13884_.
  * Jaimini et al. (2018) Jaimini, U.; Thirunarayan, K.; Kalra, M.; Venkataraman, R.; Kadariya, D.; Sheth, A.; et al. 2018.  “How Is My Child’s Asthma?” digital phenotype and actionable insights for pediatric asthma.  _JMIR pediatrics and parenting_ , 1(2): e11988.
  * Lokala et al. (2021) Lokala, U.; Gaur, M.; Roy, K.; and Sheth, A. 2021.  Knowledge infused Natural Language understanding for Public Health, Epidemiology, and Substance Use.
  * Rawte et al. (2022) Rawte, V.; Chakraborty, M.; Roy, K.; Gaur, M.; Faldu, K.; Kikani, P.; Akbari, H.; and Sheth, A. 2022.  TDLR: Top (Semantic)-Down (Syntactic) Language Representation.  _UMBC Faculty Collection_.
  * Roy et al. (2022) Roy, K.; Gaur, M.; Zhang, Q.; and Sheth, A. 2022.  Process Knowledge-infused Learning for Suicidality Assessment on Social Media.  _arXiv preprint arXiv:2204.12560_.
  * Roy et al. (2021a) Roy, K.; Lokala, U.; Khandelwal, V.; and Sheth, A. 2021a.  ” Is depression related to cannabis?”: A knowledge-infused model for Entity and Relation Extraction with Limited Supervision.  _arXiv preprint arXiv:2102.01222_.
  * Roy et al. (2021b) Roy, K.; Zhang, Q.; Gaur, M.; and Sheth, A. 2021b.  Knowledge infused policy gradients with upper confidence bound for relational bandits.  In _Machine Learning and Knowledge Discovery in Databases. Research Track: European Conference, ECML PKDD 2021, Bilbao, Spain, September 13–17, 2021, Proceedings, Part I 21_ , 35–50. Springer.
  * Sheth et al. (2019) Sheth, A.; Gaur, M.; Kursuncu, U.; and Wickramarachchi, R. 2019.  Shades of knowledge-infused learning for enhancing deep learning.  _IEEE Internet Computing_ , 23(6): 54–63.
  * Sheth et al. (2022) Sheth, A.; Gaur, M.; Roy, K.; Venkataraman, R.; and Khandelwal, V. 2022.  Process Knowledge-Infused AI: Toward User-Level Explainability, Interpretability, and Safety.  _IEEE Internet Computing_ , 26(5): 76–84.
  * WCVB (2020) WCVB. 2020.  40% of US adults reported struggling with mental health or substance abuse, according to June CDC survey.  http://bit.ly/news˙mental˙health.  Accessed: 2022-12-10.
  * WHO (2022) WHO. 2022.  Covid-19 pandemic triggers 25% increase in prevalence of anxiety and depression worldwide.  https://www.who.int/news/item/02-03-2022-covid-19-pandemic-triggers-25-increase-in-prevalence-of-anxiety-and-depression-worldwide.  (Accessed on 11/01/2022).


# An Evaluation Benchmark for Autoformalization in Lean4

Aryan Gulati*, Devanshu Ladsaria*, Shubhra Mishra*, Jasdeep Sidhu*, Brando
Miranda
Department of Computer Science
Stanford University
Stanford, CA 94305
{aryangul, devanshu, shubhra, jasdeep6<EMAIL_ADDRESS>

###### Abstract

Large Language Models (LLMs) hold the potential to revolutionize
autoformalization. The introduction of Lean4, a mathematical programming
language, presents an unprecedented opportunity to rigorously assess the
autoformalization capabilities of LLMs. This paper introduces a novel
evaluation benchmark designed for Lean4, applying it to test the abilities of
state-of-the-art LLMs, including GPT-3.5, GPT-4, and Gemini Pro. Our
comprehensive analysis reveals that, despite recent advancements, these LLMs
still exhibit limitations in autoformalization, particularly in more complex
areas of mathematics. These findings underscore the need for further
development in LLMs to fully harness their potential in scientific research
and development. This study not only benchmarks current LLM capabilities but
also sets the stage for future enhancements in autoformalization.

**footnotetext: These authors contributed equally to this work

Benchmark Page: HuggingFace

##  1 Introduction

Generating formal statements is tedious, but the impressive advances in LLMs’
capabilities show a promising future for autoformalized, verifiable systems
(Klein et al., 2018). Computer-formalized mathematics has seen advances in
many directions, including the rapid development of new computer-interpretable
mathematical languages. One such language is Lean4, the non backwards-
compatible successor to Lean3. Given the differences between the two
languages, a benchmark that evaluates a LLM’s ability to autoformalize into
Lean4 has become increasingly important.

Contribution: In this paper, we propose a benchmark of 101 pairs of
mathematical formal-informal statements across 17 different topics in math.
Then, we manually evaluated three different state of the art LLMs (GPT-3.5,
GPT-4, and Gemini Pro) on the benchmark.

Many benchmarks have used the perplexity metric to evaluate autoformalizations
(OpenAI, ; Azerbayev et al., 2023). However, this relies on string/pattern
matching, which is not a very robust measure of autoformalization, given the
fact that LMs may generate correct formalizations that differ in structure or
wording. In our paper, we evaluate autoformalizations on a 0-4 scale based on
correction effort, as proposed in (Jiang et al., 2023). Correction effort
refers to the amount of necessary adjustments or modifications required to
transform the generated formalization output of a LLM into an accurate and
fully correct Lean4 formalization. Additionally, we split the statements into
math topics, which lets our evaluation extend beyond an accuracy metric,
providing a more fine-grained understanding of how LLMs autoformalize, and
where more work is still needed.

##  2 Methodology and Results

To assess the autoformalization capabilities of contemporary LLMs, we selected
a dataset of 101 theorem statements from mathlib4, a comprehensive library of
mathematical theorems formulated in Lean4. The dataset included a wide array
of mathematical subjects (Appendix B) ensuring a diverse and representative
sample for our analysis. The dataset includes formal statements, their
corresponding natural language informalizations, and the specific mathematical
topic.

We employed a zero-shot prompting approach with three advanced LLMs: GPT-3.5,
GPT-4, and Gemini Pro. This approach involved presenting each model with
natural language statements from our dataset and analyzing the formalized
outputs they generated (Appendix C). We also streamlined the evaluation
process by trimming outputs to only include formal Lean statements.

Our evaluation methodology drew inspiration from (Jiang et al., 2023),
employing a grading scale ranging from 0 to 4. On this scale, a score of 0
indicates a flawless autoformalization, while a score of 4 signifies an output
requiring as much correction effort as formalizing a statement from scratch.

Our analysis revealed that the correction efforts for autoformalizations were
similar among GPT-3.5 and GPT-4, averaging 2.238. Gemini Pro showed a slightly
higher average effort of 2.248. Gemini Pro boasts the most number of
autoformalizations with scores of 0s and 1s. However despite this, GPT-4 and
Gemini Pro produced more instances with the maximum correction effort of 4
(Appendix D). This is likely because as discussed in (Pichai & Hassabis,
2023), Gemini, with its natively multi-modal design and recent training
incorporating Lean4 data, performs better in reasoning tasks. This is a step
forward from GPT-4’s Mixture of Experts (MoE) design and earlier training
phase, which may have had less exposure to Lean4 (as evident from GPT-4’s
misinterpretation of Lean4 capabilities in Appendix C). Both models surpass
GPT-3.5, which relies on a monolithic architecture.

Figure 1 reveals performance disparities among LLMs across mathematical
subjects, which suggests that the LLMs’ performance is subject-dependent. For
instance, all LLMs excelled in Information Theory and Logic, but had trouble
with category and model theory. We hypothesize that the frequency of these
subjects on the internet is related to the performance of the LLM. Another
potential reason for the discrepancy between subjects might be attributed to
the difficulties of autoformalization. Problems in category theory and model
theory are harder to describe even in natural language, so translating it to
formal language is a more difficult task in itself. To improve our dataset, we
could label the difficulty of each problem statement to correct for
correlation between problem- and autoformalization-difficulty. The overall
variance suggests that the LLMs’ performance is influenced by the subject
matter of the theorem, pointing to potential avenues for future research.

Figure 1: Average Correction Efforts Across Topics

##  3 Conclusion

Our research underscores the potential of LLMs in revolutionizing the field of
formalization, with implications extending across mathematics, computer
science, and engineering. While LLMs can substantially expedite research and
development, our findings indicate that even the most sophisticated models
currently fall short in achieving accurate autoformalization. This gap
highlights the unique opportunity presented by the development of Lean4,
serving as a crucial testing ground for enhancing LLM performance in
autoformalization and automated theorem proving.

### URM Statement

We acknowledge that all the authors of this work meets the URM criteria of
ICLR 2024 Tiny Papers Track.

## References

  * Azerbayev et al. (2023) Zhangir Azerbayev, Bartosz Piotrowski, Hailey Schoelkopf, Edward W. Ayers, Dragomir Radev, and Jeremy Avigad.  Proofnet: Autoformalizing and formally proving undergraduate-level mathematics.  2023\.
  * Jiang et al. (2023) Albert Jiang, Wenda Li, and Mateja Jammik.  Multilingual mathematical autoformalization, 2023.
  * Klein et al. (2018) Gerwin Klein, June Andronick, Matthew Fernandez, Ihor Kuz, Toby Murray, and Gernot Heiser.  Formally verified software in the real world.  _Commun. ACM_ , 61(10):68–77, sep 2018.  ISSN 0001-0782.  doi: 10.1145/3230627.  URL https://doi.org/10.1145/3230627.
  * (4) OpenAI.  MiniF2F benchmark.  URL https://github.com/openai/miniF2F/tree/main.
  * Pichai & Hassabis (2023) Sundar Pichai and Demis Hassabis.  Introducing gemini: Our largest and most capable ai model, Dec 2023.  URL https://blog.google/technology/ai/google-gemini-ai/#sundar-note.

##  Appendix A Dataset

The evaluation benchmark can be accessed via HuggingFace here.

##  Appendix B Inside the Dataset

Topic | Number of problems
---|---
Algebra | 9
Analysis | 8
Category Theory | 6
Combinatorics | 6
Computability | 4
Field Theory | 9
Geometry | 8
Group Theory | 6
Info. Theory | 5
Linear Algebra | 5
Logic | 5
Model Theory | 6
Number Theory | 5
Probability | 6
Rep. Theory | 3
Set Theory | 5
Topology | 5
Table 1: The Number of Problems in the Dataset, Based on Topic

##  Appendix C Sample Prompts and Outputs

⬇

Prompt:

"I am providing you with a mathematical statement

in natural language. I want you to formalize it in the Lean4

language. \n" + natural_language_statement

Output:

{

"id": 8,

"subject": "Information Theory",

"natural_language_statement": "The Hamming distance of an element to itself is
always 0.",

"ground_truth_formalization": "theorem hammingDist_self (x : $\forall$ i,
$\beta$ i) : hammingDist x x = 0 := by%n rw [hammingDist, card_eq_zero,
filter_eq_empty_iff]%n exact fun _ _ H => H rfl%n#align hamming_dist_self
hammingDist_self",

"gpt_3.5_turbo_response": "import data.list.basic%n%nopen list%n%n\-- Define
the Hamming distance function%ndef hamming_distance {$\alpha$ : Type}
[decidable_eq $\alpha$] (xs ys : list $\alpha$) : $\mathbb{N}$ :=%n (xs.zip
ys).count ($\lambda$ xy, xy.fst \neq xy.snd)%n%n\-- Formalize the
statement%ntheorem hamming_distance_self_zero {$\alpha$ : Type} [decidable_eq
\alpha] (x : $\alpha$) :%n hamming_distance [x] [x] = 0 :=%nbegin%n \-- Apply
the definition of hamming_distance%n unfold hamming_distance,%n \-- Simplify
the expression%n simp,%nend",

"gpt_4_response": "In Lean4, the Hamming distance of an element to itself
being always 0 can be formalized as follows:%n%n‘‘‘lean%nimport data.nat.basic
\-- import necessary library%n%ndef hamming_distance (x y : $\mathbb{N}$) :
$\mathbb{N}$ :=%n nat.popcount (x lxor y) \-- definition of Hamming
distance%n%ntheorem hamming_self (n : $\mathbb{N}$) : hamming_distance n n = 0
:=%nbegin%n rw hamming_distance,%n rw nat.lxor_self,%n exact
nat.popcount_zero,%nend%n‘‘‘%n%n. This code first imports the necessary
library for natural numbers. Then it defines the Hamming distance as the
population count (number of 1’s) in the binary representation of the bitwise
exclusive or (lxor) of two numbers. The theorem ‘hamming_self‘ states that the
Hamming distance of a number to itself is always 0. The proof is
straightforward: the bitwise exclusive or of a number with itself is always 0,
and the population count of 0 is 0.",

"gemini_pro_response": "theorem hamming_distance_to_self_is_zero ($\alpha$ :
Type) [decidable_eq \alpha] (x : $\alpha$) :%n hamming_distance x x = 0 :%n by
refl"

}

Scores given to Problem 8: GPT-3.5 - 1. GPT-4 - 1. Gemini Pro - 1. All
autoformalizations were near perfect with minor changes necessary, which led
us to giving scores of 1 for all models.

Output:

{

"id": 99,

"subject": "Category Theory",

"natural_language_statement": "An object is injective if its preadditive
Yoneda functor preserves finite colimits.",

"ground_truth_formalization": "theorem
injective_of_preservesFiniteColimits_preadditiveYonedaObj (J : C)%n [hP :
PreservesFiniteColimits (preadditiveYonedaObj J)] : Injective J :=",

"gpt_3.5_turbo_response": "import category_theory.category%nimport
category_theory.functor%nimport category_theory.limits%n%nopen
category_theory%n%nuniverses v u%n%nvariables (C : Type u) [category.{v}
C]%n%nstructure injective_object (X : C) : Prop
:=%n(preadditive_yoneda_functor_preserves_colimits :%n $\forall$ (J : Type v)
[small_category J] (F : J $\rightarrow$ C),%n
limits.preserves_colimits_of_shape (discrete.functor F) (yoneda.obj
X))%n%nNote: This formalization assumes that Lean4 has already imported the
necessary libraries for category theory. The statement is formalized using the
‘injective_object‘ structure, which takes an object ‘X‘ in category ‘C‘ as a
parameter. The structure contains a property
‘preadditive_yoneda_functor_preserves_colimits‘, which asserts that for any
small category ‘J‘ and functor ‘F : J $\rightarrow$ C‘, the preadditive Yoneda
functor preserves finite colimits. The ‘limits.preserves_colimits_of_shape‘
function is used to express this preservation property.",

"gpt_4_response": "Formalizing this statement in Lean4 requires a deep
understanding of category theory and the Lean4 language. Unfortunately,
Lean4’s standard library does not currently support category theory to the
extent required to formalize this statement. %n%nHowever, here is a rough
sketch of how you might start to define these concepts in
Lean4:%n%n‘‘‘lean%n\-- First, we need to define what a category is%nstructure
Category :=%n (Obj : Type)%n (Hom : Obj $\rightarrow$ Obj $\rightarrow$
Type)%n (comp : $\Pi$ {X Y Z : Obj}, Hom X Y $\rightarrow$ Hom Y Z
$\rightarrow$ Hom X Z)%n (id : $\Pi$ X : Obj, Hom X X)%n (assoc : $\Pi$ {W X Y
Z : Obj} (f : Hom W X) (g : Hom X Y) (h : Hom Y Z),%n comp (comp f g) h = comp
f (comp g h))%n (id_left : $\Pi$ {X Y : Obj} (f : Hom X Y), comp (id X) f =
f)%n (id_right : $\Pi$ {X Y : Obj} (f : Hom X Y), comp f (id Y) = f)%n%n\--
Then, we need to define what a functor is%nstructure Functor (C D : Category)
:=%n (onObj : C.Obj $\rightarrow$ D.Obj)%n (onHom : $\Pi$ {X Y : C.Obj}, C.Hom
X Y $\rightarrow$ D.Hom (onObj X) (onObj Y))%n (functor_id : $\Pi$ {X :
C.Obj}, onHom (C.id X) = D.id (onObj X))%n (functor_comp : $\Pi$ {X Y Z :
C.Obj} (f : C.Hom X Y) (g : C.Hom Y Z),%n onHom (C.comp f g) = D.comp (onHom
f) (onHom g))%n%n\-- Then, we need to define what a preadditive category
is%nstructure Preadditive (C : Category) :=%n (add : $\Pi$ {X Y : C.Obj},
C.Hom X Y $\rightarrow$ C.Hom X Y $\rightarrow$ C.Hom X Y)%n (zero : $\Pi$ {X
Y : C.Obj}, C.Hom X Y)%n (neg : $\Pi$ {X Y : C.Obj}, C.Hom X Y $\rightarrow$
C.Hom X Y)%n (sub : $\Pi$ {X Y : C.Obj}, C.Hom X Y $\rightarrow$ C.Hom X Y
$\rightarrow$ C.Hom X Y)%n \-- plus the axioms for an additive group...%n%n\--
Then, we need to define what a Yoneda functor is%ndef Yoneda (C : Category) (X
: C.Obj) : Functor C (Preadditive C) := sorry%n%n\-- Then, we need to define
what a colimit is%ndef Colimit (F : Functor C D) : D.Obj := sorry%n%n\-- Then,
we need to define what it means for a functor to preserve colimits%ndef
PreservesColimits (F : Functor C D) : Prop :=%n $\forall$ (G : Functor C D) (c
: Colimit G), Colimit (Functor.comp F G) = F.onObj c%n%n\-- Finally, we can
define what it means for an object to be injective%ndef Injective (C :
Category) (X : C.Obj) : Prop :=%n PreservesColimits (Yoneda C
X)%n‘‘‘%n%nPlease note that this is a very rough sketch and is not complete or
correct Lean4 code. The definitions of ‘Yoneda‘, ‘Colimit‘, and
‘PreservesColimits‘ are particularly difficult and would require a lot of
additional code.",

"gemini_pro_response": "def injective [additive] (C : Category) : Prop :=
$\forall$ (F : Functor C^{op} $\rightarrow$ Ab) (X : C),
preserves_finite_colimits F $\leftrightarrow$ preserves_finite_colimits
(Yoneda.obj C X) $\cong$ F"

}

Scores given to Problem 99: GPT-3.5 - 2. GPT-4 - 3. Gemini Pro - 2. GPT 4
avoided a direct autoformalization and proceeded to define other concepts in
category theory giving it a score of 3. GPT 3.5 however, attempted a direct
autoformalization with Lean4 syntax and provided partially sound logic
warranting a score of 2. Bard, similar to GPT 3.5, provided a partially
correct direct autoformalization with Lean4 syntax warranting a score of 2.

##  Appendix D Graphing the Correction Effort for Separate Models

01234$10$$20$$30$Correction EffortCountsAutoformalizing to Lean4 with GPT
3.501234$0$$10$$20$$30$Correction EffortCountsAutoformalizing to Lean4 with
GPT 4

01234$10$$20$$30$Correction EffortCountsAutoformalizing to Lean4 with Gemini
Pro


11institutetext: Instituto Superior Técnico, University of Lisbon, Portugal
22institutetext: INESC-ID, Lisbon, Portugal

# Limited depth bandit-based strategy for Monte Carlo planning in continuous
action spaces

Ricardo Quinteiro 11 Francisco S. Melo 1122 Pedro A. Santos 1122

###### Abstract

This paper addresses the problem of optimal control using search trees. We
start by considering multi-armed bandit problems with continuous action spaces
and propose LD-HOO, a limited depth variant of the hierarchical optimistic
optimization (HOO) algorithm. We provide a regret analysis for LD-HOO and show
that, asymptotically, our algorithm exhibits the same cumulative regret as the
original HOO while being faster and more memory efficient. We then propose a
Monte Carlo tree search algorithm based on LD-HOO for optimal control problems
and illustrate the resulting approach’s application in several optimal control
problems.

###### Abstract

This appendix includes a detailed proof for Theorem 3.1, establishing an
asymptotic regret bound for LD-HOO.

###### Keywords:

Multiarmed bandits Monte Carlo tree search Planning in continuous action space

##  1 Introduction

Recent years have witnessed remarkable successes of artificial intelligence,
brought about by the effective combination of powerful machine learning
algorithms based on neural networks and efficient planning approaches based on
Monte Carlo tree search. Perhaps the most celebrated is AlphaGo and its
successors [15, 17, 16, 14], which could attain super-human proficiency in
several complex games such as chess, Go, or Shogi. Even before AlphaGo, Monte
Carlo tree search approaches were already widely used in complex planning
problems due to their efficiency, mild requirements, and robust theoretical
guarantees [3] .

Monte Carlo tree search (MCTS) is a family of online planning methods
initially designed to solve sequential decision problems such as Markov
decision problems [7, 6]. At each step $t$, the decision-maker builds a search
tree with its current state, $s_{t}$, as the root node. Its children
correspond to the actions available to the agent at $s_{t}$, and the algorithm
proceeds by estimating a value for each such action by using rollouts and
efficient exploration. Rollouts provide empirical estimates for the nodes’
values in the tree, while efficient exploration directs tree expansion towards
the more promising regions of the state space (see Fig. 1 for an
illustration).

Figure 1: Illustration of MCTS. An adequate exploration policy is used to
determine the next node selected for expansion. Rollouts (i.e., sampled
trajectories) from the expanded nodes are used to build estimates about how
good the nodes are.

In this paper, we extend the idea behind MCTS to control problems with a
continuous action space. The main challenge lies in ensuring efficient
exploration. Standard MCTS approaches assume that the decision-maker has only
a finite set of possible actions available and typically use multi-armed
bandit algorithms to guide exploration. Hence, our first contribution is a
novel multi-armed bandit algorithm for continuous action spaces.

Several works have addressed multi-armed bandits with continuous action spaces
[11]. Most such approaches consider an action space that corresponds to a
hypercube in $\mathds{R}^{P}$, i.e., a set

$\mathcal{X}=\prod_{p=1}^{P}[a_{p},b_{p}],\qquad\text{for
$a_{p},b_{p}\in\mathds{R}^{P}$.}$

Multi-armed bandit problems in continuous action settings generally apply some
form of hierarchical partitioning [11]. Hierarchical partitioning successively
splits $\mathcal{X}$ into smaller hypercubes in such a way that the resulting
partition can be represented as a tree (see Fig. 2). Examples of such
algorithms include deterministic optimistic optimization (DOO) [10],
hierarchical optimistic optimization (HOO) [5], stochastic simultaneous
optimistic optimization (StoSOO) [11], truncated hierarchical optimistic
optimization (T-HOO) [4], or polynomial hierarchical optimistic optimization
(Poly-HOO) [9].

Figure 2: Hierarchical partitioning. The set $\mathcal{X}$ is successively
split in uniform subsets, and the resulting partition can be represented as a
$K$-ary tree. The sets in level $h$ are referred as “cells” and denoted as
$\mathcal{X}_{h,i}$, with $0\leq i\leq K^{h}-1$. Each set $\mathcal{X}_{h,i}$
is represented by a specific element $x_{h,i}$, referred as the center of
$\mathcal{X}_{h,i}$.

All the methods above also build on the principle of optimism in the face of
uncertainty, widely used in the multi-armed bandit literature [1] and MCTS.
The most adequate for the settings considered in this paper are HOO and its
truncated and polynomial variants. Unlike DOO, HOO admits stochastic rewards.
Unlike StoSOO, it is an anytime algorithm, a desirable property when used
within MCTS. Unfortunately, HOO exhibits quadratic runtime, which is
inconvenient for MCTS. Poly-HOO and T-HOO are faster, but exhibit a worse
performance in terms of cumulative regret.

This paper contributes LD-HOO, a modified version of HOO that is
computationally faster but retains HOO’s guarantees in terms of cumulative
regret. We also contribute an analysis of LD-HOO in terms of cumulative
regret. Finally, we propose LD-HOOT (LD-HOO for trees), a novel MCTS algorithm
for problems with continuous action spaces that uses LD-HOO for efficient
exploration. We illustrate the application of LD-HOOT in several well-known
optimal control problems.

##  2 Background

This section provides an overview of key concepts regarding the decision
problems addressed in this paper and sets the notation used throughout.

###  2.1 The (stochastic) multi-armed bandit problem

We consider the problem of a decision maker that must, at each time step
$t=1,2,\ldots$, select a (possibly random) action $X_{t}$ from a set
$\mathcal{X}$ of possible actions. Upon selecting an action $X_{t}=x$, the
decision maker receives a (possibly random) reward $Y_{t}$ with mean value
$f(x)$. The process then repeats.

We assume that $Y_{t}\in[0,1]$ and the distribution governing $Y_{t}$ is
stationary and independent of the past given the action $X_{t}$. The function
$f:\mathcal{X}\to\mathds{R}$ is unknown to the decision maker. The goal of the
decision maker is to select the actions $X_{t},t=1,2,\ldots$, to maximize the
total reward received.

A policy is a sequence $\pi=\left\\{\pi_{t},\;t=1,2,\ldots\right\\}$, where
each $\pi_{t}$ maps the history of the agent up to time step $t$ to a
distribution over $\mathcal{X}$. The cumulative regret of a policy $\pi$ at
time step $n$ is defined as

$\hat{R}_{n}=nf(x^{*})-\sum_{t=1}^{n}Y_{t},$

where $x^{*}=\operatorname*{\mathrm{argmax}}_{x\in\mathcal{X}}f(x)$, and the
cumulative pseudo-regret is

$R_{n}=nf(x^{*})-\sum_{t=1}^{n}f(x_{t}).$

The cumulative regret measures how much the agent’s policy lost in terms of
cumulative reward compared with the optimal action.

###  2.2 Markov decision problems

Markov decision problems (MDPs) extend multi-armed bandit problems by
considering that the reward at each time step $t$, $Y_{t}$, is no longer
independent of the past given only the action $X_{t}$. In an MDP, a decision-
maker observes, at each time step $t=1,2,\ldots$, the state of a Markov chain
$\left\\{S_{t},t=1,2,\ldots\right\\}$, where each $S_{t}$ takes values in some
set $\mathcal{S}$. It must then select a (possibly random) action $X_{t}$ from
a set $\mathcal{X}$ of possible actions. Upon selecting an action $X_{t}=x$
when the chain is in state $S_{t}=s$, the decision maker receives a (possibly
random) reward $Y_{t}$ with mean value $f(s,x)$. The Markov chain then
transitions to a new state $S_{t+1}=s^{\prime}$ according to the transition
probabilities

$P(s,x,s^{\prime})=\mathbb{P}\left[S_{t+1}=s^{\prime}\mid
S_{t}=s,X_{t}=x\right].$

As before, we assume that the distribution governing $Y_{t}$ is stationary and
independent of the past given $X_{t}$ and $S_{t}$. As before, the function $f$
is unknown to the learner. The goal of the decision maker is to select the
actions $X_{t},t=1,\ldots$, to maximize the value

$J=\mathbb{E}\left[\sum_{t=1}^{\infty}\gamma^{t-1}f(S_{t},X_{t})\right],$ (1)

where $\gamma$ is a discount factor. MDPs are stochastic optimal control
problems and find many applications in artificial intelligence, operations
research and optimal control [13].

##  3 Limited Depth Hierarchical Optimistic Optimization

This section introduces our first contribution, the LD-HOO algorithm. In terms
of structure, LD-HOO is similar to HOO [5]. LD-HOO also uses hierarchical
partitioning to successively build a binary tree like the one depicted in Fig.
2. The key difference is that, in LD-HOO, the depth of the tree depth is
limited to a maximum depth, $\hat{H}$. By limiting the tree’s depth, we
introduce significant computational savings without sacrificing performance.

At a very high-level, LD-HOO proceeds as follows. At each time step $t$, LD-
HOO navigates the current partition tree, $\mathcal{T}_{t}$, from the root to
some leaf node $X_{h_{t},i_{t}}$ using an “optimistic” path (we make this
notion precise ahead). It then selects an arbitrary action $x_{t}\in
X_{h_{t},i_{t}}$ and observes the corresponding reward, $y_{t}$. If
$h_{t}<\hat{H}$ the node $X_{h_{t},i_{t}}$ is expanded—i.e., its children
nodes are added to the tree. Finally, the value of the nodes in the tree is
updated accordingly.

To properly formalize the LD-HOO algorithm, we introduce some auxiliary
notation. We denote by $\mathcal{T}_{t}$ the partition tree at time step $t$.
The sets at each level $h$ of the tree are generally referred as “cells”, and
denoted as $\mathcal{X}_{h,i}$, with $0\leq i\leq 2^{h}-1$. Each cell
$\mathcal{X}_{h,i}$ originates, in level $h+1$, two children cells,
$\mathcal{X}_{h+1,2i-1}$ and $\mathcal{X}_{h+1,2i}$. We denote by
$\mathcal{C}(h,i)$ the children of $\mathcal{X}_{h,i}$, i.e.,

$\mathcal{C}(h,i)=\left\\{(h+1,2i-1),(h+1,2i)\right\\},$

and by

$T_{h,i}(t)=\sum_{\tau=1}^{t}\mathbb{I}\left[X_{\tau}\in\mathcal{X}_{h,i}\right]$

the number of times that an action from $\mathcal{X}_{h,i}$ was selected up to
time step $t$. The estimated reward associated with a node $(h,i)$ at time
step $t$ can be computed as

$\hat{\mu}_{h,i}(t)=\frac{1}{T_{h,i}(t)}\sum_{\tau=1}^{t}y_{\tau}\mathbb{I}\left[X_{\tau}\in\mathcal{X}_{h,i}\right].$

Finally, we write $\mathcal{L}(\mathcal{T}_{t})$ to denote the set of leaf
nodes of the tree $\mathcal{T}_{t}$.

The “optimism in the face of uncertainty” principle comes into play by
associating, with each node $(h,i)$ in the tree, an upper confidence bound
$b_{h,i}$ that is used to guide the traversal of the tree. The computation of
this upper confidence bound relies on two key assumptions.

The first assumption concerns the existence of a semi-metric in $\mathcal{X}$.

######  Assumption 1.

The action space $\mathcal{X}$ is equipped with a semi-metric
${\ell\\!:\mathcal{X}\\!\times\\!\mathcal{X}\\!\to\\!\mathds{R}}$.

Recall that $\ell$ is a semi-metric if, for all $x,x^{\prime}\in\mathcal{X}$,
$\ell(x,x^{\prime})\geq 0$, $\ell(x,x^{\prime})=\ell(x^{\prime},x)$ and
$\ell(x,x^{\prime})=0$ if and only if $x=x^{\prime}$. We can now define the
diameter of a set $U\subset\mathcal{X}$ as

$\operatorname{\mathrm{diam}}(U)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\sup_{x,x^{\prime}\in
U}\ell(x,x^{\prime}).$

An $\ell$-open ball centered around $x\in\mathcal{X}$ with radius
$\varepsilon$ is defined as

$\mathcal{B}(x,\varepsilon)\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\left\\{x^{\prime}\in\mathcal{X}\mid\ell(x,x^{\prime})<\varepsilon\right\\}.$

The second assumption is concerned with hierarchical partitioning.

######  Assumption 2.

There are constants $\nu_{1},\nu_{2}>0$ and $0<\rho<1$ such that, for all
$h\geq 0$ and all $i\in\left\\{0,\ldots,2^{h}-1\right\\}$, there is
$x_{h,i}\in\mathcal{X}_{h,i}$ such that

$\displaystyle\operatorname{\mathrm{diam}}(\mathcal{X}_{h,i})\leq\nu_{1}\rho^{h},$
$\displaystyle\mathcal{B}(x_{h,i},\nu_{2}\rho^{h})\subset\mathcal{X}_{h,i},$
$\displaystyle\mathcal{B}(x_{h,i},\nu_{2}\rho^{h})\cap\mathcal{B}(x_{h,j},\nu_{2}\rho^{h})=\emptyset,\qquad\text{for
$i\neq j$.}$

Assumption 2 ensures that the construction of the hierarchical partition and
the semi-metric $\ell$ are such that the diameter of the cells in level $h$
decreases uniformly, and a suitable center can be found for each cell. The
choice of partitioning method thus suggests a semi-metric, while the choice of
$\ell$ limits the way that the partition can be done [4].

From the above assumptions we can now compute an upper confidence bound for
the values of $f$ in a cell $(h,i)$ of the tree at time step $t$ as

$u_{h,i}(t)=\hat{\mu}_{h,i}(t)+\sqrt{\frac{2\log
t}{T_{h,i}(t)}}+\nu_{1}\rho^{h},$ (2)

where $\nu_{1}$ and $\rho$ are the constants from Assumption 2. It is
interesting to note the similarity between the bound in (2) and the upper
confidence bound in the well-known UCB1 algorithm [1]. The additional term,
$\nu_{1}\rho^{h}$, accounts for the variation of $f$ within
$\mathcal{X}_{h,i}$.

The actual value used to traverse the tree is referred as the $b$-value, and
is computed from the upper confidence bound in (2) as

$b_{h,i}(t)=\min\left\\{u_{h,i}(t),\max_{c\in\mathcal{C}(h,i)}b_{c}(t)\right\\},$
(3)

where the $b$-value of a non-visited node is set to $+\infty$. These values
can be computed recursively from the leaves to the root.

Algorithm 1 Limited Depth Hierarchical Optimistic Optimization (LD-HOO).

1:Initialization:

2:$\mathcal{T}_{1}=\\{(0,0)\\}$

3:$u_{0,0}\leftarrow+\infty$

4:$b_{0,0}\leftarrow+\infty$

5:

6:Main loop:

7:for $t=1,\ldots,n$ do

8: Compute $b$-values for all nodes in $\mathcal{T}_{t}$ using (3)

9: Set $(h,i)=(0,0)$ $\triangleright$ Start in the root node

10: while $(h,i)\not\in\mathcal{L}(\mathcal{T}_{t})$ do

11:
$(h,i)\leftarrow\operatorname*{\mathrm{argmax}}_{c\in\mathcal{C}(h,i)}b_{c}(t)$
$\triangleright$ Traverse tree “optimistically”

12: end while

13: $(h_{t},i_{t})\leftarrow(h,i)$ $\triangleright$ Node selection

14: Sample action $x_{t}$ arbitrarily from $\mathcal{X}_{h_{t},i_{t}}$
$\triangleright$ Action sampling

15: Observe reward $y_{t}$

16: if $h<\hat{H}$ then

17: $\mathcal{T}_{t+1}=\mathcal{T}_{t}\cup\mathcal{C}(h_{t},i_{t})$
$\triangleright$ Expand node $(h_{t},i_{t})$

18: end if

19:end for

20:

21:Final action selection:

22:Return $x_{n}\in\mathcal{X}_{h^{*}_{n},i^{*}_{n}}$

LD-HOO is summarized in Algorithm 1 for a horizon of $n$ steps. Lines 9-12
correspond to the traversal of the partition tree: at node $(h,i)$, the
algorithm moves to the child of $(h,i)$ with the largest $b$-value. The
traversal stops at a leaf node $(h_{t},i_{t})$ (line 13) and an action is then
selected from $\mathcal{X}_{h_{t},i_{t}}$. Then, if $h_{t}$ is below the limit
depth $\hat{H}$, the node $(h_{t},i_{t})$ is expanded and its children added
to the tree (lines 16-18). Finally, upon completion, the algorithm returns an
action $x_{n}$ from $\mathcal{X}_{h^{*}_{n},i^{*}_{n}}$ where

$(h^{*}_{n},i^{*}_{n})=\operatorname*{\mathrm{argmax}}_{c\in\mathcal{T}_{n}}\hat{\mu}_{c}(n).$

###  3.1 Regret analysis for LD-HOO

In this section we provide a regret analysis for LD-HOO. Our analysis closely
follows that of Bubeck et al. [4], adapted to take into consideration the fact
that LD-HOO considers limited-depth partition trees.

Our analysis requires one additional assumption regarding the behavior of the
mean payoff function, $f$, around its global maximizer, $x^{*}$.

######  Assumption 3.

The mean payoff function, $f$, is such that, for all
$x,x^{\prime}\in\mathcal{X}$,

$f(x^{*})-f(x^{\prime})\leq
f(x^{*})-f(x)+\max\left\\{f(x^{*})-f(x),\ell(x,x^{\prime})\right\\}.$

Assumption 3 states that there is no sudden decrease in the mean payoff
function around $x^{*}$. Also, setting $x=x^{*}$, Assumption 3 actually
establishes $f$ as locally Lipschitz around $x^{*}$ [5]. The set of
$\varepsilon$-optimal actions, $\mathcal{X}_{\varepsilon}$, is defined as

$\mathcal{X}_{\varepsilon}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\left\\{x\in\mathcal{X}\mid
f(x)\geq f(x^{*})-\varepsilon\right\\}.$

We have the following definition.

######  Definition 1 ($\varepsilon$-packing number).

Given a set $\mathcal{X}$ with a semi-metric $\ell$, the $\varepsilon$-packing
number of $\mathcal{X}$ with respect to $\ell$ is denoted as
$\mathcal{N}(\mathcal{X},\ell,\varepsilon)$ and defined as the largest integer
$K$ for which there are $x_{1},\ldots,x_{K}\in\mathcal{X}$ such that
$\mathcal{B}(x_{k},\varepsilon)\subset\mathcal{X}$ and
$\mathcal{B}(x_{k},\varepsilon)\cap\mathcal{B}(x_{k^{\prime}},\varepsilon)=\emptyset$,
for all $k,k^{\prime}\in\left\\{1,\ldots,K\right\\}$.

In other words, $\mathcal{N}(\mathcal{X},\ell,\varepsilon)$ is the maximum
number of disjoint $\varepsilon$-balls contained in $\mathcal{X}$. We now
introduce the notion of near-optimality dimension, which describes the size of
the sets $\mathcal{X}_{c\varepsilon}$ as a function of $\varepsilon$.

######  Definition 2 (Near-optimality dimension).

Given constants $c>0$ and $\varepsilon_{0}>0$, the $(c,\varepsilon_{0})$-near-
optimality dimension of $f$ with respect to $\ell$ is defined as

$d\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\inf\left\\{\delta\geq
0\mid\exists C>0\text{ s.t.
}\forall\varepsilon\leq\varepsilon_{0},\mathcal{N}(\mathcal{X}_{c\varepsilon},\ell,\varepsilon)\leq
C\varepsilon^{-\delta}\right\\},$

with the convention that $\inf\emptyset=+\infty$.

In other words $d$ is the smallest value such that the maximum number of
disjoint $\varepsilon$-balls that “fit” in $\mathcal{X}_{c\varepsilon}$ is no
larger than a $C\varepsilon^{-d}$. A small near-optimality dimension implies
that there is a small number of neighborhoods where the value of $f$ is close
to its maximum.

We now introduce our main result.

######  Theorem 3.1.

Suppose that Assumptions 1 through 3 are satisfied for semi-metric $\ell$ and
constants $\nu_{1}$, $\nu_{2}$ and $\rho$. Let $d<+\infty$ be the
$(4\nu_{1}/\nu_{2},\nu_{2})$-near-optimality dimension of $f$ with respect to
$\ell$. Then, for all horizons $n>0$ and depth limit $\hat{H}>0$, the expected
cumulative regret of LD-HOO verifies:

$\mathbb{E}\left[R_{n}\right]\in
O\left(\rho^{\hat{H}}n+\rho^{-\hat{H}(d+1)}\log
n+\hat{H}\max\\{\rho^{\hat{H}(1-d)},\hat{H}\\}\right).$

Due to space limitations, we provide only a sketch of the proof, and refer to
the supplementary material for a complete proof.

###### Proof sketch.

The proof proceeds in four steps. We start by providing a bound on the number
of times that each “suboptimal” node in the tree is selected. In a second step
we break down the value of $\mathbb{E}\left[R_{n}\right]$ into three
components. In the third step we show that two of the regret components are
naturally bounded as a consequence of our assumptions, and the third depends
on the number of visits to the nodes in the tree (which was bounded in the
first step). The fourth step wraps the proof by combining the intermediate
results into a final regret bound.

#### First step.

For a node $(h,i)$ in $\mathcal{T}_{n}$, let
$f_{h,i}^{*}=\sup_{x\in\mathcal{X}_{h,i}}f(x)$, and define the set

$\mathcal{I}_{h}=\left\\{(h,i)\mid f^{*}_{h,i}\geq
f(x^{*})-2\nu_{1}\rho^{h}\right\\},$

i.e., $\mathcal{I}_{h}$ is the set of $2\nu_{1}\rho^{h}$-optimal nodes at
depth $h$. Let $\mathcal{J}_{h}$ be the set of nodes at depth $h$ that are not
in $\mathcal{I}_{h}$ but whose parents are in $\mathcal{I}_{h-1}$. We can
bound the expected number of times that an action from a node
$(h,i)\in\mathcal{J}_{h}$ is selected up to time step $n$ as

$\mathbb{E}\left[T_{h,i}(n)\right]\leq\frac{8\log
n}{\nu_{1}^{2}\rho^{2h}}+2(\hat{H}+1).$ (4)

Furthermore, we can bound the number of nodes in $\mathcal{I}_{h}$ as

$\left\lvert\mathcal{I}_{h}\right\rvert\leq C(\nu_{2}\rho^{h})^{-d}.$ (5)

#### Second step.

We partition the nodes of $\mathcal{T}_{n}$ into three disjoint sets,
$\mathcal{T}^{1}$, $\mathcal{T}^{2}$, and $\mathcal{T}^{3}$, such that
$\mathcal{T}^{1}\cup\mathcal{T}^{2}\cup\mathcal{T}^{3}=\mathcal{T}_{n}$. In
particular,

  * •

$\mathcal{T}^{1}$ is the set of nodes at depth $\hat{H}$ that are
$2\nu_{1}\rho^{\hat{H}}$-optimal, i.e.,
$\mathcal{T}^{1}=\mathcal{I}_{\hat{H}}$.

  * •

$\mathcal{T}^{2}$ is the sets of all $2\nu_{1}\rho^{h}$-optimal nodes, for all
depths $h\neq\hat{H}$, i.e.,
$\mathcal{T}^{2}=\cup_{h=0}^{\hat{H}-1}\mathcal{I}_{h}$.

  * •

$\mathcal{T}^{3}$ is the set set of all remaining nodes, i.e.,
$\cup_{h=1}^{\hat{H}}\mathcal{J}_{h}$ and corresponding descendant nodes.

We now define the regret $R_{n,k}$ of playing actions in
$\mathcal{T}^{k},k=1,2,3$, as

$R_{n,k}=\sum_{t=1}^{n}(f(x^{*})-f(X_{t}))\mathbb{I}\left[(H_{t},I_{t})\in\mathcal{T}^{k}\right]$
(6)

where $f(X_{t})$ is the expected reward collected at time step $t$ given the
action $X_{t}$ and $(H_{t},I_{t})$ is the (random) node selected in that same
time step. It follows that

$\mathbb{E}\left[R_{n}\right]=\mathbb{E}\left[R_{n,1}\right]+\mathbb{E}\left[R_{n,2}\right]+\mathbb{E}\left[R_{n,3}\right].$
(7)

#### Third step.

We now bound each of the terms in (7) to establish a bound for the total
cumulative regret after $n$ rounds.

Starting with $R_{n,1}$, in the worst case we have that

$\mathbb{E}\left[R_{n,1}\right]\leq 4n\nu_{1}\rho^{\hat{H}}.$ (8)

In turn, the nodes $(h,i)\in\mathcal{T}^{2}$ are $2\nu_{1}\rho^{h}$-optimal.
This means that

$\mathbb{E}\left[R_{n,2}\right]\leq\sum_{t=1}^{n}4\nu_{1}\rho^{H_{t}}\mathbb{I}\left[(H_{t},I_{t})\in\mathcal{T}^{2}\right]$

However, each node $(h,i)\in\mathcal{T}^{2}$ is selected only once and then
expanded—only nodes at depth $\hat{H}$ can be selected multiple times. As
such, we can use the bound in (5) to get

$\mathbb{E}\left[R_{n,2}\right]\leq\sum_{h=0}^{\hat{H}-1}4\nu_{1}\rho^{h}\left\lvert\mathcal{I}_{h}\right\rvert\leq
4C\nu_{1}\nu_{2}^{-d}\sum_{h=0}^{\hat{H}-1}\rho^{h(1-d)}$ (9)

Finally, let us consider the nodes in $\mathcal{T}^{3}$. Each node
$(h,i)\in\mathcal{J}_{h}$ is the child of a node in $\mathcal{I}_{h-1}$ and,
as such, $f(x^{*})-f^{*}_{h,i}\leq 4\nu_{1}\rho^{h-1}$. Additionally,
$\left\lvert\mathcal{J}_{h}\right\rvert\leq
2\left\lvert\mathcal{I}_{h-1}\right\rvert$, with equality if
$\mathcal{I}_{h-1}$ was fully expanded and all the direct children of the
nodes $(h-1,i)\in\mathcal{I}_{h}$ are in $\mathcal{T}_{n}$.

Using (4), we can now bound $\mathbb{E}\left[R_{n,3}\right]$ as

$\displaystyle\mathbb{E}\left[R_{n,3}\right]$
$\displaystyle\leq\sum_{h=1}^{\hat{H}}4\nu_{1}\rho^{h-1}\sum_{(h,i)\in\mathcal{J}_{h}}\mathbb{E}\left[T_{h,i}(n)\right]$
$\displaystyle\leq\sum_{h=1}^{\hat{H}}4\nu_{1}\rho^{h-1}\left\lvert\mathcal{J}_{h}\right\rvert\left(\frac{8\log
n}{\nu_{1}^{2}\rho^{2h}}+2(\hat{H}+1)\right)$
$\displaystyle\leq\sum_{h=1}^{\hat{H}}8\nu_{1}\rho^{h-1}\left\lvert\mathcal{I}_{h-1}\right\rvert\left(\frac{8\log
n}{\nu_{1}^{2}\rho^{2h}}+2(\hat{H}+1)\right)$ $\displaystyle\leq
8C\nu_{1}\nu_{2}^{-d}\sum_{h=0}^{\hat{H}-1}\rho^{h(1-d)}\left(\frac{8\log
n}{\nu_{1}^{2}\rho^{2h}}+2(\hat{H}+1)\right).$ (10)

#### Fourth step.

We now combine the bounds (8), (9) and (10) to get

$\mathbb{E}\left[R_{n}\right]\leq
4n\nu_{1}\rho^{\hat{H}}+4C\nu_{1}\nu_{2}^{-d}\sum_{h=0}^{\hat{H}-1}\rho^{h(1-d)}\left(\frac{8\log
n}{\nu_{1}^{2}\rho^{2h}}+4\hat{H}+5\right)$ (11)

Rewriting (11) using asymptotic notation, we finally get

$\mathbb{E}\left[R_{n}\right]\in O\left(n\rho^{\hat{H}}+\log
n\rho^{-\hat{H}(1+d)}+\hat{H}\max\\{\rho^{\hat{H}(1-d)},\hat{H}\\}\right),$

and the proof is complete.∎∎

We get the following corollary to Theorem 3.1.

######  Corollary 1.

Under the conditions of Theorem 3.1, selecting $\hat{H}$ so that

$\rho^{\hat{H}}=c\left(\frac{n}{\log n}\right)^{-\frac{1}{d+2}},$

for some constant $c>0$, we get

$\mathbb{E}\left[R_{n}\right]\in O\left(n^{\frac{d+1}{d+2}}(\log
n)^{\frac{1}{d+2}}\right).$ (12)

Corollary 1 establishes that, through an adequate choice of the maximum depth
$\hat{H}$, the bound on the cumulative regret of LD-HOO matches that of HOO
[4]. In the continuation, we establish that both the running time and the size
of the partition tree of LD-HOO are better than those of HOO.

###  3.2 Time and space complexity of LD-HOO

The number of nodes in the partition tree generated by LD-HOO is upper bounded
by

$\sum_{h=0}^{\hat{H}}2^{h}\in O(2^{\hat{H}}).$

However, under the conditions of Corollary 1, $\hat{H}\in O(\log n)$. As such,
the space complexity of LD-HOO is $O(n^{\log 2})$. In contrast, the number of
nodes in a partition tree generated by HOO is $O(n)$. Thus, the space
complexity of LD-HOO is asymptotically better than HOO’s.

Similarly, the running time of LD-HOO is proportional to the number of updates
to the $b$-values. After $n$ iterations, the total amount of updates is, at
most, $n$ times the number of nodes in the tree. As such, the time complexity
of LD-HOO is $O(n^{1+\log 2})$, against the $O(n^{2})$ time of HOO [4].

###  3.3 Comparison with other algorithms

We conclude this section by performing an empirical comparison between LD-HOO
and related algorithms—namely HOO [5], Poly-HOO [9] and T-HOO [4].

In our tests, we use a mean reward function
$f(x)=\frac{1}{2}(\sin(13x)\sin(27x)+1)$. The reward received by the decision-
maker at each time step is a perturbed version of $f$: upon selecting an
action $X_{t}$, the decision-maker receives a reward
$Y_{t}=f(X_{t})+\varepsilon_{t}$, where $\varepsilon$ is drawn from a Gaussian
distribution with zero mean and a standard deviation of $0.05$. We set
$\nu_{1}=1$ and $\rho=0.25$ for all algorithms. For LD-HOO we set
$\hat{H}=\lceil\log n\rceil$.111Even though our selected value for $\hat{H}$
does not verify the conditions in Corollary 1, it empirically performed well
and, as such, was used in our experiments. We compare in Fig. 3 the
performance of the 4 methods, as we vary the horizon between $n=10$ and
$n=1,000$. The results portrayed are averages of $10$ independent runs.

(a) Running time.

(b) Number of nodes in the partition tree.

(c) Cumulative regret.

Figure 3: Performance of all HOO-based algorithms in terms of time, space and
regret, as a function of the horizon, $n$.

Our results are in accordance with our theoretical analysis. As seen in Figs.
3(a) and 3(b), HOO is the most computationally demanding algorithm, both in
terms of time and in terms of the number of nodes. LD-HOO is similar to Poly-
HOO in terms of computational complexity but, as seen in Fig. 3(c), it
outperforms Poly-HOO in terms of cumulative regret. Finally, LD-HOO is similar
to T-HOO in terms of regret; T-HOO exhibits a superior running time, but a
worse number of nodes (the line of T-HOO in Fig. 3(b) overlaps that of HOO).

The conclusion from our empirical results is that, overall, LD-HOO achieves
similar or better performance than the other algorithms. The only exception is
in terms of running time, where T-HOO is noticeably faster. However, since our
ultimate goal is to use our algorithm in the context of MCTS, T-HOO is not an
option, since it is not an anytime algorithm [4].

##  4 Monte Carlo Tree Search using LD-HOO

We are now in position to introduce LD-HOOT (or LD-HOO for trees), where we
combine Monte Carlo tree search with LD-HOO. We consider Markov decision
problems (MDPs) where, at each step, the agent/decision-maker observes the
current state of the MDP, $S_{t}$, and must select an action, $X_{t}$, that
maximizes the total discounted reward, as defined in (1). Like standard MCTS
algorithms, at each step $t$ LD-HOOT builds a tree representation of the MDP
similar to that in Fig. 1. To traverse the tree, each state node $s$ is
treated as a multi-armed bandit problem, and an action is selected using LD-
HOO. When computation time is over, LD-HOOT returns the action selected by LD-
HOO at the root node (line 22 of Algorithm 1).

(a) The cart pole environment.

(b) The inverted pendulum environment.

Figure 4: Illustration of the two environments used to evaluate LD-HOOT. The
black arrows illustrate the control available: in the cart-pole scenario, the
control is performed by applying a force to the cart. In the inverted
pendulum, the control is performed by applying a force to the pendulum.

To assess the applicability of LD-HOOT, we tested the algorithm in two control
problems from the literature. We used benchmark environments from OpenAI’s Gym
[2], namely CartPole-v1 and Pendulum-v0, as well as the modified version of
cart-pole with increased gravity of Mao et al. [9]. In the two cart-pole
scenarios, the pole is initialized close to the equilibrium position, and the
role of the agent is to control the cart to keep the pole (approximately)
vertical. In the inverted pendulum scenario, the pendulum is initialized in an
arbitrary position above the horizontal line with (possible) non-zero initial
velocity, and the role of the agent is to balance the pole to the vertical
position.

We used $\nu_{1}=4$, $\rho=0.25$ and allowed LD-HOOT to have a lookahead limit
of $D=50$ actions. In all scenarios, we set $\hat{H}=\lceil\log n\rceil$. In
the cart-pole scenario, the agent interacted with the environment for a total
of $T=150$ time steps. At each time step, the action of the agent was computed
using $n=100$ iterations of the planner. In contrast, in the inverted pendulum
scenario, the agent interacted with the environment for a total of $T=100$
time steps. However, since the environment is more difficult, each action was
computed from $n=100,400$ iterations of the planner to establish the impact of
the increased $n$ in each of the algorithms. The number of actions executed in
each environment permits a comparison with the benchmark results in Open AI
Gym [12]. We normalized the rewards to the interval $[0,1]$ to allow an easy
comparison with the number of actions executed since, in this case, that is
(potentially) the maximum cumulative reward that could be obtained.

Table 1: Average sum of rewards obtained in the four test scenarios. | Cart Pole | Cart Pole IG | Inverted Pendulum
---|---|---|---
$n$ | 100 | 100 | 100 | 400
LD-HOOT | $150.0\pm 0.0$ | $150.0\pm 0.0$ | $82.46\pm 10.40$ | $84.36\pm 9.00$
HOOT | $150.0\pm 0.0$ | $150.0\pm 0.0$ | $81.23\pm 13.41$ | $81.21\pm 11.45$
POLY-HOOT | $150.0\pm 0.0$ | $150.0\pm 0.0$ | $82.40\pm 11.24$ | $84.56\pm 8.79$

Table 1 compares the performance of LD-HOOT against that of HOOT [8] and Poly-
HOOT [9], the MCTS extensions of HOO and Poly-HOO, respectively. For each
algorithm, we report the sum of rewards obtained averaged over $10$
independent trials, each with a different randomly selected initial state (but
the same across algorithms). The only exception are the results obtained in
the Inverted Pendulum with $n=100$, were the number of trials was $30$. The
differences in variance observed with different $n$ in the Inverted Pendulum
tests are likely due to the discrepancy in the number of trials and,
consequently, the usage of different initial states. Even though just
slightly, HOOT is the only of the 3 algorithms that performed worse when
running for a longer period. On the other hand, both LD-HOOT and Poly-HOOT
accrued rewards over $2\%$ larger in this scenario, thus evidencing a superior
performance against their predecessor (HOOT). As seen in Table 1, all three
algorithms perform optimally in the two cart-pole scenarios (dubbed Cart Pole
and Cart Pole ig). Even with increased gravity, all algorithms were able to
maintain the pole approximately vertical. In contrast, in the inverted
pendulum scenario LD-HOOT outperforms HOOT, and performs similarly to Poly-
HOOT. It is also noteworthy that, according to Open AI’s leaderboard [12], the
best performing algorithm in this scenario obtained an average cumulative
reward of $92.45$. Our results are close but, due to the large variance, it is
not possible to assert whether the differences are significative or not.

Table 2: Average running time (in seconds) required to plan a single action, for different values of $n$ and $\hat{H}$. $n\mid\hat{H}$ | $100\mid 5$ | $400\mid 6$ | $1000\mid 7$
---|---|---|---
LD-HOOT | $1.14\pm 0.07$ | $4.51\pm 0.06$ | $11.88\pm 0.05$
HOOT | $1.06\pm 0.04$ | $4.72\pm 0.01$ | $15.15\pm 2.55$
POLY-HOOT | $1.15\pm 0.03$ | $4.90\pm 0.21$ | $12.76\pm 0.15$

Table 2 reports the running time for the three algorithms for different values
of $n$ and $\hat{H}$, when planning a single action. The results again
correspond to averages over 10 independent trials. Our results confirm that
LD-HOOT is faster than HOOT, which was expected since LD-HOO is also faster
than HOO. When $n=100$ and $\hat{H}=5$, HOOT was marginally faster, but given
the small times considered it is possible that the differences may be due to
other processes that are being run at the same time. LD-HOOT is also faster
than Poly-HOOT in all settings considered, but differences were smaller.

Summarizing, LD-HOOT outperforms HOOT in both metrics considered, and is
slightly faster than Poly-HOOT, although attaining similar cumulative rewards.

##  5 Conclusion

In this work, we contributed LD-HOO, a novel algorithm for stochastic multi-
armed bandit problems with a continuous action spaces. We provided a regret
analysis for LD-HOO and establish that, under mild conditions, LD-HOO exhibits
an asymptotic regret bound similar to that of other algorithms in the
literature, while incurring in smaller computational costs. Our analysis was
then complemented by an empirical study, in which we show that LD-HOO
generally outperforms similar algorithms.

We then propose LD-HOOT, a Monte Carlo tree search algorithm that uses LD-HOO
to drive the expansion of the search tree. We tested LD-HOOT in several
optimal control problems from the literature, and the results show that LD-HOO
can be successfully used within MCTS to address optimal control problems with
continuous actions spaces. Additionally, our results show that LD-HOOT is
competitive with existing algorithms in terms of performance, while being
computationally more efficient.

An interesting line for future research is to build on the results presented
herein—namely Theorem 3.1—to establish the consistence of LD-HOOT in the sense
that the probability of selecting the optimal action can be made to converge
to 1 as the number of samples grows to infinity. Such results exist for MCTS
with finite action spaces [7], and we conjecture that a similar line of proof
could be used to establish similar guarantees for LD-HOOT.

##  6 Acknowledgments

This work was partially supported by national funds through FCT, Fundação para
a Ciência e a Tecnologia, under project UIDB/50021/2020.

## References

  * [1] Auer, P., Cesa-Bianchi, N., Fischer, P.: Finite-time analysis of the multiarmed bandit problem. Machine Learning 47, 235–256 (2002)
  * [2] Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., Zaremba, W.: OpenAI Gym. CoRR abs/1606.01540 (2016)
  * [3] Browne, C., Powley, E., Whitehouse, D., Lucas, S., Cowling, P., Rohlfshagen, P., Tavener, S., Perez, D., Samothrakis, S., Colton, S.: A survey of Monte Carlo tree search methods. IEEE Trans. Computational Intelligence and AI in Games 4(1), 1–43 (2012)
  * [4] Bubeck, S., Munos, R., Stoltz, G., Szepesvári, C.: $X$-armed bandits. J. Machine Learning Res. 12, 1655–1695 (2011)
  * [5] Bubeck, S., Stoltz, G., Szepesvári, C., Munos, R.: Online optimization in $X$-armed bandits. In: Adv. Neural Information Processing Systems 21. pp. 201–208 (2009)
  * [6] Kearns, M., Mansour, Y., Ng, A.: A sparse sampling algorithm for near-optimal planning in large Markovian decision processes. In: Proc. 16th Int. Joint Conf. Artificial Intelligence. pp. 1324–1331 (1999)
  * [7] Kocsis, L., Szepesvári, C.: Bandit based Monte-Carlo planning. In: Proc. 17th European Conf. Machine Learning. pp. 282–293 (2006)
  * [8] Mansley, C., Weinstein, A., Littman, M.: Sample-based planning for continuous action Markov decision processes. In: Proc. 21st Int. Conf. Automated Planning and Scheduling. pp. 335–338 (2011)
  * [9] Mao, W., Zhang, K., Xie, Q., Basar, T.: Poly-HOOT: Monte-Carlo planning in continuous space MDPs with non-asymptotic analysis. In: Adv. Neural Information Proc. Systems 33. pp. 4549–4559 (2020)
  * [10] Munos, R.: Optimistic optimization of a deterministic function without the knowledge of its smoothness. In: Adv. Neural Information Processing Systems 24\. pp. 783–791 (2011)
  * [11] Munos, R.: From bandits to Monte-Carlo tree search: The optimistic principle applied to optimization and planning. Foundations and Trends in Machine Learning 7(1), 1–129 (2014)
  * [12] Open AI: Open AI Gym’s Leaderboard
  * [13] Puterman, M.: Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons (2005)
  * [14] Schrittwieser, J., Antonoglou, I., Hubert, T., Simonyan, K., Sifre, L., Schmitt, S., Guez, A., Lockhart, E., Hassabis, D., Graepel, T., Lillicrap, T., Silver, D.: Mastering Atari, Go, chess and Shogi by planning with a learned model. Nature 588, 604–609 (2020)
  * [15] Silver, D., Huang, A., Maddison, C., Guez, A., Sifre, L., Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., Dieleman, S., Grewe, D., Nham, J., Kalchbrenner, N., Sutskever, I., Lillicrap, T., Leach, M., Kavukcuoglu, K., Graepel, T., Hassabis, D.: Mastering the game of Go with deep neural networks and tree search. Nature 529, 484–489 (2016)
  * [16] Silver, D., Hubert, T., Schrittwieser, J., Antonoglou, I., Lai, M., Guez, A., Lanctot, M., Laurent, S., Kumaran, D., Graepel, T., Lillicrap, T., Simonyan, K., Hassabis, D.: A general reinforcement learning algorithm that masters chess, Shogi, and Go through self-play. Science 362(6419), 1140–1144 (2018)
  * [17] Silver, D., Schrittwieser, J., Simonyan, K., Antonoglou, I., Huang, A., Guez, A., Hubert, T., Baker, L., Lai, M., Bolton, A., Chen, Y., Lillicrap, T., Hui, F., Sifre, L., van den Driessche, G., Graepel, T., Hassabis, D.: Mastering the game of Go without human knowledge. Nature 550, 354–359 (2017)

Limited depth bandit-based strategy for Monte Carlo planning in continuous
action spaces

Supplementary material for paper n. 923

##  Appendix 0.A Proof of Theorem 1

The proof follows the structure of the proof sketch provided in the
manuscript, and is also based on the analysis of HOO found in the work of
Bubeck et al [4]. Before dwelling into the proof, we introduce some auxiliary
results.

###  0.A.1 Auxiliary results

We define the regret of a node $(h,i)\in\mathcal{T}_{n}$ as

$r_{h,i}=f(x^{*})-\sup_{x\in\mathcal{X}_{h,i}}f(x).$

Fix an optimal path
$(0,0)\to(1,i^{*}_{1})\to\ldots\to(\hat{H},i^{*}_{\hat{H}})$, where
$(h,i^{*}_{h})$ is a child of $(h-1,i_{h-1}^{*})$ and $i^{*}_{h}$ is such that
$r_{h,i^{*}_{h}}=0$. Define the set

$\hat{\mathcal{C}}(h,i)=\left\\{c\in\mathcal{T}_{n}\mid\mathcal{X}_{c}\subset\mathcal{X}_{h,i}\right\\},$

i.e., $\hat{\mathcal{C}}(h,i)$ is the set containing node $(h,i)$ and all its
descendants. The next lemma bounds the number of times that a suboptimal node
$(h,i)$ is selected up to iteration $n$. Having a bound for the expected
number of times that a suboptimal node can be played is crucial to bound the
expected cumulative regret.

######  Lemma 1.

Let $(h_{0},i_{0})$ be a suboptimal node (i.e., a node not in the path above),
and let $k$ be the largest integer such that $0\leq k\leq h_{0}-1$ and
$(k,i^{*}_{k})$ is in the path from $(0,0)$ to $(h_{0},i_{0})$.222The extreme
case is $k=0$. Then for all integers $z\geq 0$, we have

$\mathbb{E}\left[T_{h_{0},i_{0}}(n)\right]\leq
z+\sum_{t=z+1}^{n}\mathbb{P}\Big{[}\big{(}u_{h,i^{*}_{h}}(t)\leq
f(x^{*})\text{ for some }h\in\\{k+1,\ldots,\hat{H}\\}\big{)}\\\ \text{ or
}\big{(}T_{h_{0},i_{0}}(t)>z\text{ and
}u_{h_{0},i_{0}}(t)>f(x^{*})\big{)}\Big{]}.$

###### Proof.

Let $(h_{t},i_{t})$ denote the node selected by LD-HOO at some time step $t$.
If $(h_{t},i_{t})\in\hat{\mathcal{C}}(h_{0},i_{0})$, then at depth $k$ there
is a node $(k+1,i)\in\mathcal{C}(k,i^{*}_{k})$ which, by definition of $k$, is
different from $(k+1,i^{*}_{k+1})$.

By construction, the $b$-value of a node is greater than or equal to that of
its parent node. Hence, since node $(k+1,i)$ was selected instead of
$(k+1,i^{*}_{k+1})$, then $b_{k+1,i^{*}_{k+1}}(t)\leq b_{k+1,i}(t)\leq
b_{h_{0},i_{0}}(t)$. This implies, again by construction, that
$b_{h_{0},i_{0}}(t)\leq u_{h_{0},i_{0}}(t)$ and $b_{k+1,i^{*}_{k+1}}(t)\leq
u_{h_{0},i_{0}}(t)$. Putting everything together, we have

$\begin{split}(h_{t},i_{t})\in\hat{\mathcal{C}}(h_{0},i_{0})&\Rightarrow
u_{h_{0},i_{0}}(t)\geq b_{k+1,i^{*}_{k+1}}(t)\\\
&\Rightarrow\big{(}u_{h_{0},i_{0}}(t)>f(x^{*})\text{ or
}b_{k+1,i^{*}_{k+1}}(t)\leq f(x^{*})\big{)}.\end{split}$ (13)

To see why the last implication holds, suppose that $u_{h_{0},i_{0}}(t)\geq
b_{k+1,i^{*}_{k+1}}(t)$. Then, if $u_{h_{0},i_{0}}(t)\leq f(x^{*})$, it
follows that $b_{k+1,i^{*}_{k+1}}(t)\leq u_{h_{0},i_{0}}(t)\leq f(x^{*})$, and
the conclusion follows.

We also have that

$b_{k+1,i^{*}_{k+1}}(t)\leq
f(x^{*})\Rightarrow\big{(}u_{k+1,i^{*}_{k+1}}(t)\leq f(x^{*})\text{ or
}b_{k+2,i^{*}_{k+2}}(t)\leq f(x^{*})\big{)}.$ (14)

To see why the implication in (14) holds, suppose that
$b_{k+1,i^{*}_{k+1}}\leq f(x^{*})$ holds. Then, if
$u_{k+1,i^{*}_{k+1}}(t)>f(x^{*})$, the child of $(k+1,i^{*}_{k+1})$ with
maximum $b$-value, say $(k+2,j)$, satisfies $b_{k+2,j}(t)\leq f(x^{*})$ since,
by construction,

$b_{k+1,i^{*}_{k+1}}(t)=\min\left\\{u_{k+1,i^{*}_{k+1}}(t),b_{k+2,j}(t)\right\\}.$

Then, we must have $b_{k+2,i^{*}_{k+2}}(t)\leq f(x^{*})$ and the conclusion
follows.

Finally, since LD-HOO does not expand nodes beyond depth $\hat{H}$, we have
that

$b_{\hat{H},i^{*}_{\hat{H}}}(t)=u_{\hat{H},i^{*}_{\hat{H}}}(t).$ (15)

Unfolding (14) and combining with (15) yields

$\displaystyle b_{k+1,i^{*}_{k+1}}(t)\leq f(x^{*})$
$\displaystyle\Rightarrow\big{(}u_{k+1,i^{*}_{k+1}}(t)\leq f(x^{*})\text{ or
}b_{k+2,i^{*}_{k+2}}(t)\leq f(x^{*})\big{)}$
$\displaystyle\Rightarrow\big{(}u_{k+1,i^{*}_{k+1}}(t)\leq f(x^{*})\text{ or
}u_{k+2,i^{*}_{k+2}}(t)\leq f(x^{*})\text{ or }b_{k+3,i^{*}_{k+3}}(t)\leq
f(x^{*})\big{)}$ $\displaystyle\vdots$
$\displaystyle\Rightarrow\big{(}u_{k+1,i^{*}_{k+1}}(t)\leq f(x^{*})\text{ or
}u_{k+2,i^{*}_{k+2}}(t)\leq f(x^{*})\text{ or }\ldots\text{ or
}u_{\hat{H},i^{*}_{\hat{H}}}(t)\leq f(x^{*})\big{)}.$

Combining with (13), we finally get

$(h_{t},i_{t})\in\hat{\mathcal{C}}(h_{0},i_{0})\\\
\Rightarrow\big{(}u_{h_{0},i_{0}}(t)>f(x^{*})\text{ or
}u_{k+1,i^{*}_{k+1}}(t)\leq f(x^{*})\text{ or }\ldots\text{ or
}u_{\hat{H},i^{*}_{\hat{H}}}(t)\leq f(x^{*}).$ (16)

For any integer $z\geq 0$,

$\displaystyle T_{h_{0},i_{0}}(n)$
$\displaystyle=\sum_{t=1}^{n}\mathbb{I}\left[(h_{t},i_{t})\in\hat{\mathcal{C}}(h_{0},i_{0})\right]$
$\displaystyle=\sum_{t=1}^{n}\mathbb{I}\left[(h_{t},i_{t})\in\hat{\mathcal{C}}(h_{0},i_{0}),T_{h_{0},i_{0}}(t)\leq
z\right]+\sum_{t=1}^{n}\mathbb{I}\left[(h_{t},i_{t})\in\hat{\mathcal{C}}(h_{0},i_{0}),T_{h_{0},i_{0}}(t)>z\right]$
$\displaystyle\leq
z+\sum_{t=z+1}^{n}\mathbb{I}\left[(h_{t},i_{t})\in\hat{\mathcal{C}}(h_{0},i_{0}),T_{h_{0},i_{0}}(t)>z\right].$

Taking the expectation and replacing (16), we finally get

$\displaystyle\mathbb{E}\left[T_{h_{0},i_{0}}(n)\right]$ $\displaystyle\leq
z+\sum_{t=z+1}^{n}\mathbb{P}\left[(h_{t},i_{t})\in\hat{\mathcal{C}}(h_{0},i_{0}),T_{h_{0},i_{0}}(t)>z\right]$
$\displaystyle\leq
z+\sum_{t=z+1}^{n}\mathbb{P}\Big{[}T_{h_{0},i_{0}}(t)>z\text{ and
}\big{(}u_{h,i^{*}_{h}}(t)\leq f(x^{*})\text{ for some
}h\in\\{k+1,\ldots,\hat{H}\\}\big{)}$ $\displaystyle\hskip 156.49014pt\text{
or }\big{(}T_{h_{0},i_{0}}(t)>z\text{ and
}u_{h_{0},i_{0}}(t)>f(x^{*})\big{)}\Big{]}$ $\displaystyle\leq
z+\sum_{t=z+1}^{n}\mathbb{P}\Big{[}\big{(}u_{h,i^{*}_{h}}(t)\leq
f(x^{*})\text{ for some }h\in\\{k+1,\ldots,\hat{H}\\}\big{)}$
$\displaystyle\hskip 156.49014pt\text{ or }\big{(}T_{h_{0},i_{0}}(t)>z\text{
and }u_{h_{0},i_{0}}(t)>f(x^{*})\big{)}\Big{]}.$

The proof is thus complete. ∎

The next lemmata are established by Bubeck et al. [4] and are provided without
proof.

######  Lemma 2.

If Assumptions 1 through 3 hold then, for all optimal nodes $(h,i)$ and
integers $t>0$,

$\mathbb{P}\left[u_{h,i}(t)\leq f(x^{*})\right]\leq\frac{1}{t^{3}}.$

######  Lemma 3.

Suppose that Assumptions 1 through 3 hold. Then, for all integers $t\leq n$,
all suboptimal nodes $(h,i)$ such that $r_{h,i}>\nu_{1}\rho^{h}$, and for all
integers $z$ such that

$z\geq\frac{8\log n}{(r_{h,i}-\nu_{1}\rho^{h})^{2}},$

it holds that

$\mathbb{P}\left[u_{h,i}(t)>f(x^{*})\text{ and
}T_{h,i}(t)>z\right]\leq\frac{t}{n^{4}}.$

######  Lemma 4.

Suppose that Assumptions 1 through 3 hold. If, for a node $(h,i)$,
$r_{h,i}\leq c\nu_{1}\rho^{h}$, then

$\mathcal{X}_{h,i}\subset\mathcal{X}_{\max\\{2c,c+1\\}\nu_{1}\rho^{h}}.$ (17)

The next result provides an upper bound for the number of visits to a
suboptimal node $(h,i)$.

######  Lemma 5.

If Assumptions 1 through 3 hold then, for all suboptimal nodes $(h,i)$ with
$r_{h,i}>\nu_{1}\rho^{h}$ and $n\geq 1$,

$\mathbb{E}\left[T_{h,i}(n)\right]\leq\frac{8\log
n}{(r_{h,i}-\nu_{1}\rho^{h})^{2}}+2(\hat{H}+1).$

###### Proof.

Let $(h_{0},i_{0})$ denote an arbitrary suboptimal node. Taking

$z=\left\lceil\frac{8\log
n}{(r_{h_{0},i_{0}}-\nu_{1}\rho^{h_{0}})^{2}}\right\rceil$

in Lemma 1, we get

$\mathbb{E}\left[T_{h_{0},i_{0}}(n)\right]\leq\frac{8\log
n}{(r_{h,i}-\nu_{1}\rho^{h})^{2}}+1\\\
+\sum_{t=z+1}^{n}\Big{(}\mathbb{P}\left[T_{h_{0},i_{0}}(t)>z\text{ and
}u_{h_{0},i_{0}}(t)>f(x^{*})\right]+\sum_{h=1}^{\hat{H}}\mathbb{P}\left[u_{h,i^{*}_{h}}(t)\leq
f(x^{*})\right]\Big{)}.$

Using Lemmas 2 and 3,

$\displaystyle\mathbb{E}\left[T_{h_{0},i_{0}}(n)\right]$
$\displaystyle\leq\frac{8\log
n}{(r_{h,i}-\nu_{1}\rho^{h})^{2}}+1+\sum_{t=z+1}^{n}\Big{(}\frac{t}{n^{4}}+\frac{\hat{H}}{t^{3}}\Big{)}$
$\displaystyle\leq\frac{8\log
n}{(r_{h,i}-\nu_{1}\rho^{h})^{2}}+1+\frac{1}{n^{2}}+\hat{H}\sum^{n}_{t=1}\frac{1}{t^{3}}$
$\displaystyle\leq\frac{8\log n}{(r_{h,i}-\nu_{1}\rho^{h})^{2}}+2+2\hat{H},$

where the last inequality follows from the fact that
$\sum_{t=1}^{n}\frac{1}{t^{3}}<2$. ∎

Having proved Lemma 5, it is now possible to finalise the proof of the main
result.

###  0.A.2 Proof of the theorem

The proof proceeds along the same four steps outlined in the manuscript. We
specialize the bound in Lemma 5 to bound the number of times that suboptimal
nodes in the tree are selected. The second step breaks down the value of
$\mathbb{E}\left[R_{n}\right]$ into three components. The third step bounds
each component of the regret individually. The fourth step wraps the proof by
combining the intermediate results into a final regret bound.

We revisit some notation. For a node $(h,i)$ in $\mathcal{T}_{n}$, let
$f_{h,i}^{*}=\sup_{x\in\mathcal{X}_{h,i}}f(x)$, and define the set

$\mathcal{I}_{h}=\left\\{(h,i)\mid f^{*}_{h,i}\geq
f(x^{*})-2\nu_{1}\rho^{h}\right\\},$

i.e., $\mathcal{I}_{h}$ is the set of $2\nu_{1}\rho^{h}$-optimal nodes at
depth $h$. Let $\mathcal{J}_{h}$ be the set of nodes at depth $h$ that are not
in $\mathcal{I}_{h}$ but whose parents are in $\mathcal{I}_{h-1}$.

#### First step.

We start by noting that we can use Lemma 5 to bound the expected number of
times that a node $(h,i)\in\mathcal{J}_{h}$ is played. Noting that, for these
nodes, $r_{h,i}>2\nu_{1}\rho^{h}$, then

$\mathbb{E}\left[T_{h,i}(n)\right]\leq\frac{8\log
n}{(2\nu_{1}\rho^{h}-\nu_{1}\rho^{h})^{2}}+2(\hat{H}+1)=\frac{8\log
n}{\nu_{1}^{2}\rho^{2h}}+2(\hat{H}+1).$ (18)

We can also bound the cardinality of sets $\mathcal{I}_{h}$. Define

$\mathcal{U}_{h}=\cup_{c\in\mathcal{I}_{h}}\mathcal{X}_{c}.$

In other words, $\mathcal{U}_{h}$ is the union of all cells
$\mathcal{X}_{h,i}$ such that $(h,i)\in\mathcal{I}_{h}$. Since, by definition,
for $(h,i)\in\mathcal{I}_{h}$, $r_{h,i}\leq 2\nu_{1}\rho^{h}$, it follows from
Lemma 4 (with $c=2)$ that
$\mathcal{X}_{h,i}\subset\mathcal{X}_{4\nu_{1}\rho^{h}}$ and, therefore,
$\mathcal{U}_{h}\subset\mathcal{X}_{4\nu_{1}\rho^{h}}$. But then, the
cardinality of $\mathcal{I}_{h}$ can be bounded as

$\displaystyle\left\lvert\mathcal{I}_{h}\right\rvert\leq\mathcal{N}(\mathcal{U}_{h},\ell,\nu_{2}\rho^{h})\leq\mathcal{N}(\mathcal{X}_{4\nu_{1}\rho^{h}},\ell,\nu_{2}\rho^{h})=\mathcal{N}(\mathcal{X}_{\frac{4\nu_{1}}{\nu_{2}}\nu_{2}\rho^{h}},\ell,\nu_{2}\rho^{h}).$

If $d$ is the $(4\nu_{1}/\nu_{2},\nu_{2})$-near-optimality dimension, by
definition there is $C>0$ such that

$\left\lvert\mathcal{I}_{h}\right\rvert\leq\mathcal{N}(\mathcal{X}_{\frac{4\nu_{1}}{\nu_{2}}\nu_{2}\rho^{h}},\ell,\nu_{2}\rho^{h})\leq
C(\nu_{2}\rho^{h})^{-d}$ (19)

#### Second step.

We partition the nodes of $\mathcal{T}_{n}$ into three disjoint sets,
$\mathcal{T}^{1}$, $\mathcal{T}^{2}$, and $\mathcal{T}^{3}$, such that
$\mathcal{T}^{1}\cup\mathcal{T}^{2}\cup\mathcal{T}^{3}=\mathcal{T}_{n}$. In
particular,

  * •

$\mathcal{T}^{1}$ is the set of nodes at depth $\hat{H}$ that are
$2\nu_{1}\rho^{\hat{H}}$-optimal, i.e.,
$\mathcal{T}^{1}=\mathcal{I}_{\hat{H}}$.

  * •

$\mathcal{T}^{2}$ is the sets of all $2\nu_{1}\rho^{h}$-optimal nodes, for all
depths $h\neq\hat{H}$, i.e.,
$\mathcal{T}^{2}=\cup_{h=0}^{\hat{H}-1}\mathcal{I}_{h}$.

  * •

$\mathcal{T}^{3}$ is the set set of all remaining nodes, i.e.,
$\cup_{h=1}^{\hat{H}}\mathcal{J}_{h}$ and corresponding descendant nodes.

We now define the regret $R_{n,k}$ of playing actions in
$\mathcal{T}^{k},k=1,2,3$, as

$R_{n,k}=\sum_{t=1}^{n}(f(x^{*})-f(X_{t}))\mathbb{I}\left[(H_{t},I_{t})\in\mathcal{T}^{k}\right]$

where $f(X_{t})$ is the expected reward collected at time step $t$ given the
action $X_{t}$ and $(H_{t},I_{t})$ is the (random) node selected in that same
time step. It follows that

$\mathbb{E}\left[R_{n}\right]=\mathbb{E}\left[R_{n,1}\right]+\mathbb{E}\left[R_{n,2}\right]+\mathbb{E}\left[R_{n,3}\right].$
(20)

#### Third step.

We now bound each of the terms in (20) to establish a bound for the total
cumulative regret after $n$ rounds.

Starting with $R_{n,1}$, in the worst case we have that

$\mathbb{E}\left[R_{n,1}\right]\leq 4n\nu_{1}\rho^{\hat{H}}.$ (21)

In turn, the nodes $(h,i)\in\mathcal{T}^{2}$ are $2\nu_{1}\rho^{h}$-optimal.
This means that

$\mathbb{E}\left[R_{n,2}\right]\leq\sum_{t=1}^{n}4\nu_{1}\rho^{H_{t}}\mathbb{I}\left[(H_{t},I_{t})\in\mathcal{T}^{2}\right]$

However, each node $(h,i)\in\mathcal{T}^{2}$ is selected only once and then
expanded—only nodes at depth $\hat{H}$ can be selected multiple times. As
such, we can use the bound in (19) to get

$\mathbb{E}\left[R_{n,2}\right]\leq\sum_{h=0}^{\hat{H}-1}4\nu_{1}\rho^{h}\left\lvert\mathcal{I}_{h}\right\rvert\leq
4C\nu_{1}\nu_{2}^{-d}\sum_{h=0}^{\hat{H}-1}\rho^{h(1-d)}$ (22)

Finally, let us consider the nodes in $\mathcal{T}^{3}$. Each node
$(h,i)\in\mathcal{J}_{h}$ is the child of a node in $\mathcal{I}_{h-1}$ and,
as such, $f(x^{*})-f^{*}_{h,i}\leq 4\nu_{1}\rho^{h-1}$. Additionally,
$\left\lvert\mathcal{J}_{h}\right\rvert\leq
2\left\lvert\mathcal{I}_{h-1}\right\rvert$, with equality if
$\mathcal{I}_{h-1}$ was fully expanded and all the direct children of the
nodes $(h-1,i)\in\mathcal{I}_{h}$ are in $\mathcal{T}_{n}$.

Using (18), we can now bound $\mathbb{E}\left[R_{n,3}\right]$ as

$\displaystyle\mathbb{E}\left[R_{n,3}\right]$
$\displaystyle\leq\sum_{h=1}^{\hat{H}}4\nu_{1}\rho^{h-1}\sum_{(h,i)\in\mathcal{J}_{h}}\mathbb{E}\left[T_{h,i}(n)\right]$
$\displaystyle\leq\sum_{h=1}^{\hat{H}}4\nu_{1}\rho^{h-1}\left\lvert\mathcal{J}_{h}\right\rvert\left(\frac{8\log
n}{\nu_{1}^{2}\rho^{2h}}+2(\hat{H}+1)\right)$
$\displaystyle\leq\sum_{h=1}^{\hat{H}}8\nu_{1}\rho^{h-1}\left\lvert\mathcal{I}_{h-1}\right\rvert\left(\frac{8\log
n}{\nu_{1}^{2}\rho^{2h}}+2(\hat{H}+1)\right)$ $\displaystyle\leq
8C\nu_{1}\nu_{2}^{-d}\sum_{h=0}^{\hat{H}-1}\rho^{h(1-d)}\left(\frac{8\log
n}{\nu_{1}^{2}\rho^{2h}}+2(\hat{H}+1)\right).$ (23)

#### Fourth step.

We now combine the bounds (21), (22) and (23) to get

$\mathbb{E}\left[R_{n}\right]\leq
4n\nu_{1}\rho^{\hat{H}}+4C\nu_{1}\nu_{2}^{-d}\sum_{h=0}^{\hat{H}-1}\rho^{h(1-d)}\left(\frac{8\log
n}{\nu_{1}^{2}\rho^{2h}}+4\hat{H}+5\right)$ (24)

Rewriting (24) using asymptotic notation, we finally get

$\mathbb{E}\left[R_{n}\right]\in O\left(n\rho^{\hat{H}}+\log
n\rho^{-\hat{H}(1+d)}+\hat{H}\max\\{\rho^{\hat{H}(1-d)},\hat{H}\\}\right),$

and the proof is complete.