# A Survey on GPT-3

Mingyu Zong, Bhaskar Krishnamachari
USC Viterbi School of Engineering
Los Angeles, California 90089
{mzong<EMAIL_ADDRESS>
###### Abstract

This paper provides an introductory survey to GPT-3. We cover some of the
historical development behind this technology, some of the key features of
GPT-3, and discuss the machine learning model and the datasets used. We survey
both academic and commercial efforts applying GPT-3 in diverse domains such as
developing conversational AI chatbots, software development, creative work,
domain knowledge, and business productivity. We discuss some of the challenges
that GPT-3 faces such as the problems of training complexity, bias, and
hallucination/incorrect answers. We also discuss the future research
opportunities in this area.

_Keywords_ GPT-3 $\cdot$ AI

##  1 Introduction

###  1.1 What is GPT-3?

GPT-3 is the third generation of the Generative Pre-trained Transformer (GPT)
model series, developed by researchers at OpenAI.

First generation GPT-1 model (also referred as GPT) was built in 2018. It is
created to overcome the shortage of labeled data and take advantage of the
abundant amount of unlabeled, diverse instances. This auto-regressive decoder-
only transformer adopted the self-attention mechanism. It was first trained on
the BooksCorpus and then fine-tuned for downstream tasks. In order to test the
model’s capability, 12 test tasks were selected from 4 major Natural Language
Processing (NLP) catrgories: natural language inference, question answering
and common sense reasoning, semantic similarity, and classification. This
task-agnostic model outperformed state-of-the-art models in 9 test datasets,
pointing out another direction towards Artificial General Intelligence (AGI)
[RNS+18]. Under the inspiration of GPT-1’s achievements, OpenAI researchers
continued using the decoder-only architecture to develop more powerful models.
In 2019, they released GPT-2, which had ten times the parameters compared to
the first version of GPT and has a pre-training corpus that is ten times
larger than its predecessor’s. This second model was trained on the WebText,
which is a collection of millions of webpages. Having zero supervised
training, the enlarged model created new state-of-the-art records in 7 out of
8 language modeling tasks with a zero-shot learning setting. Even though this
language model failed to compete with task-specific supervised models on
summarization, translation, and other NLP subsets with zero-shot learning, it
set convincing baselines that promoted further investigation on fine-tuning
the model [RWC+19].

GPT-3 was published one year later, in 2020. Besides augmenting the model size
to contain 175 billion parameters, developers also spent efforts filtering for
a high-quality training dataset. As a result, GPT-3 was trained on around 500
billion tokens gathered from five major data sources: Common Crawl, WebText2,
Books2, Books2, and Wikipedia [BMR+20]. As a comprehensive commercial product,
GPT-3 gets embedded in dozens of real-world applications to offer assistance,
including customer service chatbots, report summarization applications,
software development tools, etc. More details are provided in section 3.
Moreover, OpenAI has made the model available to the public through a
playground (https://beta.openai.com/playground) and an API. Every registered
user has 18-dollar-worth free credits to try out the model’s capabilities.
Many parameters, such as mode and temperature, can be adjusted to better fit
downstream tasks. Their API gives access to all functionalities of the model
provided by the playground, along with an additional fine-tuning option.

###  1.2 How to use GPT-3

Figure 1: GPT-3 Playground under the "completion" mode

The GPT-3 playground is a published website with explicit design to help users
get start using the model. Users can choose between 4 models and 3 different
modes based on their needs. The most frequently used mode is the "complete"
mode. A user input some text and expect the model to continue writing until
the next word or sequence to be generated is a stop sign. The "insert" mode
requires users to use the placeholder "[insert]" when submitting a query.
GPT-3 will return the whole piece of text with the placeholder being
substituted by its prediction. However, the model can deal with only one
insert at a time. To use the "edit" mode, input text and instructions must be
typed into two text boxes. Output of the model would be modified input text. A
typical usage of the edit mode is grammar correction. The 4 models include
davinci, curie, babbage, and ada. Cost of using a model is proportional to
model’s ability, so customers can pick the optimal one to use base on their
needs and budget. Among these, davinci is the most powerful yet most expensive
model. The remaining three models trade off performance for being more
economical. Nevertheless, ada, the least capable model, is sufficient to
handle some simple tasks.

A set of parameters are listed on the right hand side of the input text box,
under the selection of mode and model. By adjusting values of these
parameters, users are able to add some control over the model’s behavior. One
of the most frequently used parameters is the "temperature", which determines
how much randomness to involve during generation. Generative models are well
known for their ability to generate new contents with the same input prompt
[GER22]. GPT-3 achieves this through the "temperature" parameter. If the value
is set to 0, then regardless of number of times of generation, the model will
always output the same response with fixed input text. Increasing the value of
"temperature" allows users to take advantage of GPT-3’s creativity, it will
provide more possible completions from multiple runs. Maximum value allowed
for this is 1. "Maximum length" sets the upper limit of the amount of tokens
to be generated. Default value is 256, but writing paragraphs or stories often
requires more. A maximum of 4000 tokens can be output. "Stop sequence" is
another useful parameter. If the model is expected to play a role in a
conversation, adding a delimiter is necessary to prevent it from writing the
lines for the other character. Other available parameters are "TOP P",
"Frequency penalty", "Presence penalty", "Best of", "Inject start text",
"Inject restart text", and "Show probabilities". All of these can be adjusted
under the "completion" mode. However, both the "insert" and the "edit" modes
are in beta, so there are less available options provided.

Furthermore, people can interact with GPT-3 through OpenAI’s API. Before use,
the "openai" library must be installed and a user needs to acquire an API key.
Then the user can access the model with specified input, model, mode, and
other parameter settings to use GPT-3 in one of the three modes listed before.
One function that provided by the API but not the playground is fine-tuning,
which further trains the model to adapt to specific task(s). Since it is
allowed to keep training a fine-tuned version of GPT-3, with enough resources,
the model’s overall ability can also be lifted. Prerequisite of using the
fine-tuning functionality, is a prepared JSONL file, in which every instance
is broken into two parts: "prompt" and "completion". OpenAI has a
corresponding CLI data preparation tool, which easily converts a CSV, TSV,
XLSX, JSON or JSONL file into the required format. Besides model, other
parameters such as "n_epochs" and "batch_size" can be customized. After
completion of the fine-tuning, the model will be accessible by its unique
name. GPT-3 learns patterns from training instances in a provided JSONL file.
When the fine-tuned model sees a similar test instance, it uses new knowledge
to write better answer.

###  1.3 Model performance on NLP tasks

|  |  | 175B GPT-3
---|---|---|---
Dataset | Metric | Fine-tuned SOTA | Zero-shot | Few-shot
Language Modeling
PTB | perplexity | 35.8 | 20.5 | -
|  |  |  |
Text Completion
LAMBADA | accuracy | 68.0 | 76.2 | 86.4
StoryCloze | accuracy | 91.8 | 83.2 | 87.7
HellaSwag | accuracy | 85.6 | 78.9 | 79.3
|  |  |  |
Question-Answering
NaturalQS | accuracy | 44.5 | 14.6 | 29.9
WebQS | accuracy | 45.5 | 14.4 | 41.5
TriviaQA | accuracy | 68.0 | 64.3 | 71.2
|  |  |  |
Language Translation
En -> Fr | BLEU-mb | 45.6 | 25.2 | 32.6
Fr -> En | BLEU-mb | 35.0 | 21.2 | 39.2
En -> De | BLEU-mb | 41.2 | 24.6 | 29.7
De -> En | BLEU-mb | 40.2 | 27.2 | 40.6
En -> Ro | BLEU-mb | 38.5 | 14.1 | 21.0
Ro -> En | BLEU-mb | 39.9 | 19.9 | 39.5
|  |  |  |
Understanding Reference of Pronoun
Winograd | accuracy | 90.1 | 88.3 | 88.6
Winogrande(XL) | accuracy | 84.6 | 70.2 | 77.7
|  |  |  |
Commonsense Reasoning
PIQA | accuracy | 77.1 | 81.0 | 82.8
ARC(easy) | accuracy | 92.0 | 68.8 | 70.1
ARC(challenge) | accuracy | 78.5 | 51.4 | 51.5
OpenBookQA | accuracy | 87.2 | 57.6 | 65.4
|  |  |  |
Reading Comprehension
CoQA | F1 | 90.7 | 81.5 | 85.0
SQuADv2 | F1 | 93.0 | 59.5 | 69.8
RACE-h | accuracy | 90.0 | 45.5 | 46.8
RACE-m | accuracy | 93.1 | 58.4 | 58.1
|  |  |  |
SuperGLUE Benchmark
SuperGLUE | average | 89.0 | 58.2 | 71.8
|  |  |  |
Understanding Relationship between Sentences
ANLI R1 | accuracy | 73.8 | 34.6 | 36.8
ANLI R2 | accuracy | 50.7 | 35.4 | 34.0
ANLI R3 | accuracy | 48.3 | 34.5 | 40.2
|  |  |  |
Arithmetic
2 digit addition | accuracy | - | 76.9 | 100.0
2 digit subtraction | accuracy | - | 58.0 | 98.9
3 digit addition | accuracy | - | 34.2 | 80.4
3 digit subtraction | accuracy | - | 48.3 | 94.2
4 digit addition | accuracy | - | 4.00 | 25.5
4 digit subtraction | accuracy | - | 7.50 | 26.8
5 digit addition | accuracy | - | 0.65 | 9.30
5 digit subtraction | accuracy | - | 0.80 | 9.90
2 digit multiplication | accuracy | - | 19.8 | 29.2
1 digit composite operations | accuracy | - | 9.75 | 21.3
|  |  |  |
Manipulated Words Correction
cycle letters | accuracy | - | 3.66 | 37.9
anagrams 1 | accuracy | - | 2.28 | 15.1
anagrams 2 | accuracy | - | 8.91 | 39.7
random insertion | accuracy | - | 8.26 | 67.2
SAT Analogies
SAT Analogies | accuracy | - | 53.7 | 65.2
Table 1: Various Test Results From SOTA And GPT-3

Along with the publication of the model, OpenAI developers also performed
thorough examination on GPT-3 of all sizes and presented results in their
original work [BMR+20]. Every model was tested three times using zero-shot,
one-shot, and few-shot learning methods separately. Zero-show learning means
no demonstration is provided to a model; while few-shot learning will offer a
few examples for a model to learn, then ask for a completion. Observing from
the results, model performance is expected to improve as a) model size
increases or b) more demonstrations are available. We present some of the
results that Brown _et al._ obtained from full-sized (175B) GPT-3 and
benchmarks set by SOTA models for reference (Table 1), more details can be
found in the original paper[BMR+20].

As a language model, GPT-3 is as competitive as the fine-tuned SOTA model on
several aspects, including text completion, question-answering, translating
other language into English, and understanding reference of pronoun. Among all
these, it is most capable of text completion and determining reference, with
an overall accuracy above 80% on these tasks. On the other hand, its
performance on the rest three categories are remarkable but not yet satisfying
as an alternative of human intelligence. One variation not shown in the table
is that, for question-answering test, fine-tuned SOTA model is open domain,
but GPT-3 had no access to any external knowledge base during the process.
Under these circumstances, GPT-3 is comparable as SOTA in two of the three
cases. Based on the considerable gaps between zero-shot results and few-shot
results, researchers suggest that problems in the NaturalQS dataset and the
WebQS dataset could be out of distribution for GPT-3’s training set [BMR+20].
Improvement of future language model can be built on this to fully explore the
potential of transformer. More complicated assignments such as commonsense
reasoning and reading comprehension still remain challenging for this
architecture, even though the "attention" mechanism enhanced its comprehension
on input text: it can hardly succeed with more than 70% accuracy. Besides
ordinary NLP tasks, GPT-3 was also tested for its ability in doing arithmetic,
correcting misspelled English words, and solving “SAT Analogies". Most of the
returning success rates are below 50%. But the model displays distinctive
strength in arithmetic computation when operands have at most three digits
[BMR+20].

Decoder-only transformer models usually perform better at language generation.
Developers of GPT-3 examined this capacity through article generations and
human evaluation. As a result, human successfully distinguish AI-generated
passages from authentic ones at a rate of 52%, which is merely above chance
[BMR+20].

##  2 Historical Background and Prior Literature before GPT-3

###  2.1 Early NLP Models

Human efforts in solving natural language processing (NLP) can be traced back
to the 1950s, as translation between languages appeared to be the key to
intelligence collection during World War II. Linguisticians tried to decode
the foreign symbols and summarized a set of rules to follow for translation.
Early NLP experiments programmed the machine to automatically enforce those
rules when performing translation tasks, contributing to one of the most
typical assignments in NLP: machine translation (MT). However, human
assistance was often involved due to the limited coverage of foreign language
regularities, which contradicts the idea of a fully automized process. An
expert editor would revise a preliminary translation result before it could be
put to use. Researchers also utilized multiple iterations of human revision
and re-generation with updated dictionaries and grammar to optimize the
quality of instance generation and the whole translation system [Hut95]. The
Automatic Language Processing Advisory Committee released a report in 1966
that thoroughly assessed MT systems’ development. Given the numerous resources
invested into the field of study, the performance of most advanced systems at
the time with human post-editing still performed much worse than human
translators regarding accuracy, efficiency, and comprehension level;
conclusively, the committee claimed there was no immediate prospect of a
desirable system [PC66]. Machine translation research reached a trough under
the reflection until statistical MT systems emerged to replace symbolic
systems. Starting with IBM’s promising experiments of purely statistical
methods, subsequent research focused on constructing corpora and adopting
machine learning methods to align words and phrases between languages [Sch18].
With increasing computational power and evolving designs of processing
architecture, natural language processing extended its scope to include text
summarization, document classification, question answering, and more sub-
classes.

Before the introduction of Transformer models, Recurrent Neural Network (RNN)
models gained significant popularity in solving NLP tasks. These models have
the capability to memorize and process long-term dependencies among inputs
because of the additional hidden layer embedded in the architecture. Thus,
they appeared to be more effective at understanding sequential and time series
data. This nature has led to its prominent manifestation in healthcare. A case
study of clinical diagnoses and medication group prediction using EHR records
has proved that the RNN model performed better with longer input records
[XS21]. RNN models’ convincing ability to complete classification assignments
has also benefited other fields, such as human studies and city planning.
Nevertheless, the design of these models resulted in a slow computation rate,
making it challenging to train an RNN model over a large dataset.
Consequently, not being able to exploit the value of the enormous amount of
data is why scientists developed the superseding Transformer architectures.

###  2.2 Transformers Before GPT-3

In 2017, the Google Brain research team proposed a "self-attention" mechanism,
along with the vanilla Transformer network architecture built upon it. The
architecture inherits the encoder-decoder structure. However, instead of
highlighting relationships between sequences, self-attention captures
relationships between different parts within one sequence by packing key-value
pairs of vectors (i.e., representations of pairwise relationships) into the
computation matrix [VSP+17]. Lin pointed out in the survey that the encoder or
decoder alone is sufficient for solving specific types of NLP problems
[LWLQ21]. Generative Pre-training Transformers (GPT) is the first published
model pre-trained on a large corpus; the model is decoder-only. Developers of
GPT at OpenAI tested the process of combining pre-training and fine-tuning and
proved it could boost model performance drastically. This workflow ensures
that GPT is adaptive to multiple tasks while overcoming the difficulty of not
having enough labeled data [RNS+18]. A series of pre-trained Transformer
models were created in recent years, with some variations in design.
Bidirectional Encoder Representations from Transformers (BERT) with the
complete encoder-decoder architecture is one of the most prominent. Its bi-
directionality allows the model to relate both previous and following words
when attending to any individual within the input [DCLT19]. As transformer
models enlarge their scales, the community has agreed that model performance
is proportional to its scale. Therefore, top tech companies are investing
resources into creating a more powerful Transformer to explore its upper
limit.

##  3 (Non-Academic) Applications of GPT-3 in Real World

###  3.1 Assistance in Question-Answering System

There are mainly two types of products that exploits GPT-3 for assistance in
question-answering interaction. On is customer service providers, and the
other is chatbots. Customer service sometimes is delivered through a chatbot.
For example, ActiveChat allows users to chat with their customers at real
time. At the same time, GPT-3 offers hints to help users formulate their
responses. On the other hand, customer service can be offered by replying to
customers’ comments/feedback/reviews. Replier.ai free retailers from manually
responding to customers’ reviews. They offer a paid product which
automatically replies to the reviews after simple setup. Chatbots are
developed for various purposes, ranging from entertainment to simulation of
the dead. AIBuddy is a GPT-3 powered version of Whatsapp. A user can discuss
whatever topic he/she is interested in with the agent. Project December is a
hyper-realistic chatbot to simulate conversations with any human being, alive
or not.

###  3.2 Contribution to Creative Work

Many applications on the market are powered by GPT-3 to generate creative and
customized contents to meet users’ demand. For instance, Copysmith combined
GPT-3 with other machine learning algorithms to write texts based on users’
requirements. Description of product, advertisement headline, blog idea are
all covered by its functionality. Similarly, email subject line generator by
Encharge utilizes the model to write emails. Required input to use this
application is a single-line subject description. And users can choose between
more than ten tones for a desired writing style. Botto, another software, uses
GPT-3 in a different way. Input data is supposed to be an image, and the model
generates poetic description for it. Another popular usage of the model is
writing articles and essays. Ghosts is a special app that writes essay about
grief with support from GPT-3.

###  3.3 As Software Developer

The Tailwind CSS code generator is one of the code generation applications
that empowered by GPT-3 model. It is design to write CSS code based on
requirements in textual format. However, later in 2021, OpenAI developers
created the Codex system based on GPT-3, which is specifically designed to
convert natural language description into code. More code generation
applications chose to embed Codex instead of the original GPT-3 model because
of the greater ability in this specific task. CodeStarter is a representative
application that uses Codex to assist code generation. With a description of
intended web app, CodeStarter will write the scripts instantly in any
specifies framework: React, Angular, and more.

###  3.4 Additional Usage by Domain

Besides the above three common category, GPT-3 is also used in games, language
learning, and content searching. Specifically, AI Dungeon relies on GPT-3 to
generate a new set of exploration options for a text adventure game. Duolingo
uses GPT-3 to correct grammars of French sentences to ensure the materials
won’t mislead its users. Podacity AI trusts GPT-3’s ability in understanding
natural language. So the model is in charge of understanding what kind of
podcasts are wanted by the user.

##  4 Academic Research on GPT-3 and its Applications

###  4.1 GPT-3 for Bio-medical and Healthcare domain

One classic usage that makes GPT-3 helpful in healthcare is that it can be
trained to support customer service with minimum efforts. Image having an
automatic agent instantly replying to trivial questions and translate local
languages into English, resources at a clinic can be more efficiently
allocated [NME+22]. Beyond these, it is more difficult but plausible to train
the model for support in triaging patients. GPT-3 can acquire all necessary
information through a conversation instead of a intake form, and there could
be multiple implemented systems to help a number of patients simultaneously
[KM21]. Overall, efficiency is the most attractive reason of adopting a
language model in this area. There are other factors at play as well. Clinics
and hospitals are places to cure illness, but it is also true that various
contagious viruses are brought into these places. If a human receptionist is
replaced by a robot, both patient and healthcare provider can be better
protected from being infected. This consideration appears to be even more
essential during the Covid-19 pandemic.

Some major concerns of embedding this language model into healthcare delivery
process include cost, model behavior, and privacy concerns. Clinics and
hospitals usually have a high volume of daily visits. An optimal system may
submit multiple queries for every single patient in order to generate
appropriate output. Altogether, deployment of GPT-3 could result in
considerable amount of operation cost. Furthermore, existing auditing methods
are not mature enough to suppress all problematic generations, as we further
explore in section 4.4. Healthcare is a field with even higher standards for
interactions with patients. Thus, it is worth evaluating the risks and harms
before implementation. Finally, medical records are strictly protected by
convention. But seeking help from GPT-3 would inevitably share these data with
OpenAI. It is necessary that OpenAI and healthcare providers obey the same set
of rules to protect patients’ privacy [SSL22].

###  4.2 GPT-3 for writing

Generative language models are prominent for writing authentic texts in
different format, including articles, essays, and summaries. In one study, a
one-sentence prompt is offered to the GPT-3 and human writers for continuation
of one paragraph. And the generated texts are randomly sent to human
annotators for evaluations. Researchers quantified different error types
noticed in the generations. It turns out that GPT-3 is better at using
technical jargon and knowledge that human readers often need to google to
confirm. But human writers outperformed the model with respect to the other
eight error types. Another finding from the study is that model’s overall
ability in writing is growing with model’s size [DFKK+22]. Apparently,
contents generated by GPT-3 are still distinguishable from human writings, but
it’s possible that newer language models are able to produce more reliable
sources and eventually defeat human in open-ended composition. Although having
GPT-3, or language model in general, as a writer raises problems with
copyrights, which we investigate in section 5.2. Another recent work aims to
use GPT-3 at data augmentation. By using ensemble techniques and 210 example
dialog summaries, Chintagunta was able to obtain medically correct synthesized
summaries [CKAK21]. It is known that medical records are not easily accessible
because of the regulations. This project proposes a solution for acquiring
medical data without violates patients’ privacy. Without the challenge of data
acquisition, the research community can make faster progress in AI-assisted
medical experiments.

###  4.3 GPT-3 for generating code or plans

Although not as reliable as in common NLP tasks like text summarization, GPT-3
shows its potential in writing code blocks and programming scripts. Examining
80 programs generated by the model, researchers found that 38 of them are of
good quality. A conclusion is derived from the test results that GPT-3’s code
generation can partially contribute to software development [NRV21]. It is
still too early to replace human coders with an AI agent.

Another area that GPT-3 expanded to cover is plan formulation, which primarily
relies on human judgment from natural language description of the situation.
With large language models’ natural language understanding talent, researchers
see a possibility to free human resources from repeatedly laying plans for
similar tasks. Olmo adopted a few-shot setting (from 1-shot to 4-shot) to test
whether GPT-3 is good at plan extraction or not. Microsoft Windows Help and
Support, WikiHow Home and Gar- den and CookingTutorial datasets were included
in the experiment. Among all four models, davinci outperformed the other three
with over 80% F1 score, and its performance benefits from additional examples
provided in the prompt. Even though GPT-3 can compete with state-of-the-art
methods, the fact that it learns from available examples makes it another
task-specific approach. Its problem-solving ability cannot extend to other
scenarios [OSK21]. Another research project focus on using GPT-3 to write
Lesson plans. It deployed a zero-shot learning setting. All prompts contained
only a one-sentence instruction. Although some contents in the responses are
incorrect, there is an opportunity to utilize GPT-3 in forming K-12 lesson
plans [Wal22].

###  4.4 GPT-3 for math tutoring

Educators have long been struggling with the imbalanced ratio of education
resources to student demand in various disciplines. One of main issues is that
there lack accessible teaching materials for students to study off-school.
Online tutorial videos are emerging to ease the situation, but society still
hope to provide personalized teaching services through AI to meet the learning
needs of each student and improve teaching efficiency. Among many disciplines,
mathematics is relatively more systematic. Researchers are making progress
towards an artificial math tutor. Recurrent neural network (RNN)-based
sequence-to-sequence, graph-to-tree, and sequence-to-tree networks are
constructed to convert math word problems into representative equations
[WLS17, ZWL+20, WZFH20]. Transformer-based architectures are also proposed to
take advantage of a huge volume of training data. However, even though these
models performed as expected on test set, they fail to extend their ability to
convert out-of-scope math problems. Besides, previous studies mainly focus on
questions with only one variable. On the other hand, GPT-3 is able to extract
a system of equations which is composed of two unknowns with satisfying
performance. It achieved an accuracy of 69% with a few-shot learning setting
and further improved the performance to convert 80% of the questions correctly
with fine-tuning[ZK22].

###  4.5 Auditing

Due to the unconstrained output space, it remains challenging to interpret a
large language model. The difficulty will be passed on to future models. For
it to be used as (part of) a commercial product, developers of GPT-3 are
expected to audit the model thoroughly before it’s open to the public.
However, there is no systematic way to unravel model’s problematic behavior.
The field is drawing increased attention from the research community.

Some preliminary actions taken by OpenAI researchers include content filtering
and feedback collection. An automated content filter is used to constantly
screening output of GPT-3 for regulating purpose. Every generation is
classified into one of the three levels: safe, sensitive, and unsafe.
Depending on the classification result, generated text is either suppressed or
displayed with a warning. Documentation of GPT-3 emphasizes that the function
is still in beta and results in higher false positive rate. An example that
confirms the filter’s imperfection is found by Gero. One generated text that
contains the word "lesbian", despite the whole statement being positive,
induced a warning of unsafe content [GER22]. In this case, the harm is not
caused by a toxic answer but the design of the filter. Another issue with the
filter design is that marginalized identities often don’t get enough
consideration [BGMMS21]. Collection of user feedback on each generation is
another insurance that OpenAI researchers take to monitor and adjust GPT-3’s
behavior. Users with diverse background help reduce bias in decision-making.
However, the process takes time and fails to protect whoever sees a harmful
content at the first place. Weighing both pros and cons of the existing
methods, it is clear that another efficient and accurate auditing
algorithm/system is highly in demand.

###  4.6 Research on improving GPT-3 performance

Primary method to improve GPT-3’s performance is _prompt engineering_. This
refers to what instructions are provided and whether or not to offer examples
in a prompt. More importantly, prompt engineering is not task-agnostic. There
is no standardized setting that guarantees the best performance in every test.
Due to difficulty of interpretation, it is always possible that a better
prompt exists for a specific task. With limited input space, exhaustive
testing is a way to find out the best combination of instructions and
examples. But this method is computationally expensive. So researchers keep
exploring more robust solutions. With respect to example selection, the best
practice is to provide similar ones so that it is easier for a model to catch
the point. Therefore, Prodan and Pelican developed a scoring system to rank
conversations based on similarity. Three concepts are taken into account:
length, content, and number of characters involved. Components are multiplied
by weights and then summed up to calculate the final score [PP21].

On the other hand, OpenAI researchers trained a verifier, which in fact is a
fine-tuned GPT-3, to output possibilities of an input being correct. The
entire problem-solving system consists of a generator and a verifier. Both of
them are GPT-3 models, but are fine-tuned using different dataset. For every
test instance, multiple candidates are pooled from the generator and ranked
according to the verifier’s evaluation. The one obtained the highest
probability is considered the final output [CKB+21]. In other words, GPT-3
itself can be calibrated into a selection tool when fine-tuning is appropriate
for intended results.

##  5 Limitations and Pitfalls of GPT-3

###  5.1 Limitations in Design

As revealed in OpenAI’s testing results, many NLP problems and mathematical
calculations expressed in the textual format are still beyond the scope of
GPT-3’s knowledge. Thus, transformers’ performance on several tasks has not
yet reached the cap. Since the model’s performance on various tasks still
grows with scale, researchers can efficiently address this issue by expanding
a pre-trained transformer’s training dataset and enlarging the model size.
Given its unidirectional decoder-only architecture, GPT-3 is naturally less
suitable for certain types of NLP tasks, for example, semantic understanding.
Using only statistical probabilities to predict the following tokens, GPT-3
tends to fail simple reversible answers that can be solved by common knowledge
[FC20]. Moreover, GPT-3 is primarily designed to process text inputs. Although
when using the playground, users can upload audio file or record instantly to
have the data converted into text, the functionality is still in beta.
Developing extensions to precisely transform imagery and audio input will
further expand model’s usage in the industry. Lastly, even though GPT-3 has
approved its capability in various assignments to excel in domain-specific
tasks, fine-tuning is still required to supplement domain knowledge and
improve performance. A reasonable amount of data required to fine-tune GPT-3
is 1000 instances, which could be a challenge for some down-stream tasks, for
example, analysis of medical records.

###  5.2 Misuse of the model

One concern pointed out by GPT-3 developers is the misuse of this model,
including fraudulent essay composition, spam message creation, and even
assistance in formulating malicious tactics, techniques, and procedures
(TTPs). Given the fact that GPT-3 is writing on top of its training corpus, it
is difficult to decide who should get credit for the generated piece of work:
writers who composed these training data, GPT-3’s owner OpenAI, or whoever
used the model to create the text. This nature also blurs the boundary between
plagiarism and original work [Deh21]. The model currently couldn’t support any
large-scale activities because generated contents still need to be manually
filtered for quality [BMR+20]. However, GPT-3 is not embedded with mechanisms
to detect and prevent illegal usage, which may lead to the development of
subsidiary systems and new regulations or policies pertaining to authentic
materials and plagiarism.

###  5.3 Bias

Humans are inevitably biased, so are their writings. Being trained on human
created contents infers that GPT-3 inherits these biases and will perpetuate
them using its responses. Several studies focused on eliciting biased
generations. Different types of biases are revealed. First type of bias
relates to gender representation. GPT-3’s output space varies depending on the
perceived gender of a given character. Four topics that are frequently used to
generate stories for a male character are war, crime, politics, and sports.
However for a female character, her story depicts more about family, emotions,
and body. Furthermore, masculine descriptions are often used to portray a male
character, while female characters generally have a weaker and less powerful
setting [LB21]. Even if the same set of brilliant traits are offered in the
prompt, the model still understates the brilliance of woman compared with a
man [SAT+22]. Second variation of bias that exists in GPT-3’s "mind" is racial
bias. OpenAI researchers explored whether racial bias would be a major concern
for publication. A placeholder of race is embedded in every prompt and the
model is supposed to choose among seven available options. After computing
sentiment score, they noticed that sentiment score for "Asian" is consistently
high but the score for "Black" is consistently low [BMR+20]. Researchers at
Stanford University created a Q-Pain dataset to test if GPT-2 and GPT-3 has
racial biases in medical Q&A tasks. The experiment focused on pain management.
As a result, GPT-3 has 3.6% higher possibility of refusing a pain treatment if
the patient is black [LRD+21]. This set of discoveries support that GPT-3 is
racially biased and it needs further calibration. Moreover, religious bias is
also an issue with large language models including GPT-3. A research found out
that the word "Muslim" is tightly related to the word "terrorist" and has a
much higher chance to induce violent output [AFZ21].

###  5.4 Being energy-intensive

Running such a gigantic architecture is incredibly energy-consuming. In
addition, the training process is equally energy-intensive, considering the
resources needed to distribute billions of tokens and number of iterations
required before publication [BHA+21]. Future language models aim to surpass
GPT-3 by increasing model size until another architecture is proposed to
replace transformers. There is no doubt that resources to be consumed will
grow exponentially, leading to serious environmental concerns. It is worth
thinking whether the boost in model performance deserves the extra amount of
resources needed for its operation. Considering the accelerated global warming
and its negative impact on human habitat, it is imperative to innovate new
architecture which is equivalently powerful yet more environmental-friendly.

##  6 Conclusion

We have introduced the GPT-3 model, arguably the most capable large language
model in existence today. This introduction discussed what it is, how it is
developed, what it’s capable of, and what its limitations are. As the largest
publicly available language model at this time, GPT-3 performs well in a
number of standard NLP tasks such as text completion and summarization.
Despite the risks of creating misleading/inappropriate/biased, this
architecture is already starting to see practical adoption in commercial
products, from chatbots to software development applications. However, the
research community emphasizes the importance of development of auditing
systems, which will benefit not only GPT-3, but also future language models.

## References

  * [AFZ21] Abubakar Abid, Maheen Saleem Farooqi, and James Y. Zou.  Persistent anti-muslim bias in large language models.  Proceedings of the 2021 AAAI/ACM Conference on AI, Ethics, and Society, 2021.
  * [BGMMS21] Emily M. Bender, Timnit Gebru, Angelina McMillan-Major, and Shmargaret Shmitchell.  On the dangers of stochastic parrots: Can language models be too big? ´f99c.  Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency, 2021.
  * [BHA+21] Rishi Bommasani, Drew A. Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S. Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, Erik Brynjolfsson, S. Buch, Dallas Card, Rodrigo Castellon, Niladri S. Chatterji, Annie S. Chen, Kathleen A. Creel, Jared Davis, Dora Demszky, Chris Donahue, Moussa Doumbouya, Esin Durmus, Stefano Ermon, John Etchemendy, Kawin Ethayarajh, Li Fei-Fei, Chelsea Finn, Trevor Gale, Lauren E. Gillespie, Karan Goel, Noah D. Goodman, Shelby Grossman, Neel Guha, Tatsunori Hashimoto, Peter Henderson, John Hewitt, Daniel E. Ho, Jenny Hong, Kyle Hsu, Jing Huang, Thomas F. Icard, Saahil Jain, Dan Jurafsky, Pratyusha Kalluri, Siddharth Karamcheti, Geoff Keeling, Fereshte Khani, O. Khattab, Pang Wei Koh, Mark S. Krass, Ranjay Krishna, Rohith Kuditipudi, Ananya Kumar, Faisal Ladhak, Mina Lee, Tony Lee, Jure Leskovec, Isabelle Levent, Xiang Lisa Li, Xuechen Li, Tengyu Ma, Ali Malik, Christopher D. Manning, Suvir P. Mirchandani, Eric Mitchell, Zanele Munyikwa, Suraj Nair, Avanika Narayan, Deepak Narayanan, Benjamin Newman, Allen Nie, Juan Carlos Niebles, Hamed Nilforoshan, J. F. Nyarko, Giray Ogut, Laurel J. Orr, Isabel Papadimitriou, Joon Sung Park, Chris Piech, Eva Portelance, Christopher Potts, Aditi Raghunathan, Robert Reich, Hongyu Ren, Frieda Rong, Yusuf H. Roohani, Camilo Ruiz, Jack Ryan, Christopher R’e, Dorsa Sadigh, Shiori Sagawa, Keshav Santhanam, Andy Shih, Krishna Parasuram Srinivasan, Alex Tamkin, Rohan Taori, Armin W. Thomas, Florian Tramèr, Rose E. Wang, William Wang, Bohan Wu, Jiajun Wu, Yuhuai Wu, Sang Michael Xie, Michihiro Yasunaga, Jiaxuan You, Matei A. Zaharia, Michael Zhang, Tianyi Zhang, Xikun Zhang, Yuhui Zhang, Lucia Zheng, Kaitlyn Zhou, and Percy Liang.  On the opportunities and risks of foundation models.  ArXiv, abs/2108.07258, 2021.
  * [BMR+20] Tom B Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al.  Language models are few-shot learners.  arXiv preprint arXiv:2005.14165, 2020.
  * [CKAK21] Bharath Chintagunta, Namit Katariya, Xavier Amatriain, and Anitha Kannan.  Medically aware gpt-3 as a data generator for medical dialogue summarization.  In NLPMC, 2021.
  * [CKB+21] Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman.  Training verifiers to solve math word problems.  ArXiv, abs/2110.14168, 2021.
  * [DCLT19] Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In NAACL, 2019.
  * [Deh21] Nassim Dehouche.  Plagiarism in the age of massive generative pre-trained transformers (gpt-3).  Ethics in Science and Environmental Politics, 21:17–23, 2021.
  * [DFKK+22] Yao Dou, Maxwell Forbes, Rik Koncel-Kedziorski, Noah A. Smith, and Yejin Choi.  Is gpt-3 text indistinguishable from human text? scarecrow: A framework for scrutinizing machine text.  In Annual Meeting of the Association for Computational Linguistics, 2022.
  * [FC20] Luciano Floridi and Massimo Chiriatti.  Gpt-3: Its nature, scope, limits, and consequences.  Minds and Machines, 30(4):681–694, 2020.
  * [GER22] KATY ILONKA GERO.  How do we audit generative algorithms?  2022\.
  * [Hut95] William J. Hutchins.  Machine translation: A brief history.  1995\.
  * [KM21] Diane M. Korngiebel and Sean D. Mooney.  Considering the possibilities and pitfalls of generative pre-trained transformer 3 (gpt-3) in healthcare delivery.  NPJ Digital Medicine, 4, 2021.
  * [LB21] Li Lucy and David Bamman.  Gender and representation bias in gpt-3 generated stories.  In NUSE, 2021.
  * [LRD+21] C’ecile Log’e, Emily L. Ross, David Yaw Amoah Dadey, Saahil Jain, Adriel Saporta, Andrew Y. Ng, and Pranav Rajpurkar.  Q-pain: A question answering dataset to measure social bias in pain management.  ArXiv, abs/2108.01764, 2021.
  * [LWLQ21] Tianyang Lin, Yuxin Wang, Xiangyang Liu, and Xipeng Qiu.  A survey of transformers.  ArXiv, abs/2106.04554, 2021.
  * [NME+22] Siddharth Nath, Abdullah Marie, Simon Ellershaw, Edward Korot, and Pearse A. Keane.  New meaning for nlp: the trials and tribulations of natural language processing with gpt-3 in ophthalmology.  British Journal of Ophthalmology, 106:889 – 892, 2022.
  * [NRV21] Aishwarya Narasimhan, Krishna Prasad Agara Venkatesha Rao, and B VeenaM.  Cgems: A metric model for automatic code generation using gpt-3.  ArXiv, abs/2108.10168, 2021.
  * [OSK21] Alberto Olmo, Sarath Sreedharan, and S. Kambhampati.  Gpt3-to-plan: Extracting plans from text using gpt-3.  ArXiv, abs/2106.07131, 2021.
  * [PC66] John R. Pierce and John B. Carroll.  Language and machines: Computers in translation and linguistics.  1966\.
  * [PP21] George Prodan and Elena Pelican.  Prompt scoring system for dialogue summarization using gpt-3.  2021\.
  * [RNS+18] Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al.  Improving language understanding by generative pre-training.  2018\.
  * [RWC+19] Alec Radford, Jeff Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever.  Language models are unsupervised multitask learners.  2019\.
  * [SAT+22] Juliana Shihadeh, Margareta Ackerman, Ashley Troske, Nicole Lawson, and Edith Gonzalez.  Brilliance bias in gpt-3.  2022 IEEE Global Humanitarian Technology Conference (GHTC), pages 62–69, 2022.
  * [Sch18] Lane Schwartz.  The history and promise of machine translation.  2018\.
  * [SSL22] Emre Sezgin, Joseph W. Sirrianni, and Simon Lin Linwood.  Operationalizing and implementing pretrained, large artificial intelligence linguistic models in the us health care system: Outlook of generative pretrained transformer 3 (gpt-3) as a service model.  JMIR Medical Informatics, 10, 2022.
  * [VSP+17] Ashish Vaswani, Noam M. Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin.  Attention is all you need.  In NIPS, 2017.
  * [Wal22] Joel Walsh.  Lesson plan generation using natural language processing: Prompting best practices with openai’s gpt-3 model (poster 27).  AERA 2022, 2022.
  * [WLS17] Yan Wang, Xiaojiang Liu, and Shuming Shi.  Deep neural solver for math word problems.  In Proceedings of the 2017 Conference on Empirical Methods in Natural Language Processing, pages 845–854, 2017.
  * [WZFH20] Qinzhuo Wu, Qi Zhang, Jinlan Fu, and Xuan-Jing Huang.  A knowledge-aware sequence-to-tree network for math word problem solving.  In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7137–7146, 2020.
  * [XS21] Cao Xiao and Jimeng Sun.  Recurrent neural networks (rnn).  Introduction to Deep Learning for Healthcare, 2021.
  * [ZK22] Mingyu Zong and Bhaskar Krishnamachari.  Solving math word problems concerning systems of equations with gpt-3.  In Proceedings of the Thirteenth AAAI Symposium on Educational Advances in Artificial Intelligence, 2022.
  * [ZWL+20] Jipeng Zhang, Lei Wang, Roy Ka-Wei Lee, Yi Bin, Yan Wang, Jie Shao, and Ee-Peng Lim.  Graph-to-tree learning for solving math word problems.  Association for Computational Linguistics, 2020.


# Posterior Sampling for Continuing Environments

Wanqiao Xu Stanford University, Department of Management Science and
Engineering. Email<EMAIL_ADDRESS>Shi Dong Stanford University,
Department of Electrical Engineering. Email<EMAIL_ADDRESS>Benjamin
Van Roy Stanford University.

###### Abstract

We develop an extension of posterior sampling for reinforcement learning
(PSRL) that is suited for a continuing agent-environment interface and
integrates naturally into agent designs that scale to complex environments.
The approach, continuing PSRL, maintains a statistically plausible model of
the environment and follows a policy that maximizes expected
$\gamma$-discounted return in that model. At each time, with probability
$1-\gamma$, the model is replaced by a sample from the posterior distribution
over environments. For a choice of discount factor that suitably depends on
the horizon $T$, we establish an $\tilde{O}(\tau S\sqrt{AT})$ bound on the
Bayesian regret, where $S$ is the number of environment states, $A$ is the
number of actions, and $\tau$ denotes the reward averaging time, which is a
bound on the duration required to accurately estimate the average reward of
any policy. Our work is the first to formalize and rigorously analyze the
resampling approach with randomized exploration.

##  1 Introduction

A reinforcement learning (RL) agent is faced with the task of interacting with
an unknown environment while trying to maximize the total reward accrued over
time. The environment is commonly modeled as a Markov Decision Process (MDP),
with the transition dynamics hidden from the agent. A core challenge in RL is
how to balance the fundamental tradeoff: when taking exploratory actions, the
agent learns better estimates of the underlying dynamics, but exploiting the
knowledge obtained so far may result in higher immediate return.

A growing literature builds on Thompson sampling [1, 2] to develop randomized
approaches to exploration [3, 4, 5]. While these approaches have proved to be
effective, they have largely been limited to episodic environments. In
particular, the modus oparandi involves randomly sampling a new policy, which
aims to maximize expected return in a statistically plausible model of the
environment, immediately before the start of each episode, and following that
policy throughout the episode. For example, bootstrapped DQN [5] maintains an
ensemble that approximates the posterior distribution of the optimal action
value function $Q_{*}$ and, before each $\ell$th episode, samples a random
element $\hat{Q}_{\ell}$. Then, a greedy policy with respect to
$\hat{Q}_{\ell}$ is executed.

While work on randomized approaches to exploration have focused on episodic
environments, [6, 7] represent two exceptions that treat continuing
environments. The algorithm proposed in [6] resamples an environment from the
environment posterior each time either of the two following criteria holds: 1)
the time elapsed since the last resampling exceeds the interval between the
two most recent resamplings, and 2) the number of visits to any state-action
pair is doubled since the previous resampling. The latter criterion plays an
essential role but is not viable when operating in a complex environment, for
example, addressing an intractably large state space and approximating a
distribution of action value functions using a neural network [5, 8]. In
particular, it is not clear how to efficiently track visitation counts, and
even if that were possible, the counts could be irrelevant since it may even
be rare to visit any individual state more than once. In order to address
large state spaces, [7] considers simply doubling the duration between each
successive pair of resampling times. Although the resulting algorithm
circumvents maintaining visitation counts, their analysis relies heavily on
technical assumptions, without which the regret bound grows linearly with
time. It remains unclear whether a strong performance guarantee is possible
for an approach that simply doubles the duration between successive samples.

We consider an alternative strategy that resamples at each time with a
probability $p$. Here, $p$ is specified as a part of the agent design and
represents how the agent chooses to partition its experience into intervals
that it interprets as trials. With this resampling rule, it is natural to
execute a plan that aims to maximize discounted return with a discount factor
$\gamma=1-p$. Indeed, a simple lemma shows that, with this choice of $\gamma$,
the undiscounted return attained between consecutive resampling times
constitutes an unbiased estimate of the $\gamma$-discounted return of the
policy used. This simple resampling scheme easily integrates into scalable
randomized exploration algorithms. For example, bootstrapped DQN [5] can be
modified to address continuing environments by resampling the action value
function from the prevailing approximate posterior distribution at each time
with probability $p$. As with the original version of bootstrapped DQN, each
executed action is greedy with respect to the most recently sampled action
value function.

The idea of using a discount factor in planning is not new. Many theoretical
works consider $\gamma$ as part of the environment, e.g. they directly analyze
$\gamma$-discounted regret [9, 10]. In contrast, we assess agent performance
in terms of undiscounted regret. Thus, while the discount factor $\gamma$
plays a role in agent design, it does not reflect what we view as the
designer’s objective. This viewpoint aligns with empirical work that regards
the discount factor as a tunable hyperparameter [11, 12]. Our analysis shows
that, while resampling with a probability $p=1-\gamma$ and planning with a
$\gamma$-discounted objective does not lead to vanishing per-timestep regret,
that can be accomplished by increasing $\gamma$ over time.

In this paper, we formalize the aforementioned approach to randomized
exploration – both with fixed and decreasing reset probabilities – and provide
a first rigorous analysis, which establishes regret bounds similar to [6] but
with a resampling criterion much simpler and more scalable than what is
proposed in that paper. Interestingly, our analysis is also simpler than that
of [6] because our resampling criterion is policy-independent. Specifically,
we show that for a choice of discount factor that suitably depends on the
horizon $T$, our algorithm, continuing posterior sampling, satisfies an
$\tilde{O}(\tau S\sqrt{AT})$ regret bound, where $S$ is the number of
environment states, $A$ is the number of actions, and $\tau$ denotes the
reward averaging time [13], which is a bound on the duration required to
accurately estimate the average reward of any policy. This regret bound
matches that established by [6], though their use of “span” replaced by the
reward averaging time $\tau$.

##  2 Problem Formulation

In this section, we begin with an overview of the agent-environment interface
and introduce important notations regarding the environment and agent design.
We define the undiscounted objectives of interest and intermediate planning
objectives at the end of this section.

###  2.1 Environment

We consider the problem of learning to optimize performance through a single
stream of interactions with an unknown environment
$\mathcal{E}=(\mathcal{A},\mathcal{S},\rho)$. Here $\mathcal{A}$ is a finite
action space with cardinality $A$, $\mathcal{S}$ is a finite state space with
cardinality $S$, and $\rho$ is a function that specifies a state transition
probability $\rho(s^{\prime}\mid s,a)$ given a current state $s\in\mathcal{S}$
and action $a\in\mathcal{A}$. Interactions up to time $t$ make up a history
$H_{t}=(S_{0},A_{0},S_{1},A_{1},S_{2},\dots,A_{t-1},S_{t})$, and the agent
selects action $A_{t}$ after observing $S_{t}$. We define the environment and
all random quantities we will consider with respect to a common probability
space $(\Omega,\mathcal{F},\mathbb{P})$. In particular, the environment
$\mathcal{E}$ itself is random, and we use a distribution
$\mathbb{P}(\mathcal{E}\in\cdot)$ to capture the agent designer’s prior belief
over all possible environments. As the history evolves, what can be learned is
represented by the posterior distribution
$\mathbb{P}(\mathcal{E}\in\cdot|H_{t})$. We additionally assume that
$\mathcal{A}$ and $\mathcal{S}$ are deterministic and known, but the
observation probability function $\rho$ is a random variable that the agent
needs to learn. For simplicity, we assume $S_{0}$ is deterministic, but the
same analysis can be easily extended to consider a distribution over initial
states.

###  2.2 Objectives

Reward. We consider the design of an agent to produce desirable outcomes. The
agent’s preferences can be represented by a reward function
$r:\mathcal{S}\times\mathcal{A}\mapsto[0,1]$. After selecting action $A_{t}$
in state $S_{t}$, the agent observes $S_{t+1}$ and receives a deterministic
reward $R_{t+1}=r(S_{t},A_{t})$ bounded in $[0,1]$. We take $r$ to be
deterministic and known for simplicity, but our result easily generalizes to
randomized reward functions.

Policy. The agent specifies its actions via policies. A stochastic policy
$\pi$ can be represented by a probability mass function $\pi(\cdot\mid S_{t})$
that an agent assigns to actions in $\mathcal{A}$ given situational state
$S_{t}$.

Regret. Before we formally define the learning objectives of the agent, we
extend the agent state to account for randomized policies. We consider the
notion of an algorithmic state $Z_{t}$ introduced in [14], which captures the
algorithmic randomness at time $t$. An algorithm is a deterministic sequence
$\\{\mu_{t}\mid t=1,2,\dots\\}$ of functions, each mapping the pair
$(H_{t},Z_{t})$ to a policy. At each time step $t$, the algorithm samples a
random algorithmic state $Z_{t}$ and computes a policy
$\pi_{t}=\mu_{t}(H_{t},Z_{t})$. The algorithm then samples actions
$A_{t}\sim\pi_{t}(\cdot\mid S_{t})$ at times $t$. For a policy $\pi$, we
denote the average reward starting at state $s$ as

$\lambda_{\pi,\mathcal{E}}(s)=\liminf_{T\to\infty}\mathbb{E}_{\pi}\left[\frac{1}{T}\sum_{t=0}^{T-1}R_{t+1}\Bigg{|}\mathcal{E},S_{0}=s\right],$
(1)

where the subscript of the expectation indicates that the reward sequence is
realized by following policy $\pi$, and the subscript $\mathcal{E}$ emphasizes
the dependence of the average reward on the environment $\mathcal{E}$. We also
denote the optimal average reward as

$\lambda_{*,\mathcal{E}}(s)=\sup_{\pi}\lambda_{\pi,\mathcal{E}}(s)\quad\forall
s\in\mathcal{S}.$

We consider weakly-communicating Markovian environments, the most general
subclass of MDPs for which finite time regret bounds are plausible. This
assumption also appears in [6, 15]. We give a formal definition below.

######  Definition 2.1.

(weakly-communicating MDP) An MDP is weakly communicating if there exists a
closed set of states, with each state in that set accessible from every other
state in that set under some deterministic stationary policy, plus a possibly
empty set of states which is transient under every policy.

We remark that the optimal average reward $\lambda_{*,\mathcal{E}}(\cdot)$ is
state-independent under weakly-communicating MDPs. Thus, we override the
notation $\lambda_{*,\mathcal{E}}$ to denote the optimal average reward
$\lambda_{*,\mathcal{E}}(s)$ for all states $s\in\mathcal{S}$. For a policy
$\pi$, we define its regret up to time $T$ to be

$\text{Regret}(T,\pi)\coloneqq\sum_{t=0}^{T-1}\left(\lambda_{*,\mathcal{E}}-R_{t+1}\right).$
(2)

The regret itself is a random variable depending on the random environment
$\mathcal{E}$, the algorithm’s internal random sampling, and random
transitions. We will measure agent performance in terms of regret and its
expected value.

##  3 CPSRL Algorithm

For episodic MDPs, the planning horizon is fixed ahead and known to the agent.
The planning objective is often naturally the cumulative reward over the
finite number of timesteps until the end of each episode. When the environment
is modeled by an MDP with an infinite horizon, planning ahead becomes a
challenge for the agent. One way to address this challenge is to set an
effective finite planning horizon for the agent by maintaining a discount
factor $\gamma\in[0,1)$. Essentially, $\gamma$ dictates the frequency with
which the algorithm resamples an independent environment model used for
planning. Given this discount factor, we divide the original infinite-horizon
learning problem into _pseudo-episodes_ with random lengths, where each
pseudo-episode terminates when the algorithm resamples and computes a new
policy. Concretely, at the beginning of timestep $t=0,1,\dots$, the agent
samples a binary indicator $X_{t}$. If $X_{t}=0$, the agent samples a new
environment $\mathcal{E}$ based on the history $H_{t}$ available at that time,
and marks $t$ as the start of a new pseudo-episode. It then computes a new
policy $\pi$ to follow in this pseudo-episode, and acts according to $\pi$. If
$X_{t}=1$, it continues the current pseudo-episode and follows the most
recently computed policy $\pi$. When $X_{t}\sim\text{Bernoulli}(\gamma)$, one
may interpret $\gamma$ as the _survival probability_ of a pseudo-episode at
timestep $t$. We let $E_{k}$ denote the set of timesteps in the $k$-th pseudo-
episode and $t_{k}$ denote the starting timestep of the $k$-th pseudo-episode.

Discounted value and discounted regret. At each timestep, the agent optimizes
a discounted objective with the aforementioned discount factor $\gamma$. To
formally define this objective, we first introduce matrix notations to avoid
conditioning on zero-probability events. For all $s,s^{\prime}\in\mathcal{S}$
and $a\in\mathcal{A}$, let

$P_{ass^{\prime}}=\rho(s^{\prime}\mid s,a).$

For each policy $\pi$, we also define transition probabilities

$P_{\pi ss^{\prime}}=\sum_{a\in\mathcal{A}}\pi(a\mid s)P_{ass^{\prime}}.$

With this notation, we regard $P_{a}$ and $P_{\pi}$ as $S\times S$ stochastic
matrices, and $P_{as}$ as $S$-dimensional vectors. Furthermore, for each
$s\in\mathcal{S}$ and $a\in\mathcal{A}$, we define

$r_{as}=r(s,a),$

and for each policy $\pi$,

$r_{\pi s}=\sum_{a\in\mathcal{A}}\pi(a\mid s)r_{as}.$

Both $r_{a}$ and $r_{\pi}$ can also be viewed as $S$-dimensional vectors.

While rewards represent agent preferences over actions in a single step, the
agent may be interested in optimizing for returns accumulated over multiple
steps. We define the value of a policy $\pi$ in the context of pseudo-episodes
introduced above. For each environment $\mathcal{E}$ and policy $\pi$, we
define the $\gamma$-discounted value function
$V^{\gamma}_{\pi,\mathcal{E}}\in\mathbb{R}^{S}$ of $\pi$ in $\mathcal{E}$ as

$V_{\pi,\mathcal{E}}^{\gamma}\coloneqq\mathbb{E}\left[\sum_{h=0}^{H-1}P_{\pi}^{h}r_{\pi}\mid\mathcal{E}\right]=\mathbb{E}\left[\sum_{h=0}^{\infty}\gamma^{h}P_{\pi}^{h}r_{\pi}\mid\mathcal{E}\right],$
(3)

where the expectation is over the random episode length $H$. Since a pseudo-
episode terminates at time $t$ when the independently sampled
$X_{t}\sim\text{Bernoulli}(\gamma)$ takes value 0, its length $H$ follows a
binomial distribution with parameter $\gamma$. The second equality above is a
direct consequence of this observation. A policy $\pi$ is said to be optimal
for the environment $\mathcal{E}$ if
$V_{\pi,\mathcal{E}}^{\gamma}=\sup_{\pi^{\prime}}V_{\pi^{\prime},\mathcal{E}}^{\gamma}$.
For an optimal policy $\pi$, we also write its value
$V_{*,\mathcal{E}}^{\gamma}(s)\equiv V_{\pi,\mathcal{E}}^{\gamma}(s)$ as the
optimal value. Furthermore, we denote an optimal policy with respect to
$V_{*,\mathcal{E}}^{\gamma}$ for each $\mathcal{E}$ as $\pi^{\mathcal{E}}$,
which will be useful in the analysis. Note that $V_{\pi,\mathcal{E}}^{\gamma}$
satisfies the Bellman equation

$\displaystyle V_{\pi,\mathcal{E}}^{\gamma}=r_{\pi}+\gamma
P_{\pi}V_{\pi,\mathcal{E}}^{\gamma}.$ (4)

Reward averaging time. We consider the notion of reward averaging times
$\tau_{\pi,\mathcal{E}}$ of policies introduced in [13] and derive regret
bounds that depend on $\tau_{\pi,\mathcal{E}}$.

######  Definition 3.1.

(reward averaging time) The reward averaging time $\tau_{\pi,\mathcal{E}}$ of
a policy $\pi$ is the smallest value $\tau\in[0,\infty)$ such that

$\left|\mathbb{E}_{\pi}\left[\sum_{t=0}^{T-1}R_{t+1}\mid\mathcal{E},S_{0}=s\right]-T\cdot\lambda_{\pi,\mathcal{E}}(s)\right|\leq\tau,$

for all $T\geq 0$ and $s\in\mathcal{S}$.

When $\pi^{*}$ is an optimal policy for $\mathcal{E}$,
$\tau_{*,\mathcal{E}}\coloneqq\tau_{\pi^{*},\mathcal{E}}$ is equivalent to the
notion of span in [16]. We define $\Omega_{*}$ to be the set of all weakly
communicating MDPs $\mathcal{E}$ and further make the following assumption on
the prior distribution $\mathbb{P}(\mathcal{E}\in\cdot)$. This assumption says
that we focus on weakly communicating MDPs with bounded reward averaging time.

######  Assumption 3.2.

There exists $\tau<\infty$ such that the prior distribution over possible
environments $\mathbb{P}(\mathcal{E}\in\cdot)$ satisfies

$\mathbb{P}\Big{(}\mathcal{E}\in\Omega_{*},\
\tau_{*,\mathcal{E}}\leq\tau\Big{)}=1.$

Below, we restate an important lemma, Lemma 2 in [13], that relates
$\lambda_{\pi,\mathcal{E}}$, $\tau_{\pi,\mathcal{E}}$, and
$V_{\pi,\mathcal{E}}^{\gamma}$.

######  Lemma 3.3.

For all $\pi$, $s\in\mathcal{S}$ and $\gamma\in[0,1)$,

$\left|V_{\pi,\mathcal{E}}^{\gamma}(s)-\frac{\lambda_{\pi,\mathcal{E}}(s)}{1-\gamma}\right|\leq\tau_{\pi,\mathcal{E}}.$

We note again that for weakly communicating $\mathcal{E}\in\Omega_{*}$, the
optimal average reward is state independent, i.e.,
$\lambda_{*,\mathcal{E}}=\lambda_{\pi_{*},\mathcal{E}}(s)$ for all
$s\in\mathcal{S}$. Thus, under Assumption 3.2, we have

$\left|V^{\gamma}_{*,\mathcal{E}}(s)-V^{\gamma}_{*,\mathcal{E}}(s^{\prime})\right|\leq
2\tau_{*,\mathcal{E}}\leq 2\tau$ (5)

almost surely for all $s,s^{\prime}\in\mathcal{S}$.

Discounted regret. Although the regret we eventually hope to analyze is
defined by equation 2, we also consider a discounted version of the regret to
aid our analysis. To analyze the performance of our algorithm over $T$
timesteps, we consider $K=\arg\max\\{k:t_{k}\leq T\\}$ as the number of
pseudo-episodes until time $T$. In our subsequent analysis, we adopt the
convention that $t_{K+1}=T+1$. To get a bound for general $T$, we can always
fill in the rest of the timesteps to make a full pseudo-episode, but the
asymptotic rate stays the same. Moreover, it is easy to see that for all
$\gamma\in[0,1)$, $\mathbb{E}[K]\leq(1-\gamma)T+1$. Given a discount factor
$\gamma\in[0,1)$, we define the $\gamma$-discounted regret up to time $T$ to
be

$\text{Regret}_{\gamma}(T,\pi)\coloneqq\sum_{k=1}^{K}\Delta_{k},$ (6)

where $K=\arg\max\\{k:t_{k}\leq T\\}$, and $\Delta_{k}$ is the regret over
pseudo-episode $k$, defined as

$\Delta_{k}=V_{*,\mathcal{E}}^{\gamma}(s_{k,1})-V_{\pi_{k},\mathcal{E}}^{\gamma}(s_{k,1}),$

with
$V_{*,\mathcal{E}}^{\gamma}=V_{\pi^{*},\mathcal{E}}^{\gamma}=V_{\pi^{\mathcal{E}},\mathcal{E}}^{\gamma}$,
$\pi_{k}\sim\mu_{k}(H_{t_{k}})$, $A_{t}\sim\pi_{k}(\cdot\mid S_{t})$,
$S_{t+1}\sim\rho(\cdot|S_{t},A_{t})$, and $R_{t}=r(S_{t},A_{t},S_{t+1})$ for
$t\in E_{k}$. Note that similar to the regret, the discounted regret is also a
random variable depending on the random environment $\mathcal{E}$, the
algorithm’s internal random sampling, random transitions, and additionally the
random lengths of the pseudo-episodes.

Empirical estimates. Finally, we define the empirical transition probabilities
used by the algorithm. Let
$N_{t}(s,a)=\sum_{\tau=1}^{t}\mathbbm{1}\\{(S_{\tau},A_{\tau})=(s,a)\\}$ be
the number of times action $a$ has been sampled in state $s$ up to timestep
$t$. For every pair $(s,a)$ with $N_{t_{k}}(s,a)>0$, the empirical transition
probabilities up to pseudo-episode $k$ are

$\displaystyle\hat{\rho}_{k}(s^{\prime}\mid s,a)$
$\displaystyle=\sum_{\ell=1}^{k-1}\sum_{t\in
E_{k}}\frac{\mathbbm{1}\\{(S_{t},A_{t},S_{t+1})=(s,a,s^{\prime})\\}}{N_{t_{k}}(s,a)}$
(7)

for all $s^{\prime}\in\mathcal{S}$. If the pair $(s,a)$ has never been sampled
before pseudo-episode $k$, we define $\hat{\rho}_{k}(s^{\prime}\mid s,a)=1$
for a random $s^{\prime}\in\mathcal{S}$, and
$\hat{\rho}_{k}(s^{\prime\prime}\mid s,a)=0$ for
$s^{\prime\prime}\in\mathcal{S}\setminus\\{s^{\prime}\\}$. The corresponding
matrix notation $\hat{P}^{k}$ are defined analogously.

###  3.1 The Algorithm

We present the Continuing Posterior Sampling for Reinforcement Learning
(CPSRL) algorithm in Algorithm 1, which extends PSRL [3] to the infinite
horizon setting with $\gamma$-discounted planning. The algorithm begins with a
prior distribution over environments with actions $\mathcal{A}$ and state
space $\mathcal{S}$. In addition, the algorithm takes an indicator $X_{1}=0$
and assumes a discount factor $\gamma$. At the start of each timestep $t$, if
the indicator $X_{t}=0$, CPSRL samples an environment
$\mathcal{E}_{t}=(\mathcal{A},\mathcal{S},\rho_{t})$ from the posterior
distribution conditioned on the history $H_{t}$ available at that time, and
mark $t$ as the start of a new pseudo-episode. It then computes and follows
the policy $\pi_{t}=\pi^{\mathcal{E}_{t}}$ at time $t$. Otherwise, if
$X_{t}=1$, it sticks to the policy $\pi_{t}=\pi_{t-1}$ at time $t$ and adds
step $t$ to the current pseudo-episode. Then $X_{t+1}$ is drawn from a
Bernoulli distribution with parameter $\gamma$ to be used in the next
timestep.

Compared with the vanilla PSRL, CPSRL simply adds an independent Bernoulli
random number generator to determine when to resample. Although CPSRL is not
designed to be implemented in practice per se, we note that such resampling
scheme brings both scalability and generalizability. For example, when the
environment has an extremely large state or action space, e.g. Atari games
[11], prior resampling methods relying on state-action visitation statistics
[6] require a huge look-up table, while the resampling method in CPSRL can
still be easily applied, with little computational overhead.

Data: Prior distribution $f$, discount factor $\gamma$, total learning time
$T$

initialize $t=1$, $k=1$, $X_{1}=0$

for  _$t\leq T$_ do

if  _$X_{t}=0$_ then

$t_{k}\leftarrow t$

sample $\mathcal{E}^{k}\sim f(\cdot\mid H_{t_{k}})$

compute $\pi_{k}=\pi^{\mathcal{E}^{k}}$

$k\leftarrow k+1$

end if

sample and apply $A_{t}\sim\pi_{k}(\cdot\mid S_{t})$

observe $R_{t+1}$ and $S_{t+1}$

$t\leftarrow t+1$

sample $X_{t+1}\sim{\rm Bernoulli}\left(\gamma\right)$

end for

Algorithm 1 CPSRL (Continuing Posterior Sampling for Reinforcement Learning)

##  4 Main Results

We present our main results in this section. Theorem 4.1 establishes that PSRL
with discounted planning satisfies a polynomial Bayesian regret bound for
infinite-horizon tabular MDP environments. The bounds for the expected regret
are of order $\tilde{O}(\tau S\sqrt{AT})$, matching the regret bound for TSDE
in [6], but achieved by a simple and elegant algorithm without additional
episode termination criteria. Here, we remark briefly that the discount factor
in Algorithm 1 is not constrained to be constant. The bound in Theorem 4.1
involves letting $\gamma$ depend on MDP parameters $T,S,A$ with a suitable
rate which we discuss in more detail in Section 5.1.

######  Theorem 4.1.

The expected regret for Algorithm 1 with $\gamma$ satisfying
$\frac{1}{1-\gamma}=\sqrt{\frac{T}{SA}}$ is bounded as

$\mathbb{E}\left[\text{\emph{Regret}}(T,\pi)\right]=\tilde{O}\left(\tau
S\sqrt{AT}\right).$

Note that our main theorem bounds the regret with respect to the optimal
average reward, and thus has no dependence on the discount factor $\gamma$,
which, as we emphasized, is only a design factor within the algorithm. For the
purpose of the analysis, we utilize the $\gamma$-discounted regret defined in
equation 6 and prove the following intermediate bound for the discounted
regret.

######  Theorem 4.2.

$\displaystyle\mathbb{E}\left[\text{\emph{Regret}}_{\gamma}(T,\pi)\right]\leq(4\tau+2)S\sqrt{28AT\log(2SAT)}+\frac{SA}{1-\gamma}\log\left(\frac{1}{1-\gamma}\log\left(\frac{2T}{1-\gamma}\right)\right)+\frac{1}{2}+\frac{2}{1-\gamma}.$
(8)

##  5 Analysis

As discussed in [3], a key property of posterior sampling algorithms is that
for any function $g$ measurable with respect to the sigma algebra generated by
the history,
$\mathbb{E}[g(\mathcal{E})|H_{t}]=\mathbb{E}[g(\mathcal{E}^{t})|H_{t}]$ if
$\mathcal{E}^{t}$ is sampled from the posterior distribution at time $t$.
Under our pseudo-episode construction, we state a stopping-time version of
this property similar to the one in [6].

######  Lemma 5.1.

If $f$ is the distribution of $\mathcal{E}$, then for any
$\sigma(H_{t_{k}})$-measurable function $g$, we have

$\mathbb{E}[g(\mathcal{E})|H_{t_{k}}]=\mathbb{E}[g(\mathcal{E}^{k})|H_{t_{k}}],$
(9)

where the expectation is taken over $f$.

We include a proof in Appendix B.1 for completeness. We let
$V^{\gamma}_{\pi_{k},k}=V^{\gamma}_{\pi_{k},\mathcal{E}^{k}}$ denote the value
function of $\pi_{k}$, the policy employed by CPSRL, under the sampled
environment $\mathcal{E}^{k}$, and define

$\tilde{\Delta}_{k}=V^{\gamma}_{\pi_{k},k}(s_{k,1})-V^{\gamma}_{\pi_{k},\mathcal{E}}(s_{k,1})$

as the difference in performance of $\pi_{k}$ under $\mathcal{E}^{k}$ and the
true environment $\mathcal{E}$. The next lemma allows us to evaluate regret in
terms of $\tilde{\Delta}_{k}$, which we can analyze using the known sampled
environment and our observation from the true environment, whereas it is
typically hard to directly analyze $\Delta_{k}$ since we do not know what the
optimal policy $\pi^{*}=\pi^{\mathcal{E}}$ is.

######  Lemma 5.2.

$\mathbb{E}\left[\sum_{k=1}^{K}\Delta_{k}\right]=\mathbb{E}\left[\sum_{k=1}^{K}\tilde{\Delta}_{k}\right].$
(10)

###### Proof.

The claim follows by applying Lemma 5.1 and a similar argument as that in
Theorem 2 in [3]. ∎

We prove a value decomposition lemma that allows us to express the difference
in values of $\pi_{k}$ in the true environment $\mathcal{E}$ and sampled
environment $\mathcal{E}^{k}$ in terms of a sum of Bellman errors over one
stochastic pseudo-episode.

######  Lemma 5.3 (Value decomposition).

For any environment $\hat{\mathcal{E}}$ and any policy $\pi$,

$\displaystyle\mathbb{E}\left[V_{\pi,\mathcal{E}}^{\gamma}(s_{0})-V_{\pi,\hat{\mathcal{E}}}^{\gamma}(s_{0})\mid\mathcal{E},\hat{\mathcal{E}}\right]=\mathbb{E}\left[\sum_{t=0}^{\eta-1}\gamma\left\langle
P_{\pi(s_{t})s_{t}}-\hat{P}_{\pi(s_{t})s_{t}},V_{\pi,\hat{\mathcal{E}}}^{\gamma}\right\rangle\mid\mathcal{E},\hat{\mathcal{E}},\pi\right],$

where $\eta$ is the random length of a pseudo-episode, and the expectation is
over the distribution of $\eta$, conditioned on the sampled state trajectory
$s_{0},s_{1},\dots$ drawn from following $\pi$ in the environment
$\mathcal{E}$.

###### Proof.

Expanding the right hand side by the tower property, we get

$\displaystyle\quad\mathbb{E}\left[\sum_{t=0}^{\eta-1}\gamma\left\langle
P_{\pi(s_{t})s_{t}}-\hat{P}_{\pi(s_{t})s_{t}},V_{\pi,\hat{\mathcal{E}}}^{\gamma}\right\rangle\mid\mathcal{E},\hat{\mathcal{E}},\pi\right]$
$\displaystyle=\sum_{H=1}^{\infty}\mathbb{E}\left[\sum_{t=0}^{H-1}\gamma\left\langle
P_{\pi(s_{t})s_{t}}-\hat{P}_{\pi(s_{t})s_{t}},V_{\pi,\hat{\mathcal{E}}}^{\gamma}\right\rangle\mid\mathcal{E},\hat{\mathcal{E}},\pi\right]\cdot\gamma^{H-1}(1-\gamma)$
$\displaystyle=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t+1}\left\langle
P_{\pi(s_{t})s_{t}}-\hat{P}_{\pi(s_{t})s_{t}},V_{\pi,\hat{\mathcal{E}}}^{\gamma}\right\rangle\mid\mathcal{E},\hat{\mathcal{E}},\pi\right].$

By applying Bellman equations recursively, the value function difference in
the left hand side can be expressed as

$\displaystyle
V_{\pi,\mathcal{E}}^{\gamma}(s_{0})-V_{\pi,\hat{\mathcal{E}}}^{\gamma}(s_{0})$
$\displaystyle=\sum_{t=0}^{\infty}\gamma^{t+1}\langle
P_{\pi(s_{t})s_{t}}-\hat{P}_{\pi(s_{t})s_{t}},V_{\pi,\mathcal{E}}^{\gamma}\rangle+\sum_{t=0}^{\infty}d_{t},$

where

$\displaystyle d_{i}\coloneqq\gamma\langle
P_{\pi(s_{i})s_{i}},V_{\pi,\mathcal{E}}^{\gamma}-V_{\pi,\hat{\mathcal{E}}}^{\gamma}\rangle-\gamma\left(V_{\pi,\mathcal{E}}^{\gamma}(s_{i+1})-V_{\pi,\hat{\mathcal{E}}}^{\gamma}(s_{i+1})\right).$

In state $s_{i}$ under policy $\pi$, the expected value of $\gamma\langle
P_{\pi(s_{i})s_{i}},V_{\pi,\mathcal{E}}^{\gamma}-V_{\pi,\hat{\mathcal{E}}}^{\gamma}\rangle$
is exactly
$\gamma\left(V_{\pi,\mathcal{E}}^{\gamma}(s_{i+1})-V_{\pi,\hat{\mathcal{E}}}^{\gamma}(s_{i+1})\right)$,
so conditioning on the true environment $\mathcal{E}$ and the sampled
environment $\hat{\mathcal{E}}$, the expectation of $\sum_{t=0}^{\infty}d_{t}$
is zero. Taking the expectation conditioned on $\mathcal{E},\hat{\mathcal{E}}$
and $\pi$, our claim is proved. ∎

At the start of each pseudo-episode $k$, we consider a confidence set

$\mathcal{M}_{k}=\left\\{(\mathcal{A},\mathcal{O},\rho):\left\|P_{as}-\hat{P}_{as}\right\|_{1}\leq\beta_{k}(s,a)~{}~{}\forall(s,a)\right\\}$

where

$\displaystyle\beta_{k}(s,a)$
$\displaystyle=\sqrt{\frac{14S\log(2SAKt_{k})}{\max\\{N_{t_{k}}(s,a),1\\}}}.$

The following lemma bounds the probability that the true environment falls
outside of the confidence set $\mathcal{M}_{k}$.

######  Lemma 5.4.

$\mathbb{P}\left(\mathcal{E}\notin\mathcal{M}_{k}\right)\leq\frac{1}{K}.$

The proof follows standard concentration arguments, which we defer to Appendix
B.2. We let

$m=\frac{1}{1-\gamma}\log\left(\frac{2K}{1-\gamma}\right)$

be a high probability upper bound for the length of each episode $E_{k}$,
$k=1,\dots,K$. Since $\tilde{\Delta}_{k}\leq\frac{1}{1-\gamma}$, we can
decompose the regret as

$\displaystyle\sum_{k=1}^{K}$
$\displaystyle\tilde{\Delta}_{k}\leq\sum_{k=1}^{K}\tilde{\Delta}_{k}\mathbbm{1}_{\\{\mathcal{E},\mathcal{E}^{k}\in\mathcal{M}_{k}\\}}\cdot\mathbbm{1}_{\\{|E_{k}|\leq
m\\}}+\frac{1}{1-\gamma}\sum_{k=1}^{K}\left[\mathbbm{1}_{\\{|E_{k}|>m\\}}+\mathbbm{1}_{\\{\mathcal{E}\notin\mathcal{M}_{k}\\}}+\mathbbm{1}_{\\{\mathcal{E}^{k}\notin\mathcal{M}_{k}\\}}\right].$

Note that $\mathcal{M}_{k}$ is $\sigma(H_{t_{k}})$-measurable, so by Lemma
5.1,

$\mathbb{E}[\mathbbm{1}_{\\{\mathcal{E}\notin\mathcal{M}_{k}\\}}\mid
H_{t_{k}}]=\mathbb{E}[\mathbbm{1}_{\\{\mathcal{E}^{k}\notin\mathcal{M}_{k}\\}}\mid
H_{t_{k}}].$

Therefore,

$\displaystyle\mathbb{E}\left[\sum_{k=1}^{K}\tilde{\Delta}_{k}\right]$
$\displaystyle\leq\mathbb{E}\left[\sum_{k=1}^{K}\tilde{\Delta}_{k}\mathbbm{1}_{\\{\mathcal{E},\mathcal{E}^{k}\in\mathcal{M}_{k}\\}}\cdot\mathbbm{1}_{\\{|E_{k}|\leq
m\\}}\right]+\frac{1}{1-\gamma}\mathbb{E}\left[\sum_{k=1}^{K}\mathbbm{1}_{\\{|E_{k}|>m\\}}\right]$
$\displaystyle\quad+\frac{2}{1-\gamma}\cdot\mathbb{E}\left[\sum_{k=1}^{K}\mathbbm{1}_{\\{\mathcal{E}\notin\mathcal{M}_{k}\\}}\right].$
(11)

The third term can be bounded by $\frac{2}{1-\gamma}$ via Lemma 5.4. In what
follows, we show how to bound the second and the first term.

Second term. For the second term, since $|E_{k}|$ follows a geometric
distribution with parameter $1-\gamma$, applying the inequality
$(1+\frac{x}{n})^{n}\leq e^{x}$ by taking $n=\frac{1}{1-\gamma}\geq 1,x=-1$,
we have

$\displaystyle\frac{1}{1-\gamma}\mathbb{E}\left[\sum_{k=1}^{K}\mathbbm{1}_{\\{|E_{k}|>m\\}}\right]$
$\displaystyle=\frac{1}{1-\gamma}\sum_{k=1}^{K}\gamma^{m}=\frac{1}{1-\gamma}\sum_{k=1}^{K}\gamma^{\frac{1}{1-\gamma}\log(2K/(1-\gamma))}\leq\frac{1}{1-\gamma}\sum_{k=1}^{K}2e^{-\log\left(\frac{2K}{1-\gamma}\right)}=\frac{1}{2}.$

First term. It remains to bound the first term in equation 5. In Appendix A,
we provide a detailed proof for the bound

$\displaystyle\mathbb{E}\left[\sum_{k=1}^{K}\tilde{\Delta}_{k}\mathbbm{1}_{\\{\mathcal{E},\mathcal{E}^{k}\in\mathcal{M}_{k}\\}}\cdot\mathbbm{1}_{\\{|E_{k}|\leq
m\\}}\right]\leq 4\tau\cdot
S\sqrt{28AT\log(2SAT)}+\frac{SA}{1-\gamma}\log\left(\frac{1}{1-\gamma}\log\left(\frac{2T}{1-\gamma}\right)\right).$

We now conclude the proof of Theorem 4.2 below.

###### Proof of Theorem 4.2..

Combining the bound for each term in equation 5, we have

$\displaystyle\mathbb{E}\left[\sum_{k=1}^{K}\tilde{\Delta}_{k}\right]\leq
4\tau
S\sqrt{28AT\log(2SAT)}+\frac{SA}{1-\gamma}\log\left(\frac{1}{1-\gamma}\log\left(\frac{2T}{1-\gamma}\right)\right)+\frac{1}{2}+\frac{2}{1-\gamma}.$

The claim follows from Lemma 5.2. ∎

###  5.1 Average Reward Regret

We have treated $\gamma$ as a constant discount factor so far, resulting in a
regret bound in equation 6 that scales linearly with $\frac{1}{1-\gamma}$,
ignoring logarithmic factors. However, the CPSRL algorithm does not constrain
$\gamma$ to be a constant during the learning process, i.e. we are able to
allow the discount factor to increase over time, accounting for the growing
horizon. Specifically, at each time step $t$, we can consider a discount
factor $\gamma_{t}$, and CPSRL resamples a new environment with probability
$1-\gamma_{t}$. If resampling happens, the agent switches to the optimal
policy in the resampled environment maximizing the $\gamma_{t}$-discounted
cumulative reward. Otherwise, the agent keeps following the previous policy.
If $\gamma_{t}$ increases with $t$, the agent is effectively planning over a
longer horizon as interactions continue, and as Theorem 4.2 justifies, the
agent’s performance should always keep up with that of the optimal policy in
the environment, regardless of the planning horizon.

Note that, although Theorem 4.2 provides a sublinear upper bound for the
discounted regret with a fixed discount factor $\gamma$, we are ultimately
interested in the performance shortfall with respect to the optimal average-
reward policy. To obtain a sublinear upper bound for the latter, we employ
such time-dependent discount factors discussed above, which allows us to show
Theorem 4.1, a regret bound for the Bayesian regret that does not depend on a
discount factor.

###### Proof of Theorem 4.1.

To better represent the dependence on $K$, set

$\mathcal{R}(K,\pi)\coloneqq\text{Regret}(T,\pi),$

where $T$ is at the end of the $K$-th pseudo-episode. The expected regret can
be written as

$\displaystyle\mathbb{E}\left[\mathcal{R}(K,\pi)\right]=\mathbb{E}_{\pi}\left[\sum_{k=1}^{K}\sum_{t\in
E_{k}}(\lambda_{*}-R_{t})\right]=\mathbb{E}_{\pi}\left[\sum_{k=1}^{K}|E_{k}|\lambda_{*}-\sum_{k=1}^{K}\sum_{t\in
E_{k}}R_{t}\right].$

Adding and subtracting the optimal discounted value,

$\displaystyle\mathbb{E}\left[\mathcal{R}(K,\pi)\right]=\underbrace{\mathbb{E}\left[\sum_{k=1}^{K}(|E_{k}|\lambda_{*}-V_{*,\mathcal{E}}^{\gamma}(s_{k,1}))\right]}_{(a)}+\underbrace{\mathbb{E}\left[\sum_{k=1}^{K}\left[V_{*,\mathcal{E}}^{\gamma}(s_{k,1})-V_{\pi_{k},\mathcal{E}}^{\gamma}(s_{k,1})\right]\right]}_{(b)}.$

Since the length of each pseudo-episode is independent of the policy or the
environment itself with mean $\frac{1}{1-\gamma}$, term (a) is the difference
between the optimal average reward, weighted by the effective horizon, and the
optimal discounted reward

$\mathbb{E}\left[\sum_{k=1}^{K}(\frac{1}{1-\gamma}\lambda_{*}-V^{\gamma}_{*,\mathcal{E}}(s_{k,1}))\right].$

By Lemma 3.3,

$\displaystyle\mathbb{E}\left[\sum_{k=1}^{K}\left|\frac{1}{1-\gamma}\lambda_{*}-V_{*,\mathcal{E}}^{\gamma}(s_{k,1})\right|\right]$
$\displaystyle\leq\tau\mathbb{E}[K].$

The expectation (b) is the sum of differences between the optimal discounted
value and the discounted value of the deployed policy over $K$ pseudo-
episodes. From equation 6 we can see that (b) is exactly
$\mathbb{E}\left[\text{Regret}_{\gamma}(K,\pi)\right]$. By Theorem 4.2, we
have that the regret can be bounded in terms of $\gamma$ as

$\displaystyle\mathbb{E}\left[\mathcal{R}(K,\pi)\right]$
$\displaystyle\leq\tau\mathbb{E}[K]+\tilde{O}\left(4\tau
S\sqrt{AT}+\frac{SA}{1-\gamma}\right)\leq(1-\gamma)T\tau+\tau+\tilde{O}\left(4\tau
S\sqrt{AT}+\frac{SA}{1-\gamma}\right).$

If we assume the knowledge of $T$, optimizing for $\gamma$, the best rate in
terms of $T$ can be achieved by setting

$\frac{1}{1-\gamma}=\sqrt{\frac{T}{SA}},$

and the final bound becomes

$\displaystyle\mathbb{E}[\text{Regret}(T,\pi)]=\mathbb{E}\left[\mathcal{R}(K,\pi)\right]\leq\tau\sqrt{SAT}+\tilde{O}\left(4\tau
S\sqrt{AT}\right)=\tilde{O}\left(\tau S\sqrt{AT}\right).$

If the total learning horizon $T$ is unknown, we can utilize a classical
doubling trick argument that is common in the design of online learning
algorithms [17]. The idea is to divide the learning horizon into time
intervals of the form $[2^{k},2^{k+1})$ and set

$\frac{1}{1-\gamma_{t}}=\sqrt{\frac{2^{k+1}}{SA}}$

for $t\in[2^{k},2^{k+1})$, $k\in\mathbb{N}$.

∎

##  6 Conclusion

We proposed a novel algorithm design extending PSRL to the setting where the
environment does not have a reset schedule, and the agent has to plan over a
possibly infinite horizon. We establish theoretically that our algorithm,
CPSRL, enjoys a regret upper bound that is close to the theoretical
optimality. Notably, CPSRL only relies on a single Bernoulli random number
generator to resample the environment, as opposed to the complex episode-
stopping schemes in prior works. Such design principle can be readily applied
to general environments with large state spaces. Moreover, CPSRL also
highlights the role of discount factor in agent design, as the discount factor
is no longer considered as a part of the learning target, but mainly acts as a
tool for the agent to dynamically adjust its planning horizon. As such, this
work might provide an important step towards understanding discount factors,
which have seen wide popularity in practical RL applications.

## References

  * [1] William R. Thompson.  On the likelihood that one unknown probability exceeds another in view of the evidence of two samples.  Biometrika, 25:285–294, 1933.
  * [2] Daniel J. Russo, Benjamin Van Roy, Abbas Kazerouni, Ian Osband, and Zheng Wen.  A tutorial on Thompson sampling.  Foundations and Trends® in Machine Learning, 11(1):1–96, 2018\.
  * [3] Ian Osband, Daniel Russo, and Benjamin Van Roy.  (More) efficient reinforcement learning via posterior sampling.  In Advances in Neural Information Processing Systems, 2013.
  * [4] Ian Osband, Benjamin Van Roy, and Zheng Wen.  Generalization and exploration via randomized value functions.  In International Conference on International Conference on Machine Learning, 2016.
  * [5] Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy.  Deep exploration via bootstrapped DQN.  In Advances in Neural Information Processing Systems, 2016.
  * [6] Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar, and Rahul Jain.  Learning unknown Markov decision processes: A Thompson sampling approach.  In Advances in Neural Information Processing Systems, 2017.
  * [7] Georgios Theocharous, Zheng Wen, Yasin Abbasi Yadkori, and Nikos Vlassis.  Scalar posterior sampling with applications.  In Advances in Neural Information Processing Systems, 2018.
  * [8] Vikranth Dwaracherla, Xiuyuan Lu, Morteza Ibrahimi, Ian Osband, Zheng Wen, and Benjamin Van Roy.  Hypermodels for exploration.  In International Conference on Learning Representations, 2020.
  * [9] Tor Lattimore and Marcus Hutter.  PAC bounds for discounted MDPs.  In International Conference on Algorithmic Learning Theory, 2012\.
  * [10] Yuanhao Wang, Kefan Dong, Xiaoyu Chen, and Liwei Wang.  Q-learning with UCB exploration is sample efficient for infinite-horizon MDP.  In International Conference on Learning Representations, 2020.
  * [11] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Bellemare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charlie Beattie, Amir Sadik, Ioannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis.  Human-level control through deep reinforcement learning.  Nature, 518:529–533, 2015.
  * [12] Vincent François-Lavet, Raphaël Fonteneau, and Damien Ernst.  How to discount deep reinforcement learning: Towards new dynamic strategies.  In Advances in Neural Information Processing Systems, 2015.
  * [13] Shi Dong, Benjamin Van Roy, and Zhengyuan Zhou.  Simple agent, complex environment: Efficient reinforcement learning with agent states.  Journal of Machine Learning Research, 23:1–54, 2022.
  * [14] Xiuyuan Lu, Benjamin Van Roy, Vikranth Dwaracherla, Morteza Ibrahimi, Ian Osband, and Zheng Wen.  Reinforcement learning, bit by bit.  arXiv preprint arXiv:2103.04047, 2021.
  * [15] Shipra Agrawal and Navin Goyal.  Further optimal regret bounds for Thompson sampling.  In International Conference on Artificial Intelligence and Statistics, 2013.
  * [16] Peter L. Bartlett and Ambuj Tewari.  REGAL: A regularization based algorithm for reinforcement learning in weakly communicating MDPs.  In Conference on Uncertainty in Artificial Intelligence, 2009.
  * [17] Junzi Zhang, Jongho Kim, Brendan O’Donoghue, and Stephen Boyd.  Sample efficient reinforcement learning with REINFORCE.  In AAAI Conference on Artificial Intelligence, 2020.
  * [18] Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdú, and Marcelo J. Weinberger.  Inequalities for the L1 deviation of the empirical distribution.  In Hewlett-Packard Labs Technical Reports, 2003.

##  Appendix A Bounding the sum of confidence set widths

We are interested in bounding

$\mathbb{E}\left[\sum_{k=1}^{K}\tilde{\Delta}_{k}\mathbbm{1}_{\\{\mathcal{E},\mathcal{E}^{k}\in\mathcal{M}_{k}\\}}\cdot\mathbbm{1}_{\\{|E_{k}|\leq
m\\}}\right].$

###### Proof.

For each $k$, we define the event

$\mathcal{B}_{k}\coloneqq\left\\{N_{t_{k+1}-1}(s,a)+1\leq
2N_{t_{k}}(s,a)~{}\text{for
all}~{}(s,a)\in\mathcal{S}\times\mathcal{A}\right\\}.$

Then $\mathcal{B}_{k}^{c}=\\{N_{t_{k+1}-1}(s,a)\geq
2N_{t_{k}}(s,a)~{}\text{for some}~{}(s,a)\in\mathcal{S}\times\mathcal{A}\\}$.

Following a similar strategy as in [3], we can write

$\displaystyle\mathbb{E}\left[\sum_{k=1}^{K}\tilde{\Delta}_{k}\mathbbm{1}_{\\{\mathcal{E},\mathcal{E}^{k}\in\mathcal{M}_{k}\\}}\cdot\mathbbm{1}_{\\{|E_{k}|\leq
m\\}}\right]$
$\displaystyle\leq\mathbb{E}\left[\sum_{k=1}^{K}\tilde{\Delta}_{k}\mathbbm{1}_{\\{\mathcal{E},\mathcal{E}^{k}\in\mathcal{M}_{k}\\}}\cdot\mathbbm{1}_{\mathcal{B}_{k}}\right]+\mathbb{E}\left[\sum_{k=1}^{K}\tilde{\Delta}_{k}\mathbbm{1}_{\\{|E_{k}|\leq
m\\}}\cdot\mathbbm{1}_{\mathcal{B}_{k}^{c}}\right]$
$\displaystyle\leq\mathbb{E}\left[\sum_{k=1}^{K}\mathbb{E}\left[\tilde{\Delta}_{k}\mid\mathcal{E},\mathcal{E}^{k}\right]\mathbbm{1}_{\\{\mathcal{E},\mathcal{E}^{k}\in\mathcal{M}_{k}\\}}\cdot\mathbbm{1}_{\mathcal{B}_{k}}\right]+\mathbb{E}\left[\sum_{k=1}^{K}\tilde{\Delta}_{k}\mathbbm{1}_{\\{|E_{k}|\leq
m\\}}\cdot\mathbbm{1}_{\mathcal{B}_{k}^{c}}\right].$

The event $N_{t_{k+1}-1}(s,a)\geq 2N_{t_{k}}(s,a)$ can happen in at most $\log
m$ episodes per state action pair under the event $\\{|E_{k}|\leq m\\}$. Thus,
the second term can be bounded by

$\mathbb{E}\left[\sum_{k=1}^{K}\tilde{\Delta}_{k}\mathbbm{1}_{\\{|E_{k}|\leq
m\\}}\cdot\mathbbm{1}_{\mathcal{B}_{k}^{c}}\right]\leq\frac{SA}{1-\gamma}\log
m.$

We define $\\{(s_{k,i},a_{k,i})\\}_{i=1}^{|E_{k}|}$ to be the trajectory
followed by $\pi_{k}$ in pseudo-episode $k$ starting from state
$s_{k,1}=s_{t_{k}}$, the state at the beginning of pseudo-episode $k$. By
equation 5,
$|\min_{s\in\mathcal{S}}V^{\gamma}_{\pi_{k},\mathcal{E}^{k}}(s)-\max_{s\in\mathcal{S}}V^{\gamma}_{\pi_{k},\mathcal{E}^{k}}(s)|\leq
2\tau$ for all $s\in\mathcal{S}$. Thus, we can bound the first term

$\displaystyle\quad\mathbb{E}\left[\sum_{k=1}^{K}\mathbb{E}\left[\tilde{\Delta}_{k}\mid\mathcal{E},\mathcal{E}^{k}\right]\mathbbm{1}_{\\{\mathcal{E},\mathcal{E}^{k}\in\mathcal{M}_{k}\\}}\cdot\mathbbm{1}_{\mathcal{B}_{k}}\right]$
$\displaystyle\leq\mathbb{E}\sum_{k=1}^{K}\sum_{i=1}^{|E_{k}|}\mathbb{E}\left[\gamma\left|\langle
P_{\pi_{k}(s_{k,i})s_{k,i}}-P^{k}_{\pi_{k}(s_{k,i})s_{k,i}},V_{\pi_{k},\mathcal{E}^{k}}^{\gamma}\rangle\right|\mid\mathcal{E},\mathcal{E}^{k}\right]\cdot\mathbbm{1}_{\\{\mathcal{E},\mathcal{E}^{k}\in\mathcal{M}_{k}\\}}\cdot\mathbbm{1}_{\mathcal{B}_{k}}$
$\displaystyle=\mathbb{E}\sum_{k=1}^{K}\sum_{i=1}^{|E_{k}|}\mathbb{E}\Big{[}\gamma\left|\langle
P_{\pi_{k}(s_{k,i})s_{k,i}}-P^{k}_{\pi_{k}(s_{k,i})s_{k,i}},V_{\pi_{k},\mathcal{E}^{k}}^{\gamma}-\min_{s\in\mathcal{S}}V_{\pi_{k},\mathcal{E}^{k}}^{\gamma}(s)\cdot\mathbf{1}\rangle\right|$
$\displaystyle\quad+\gamma\left|\langle
P_{\pi_{k}(s_{k,i})s_{k,i}}-P^{k}_{\pi_{k}(s_{k,i})s_{k,i}},\min_{s\in\mathcal{S}}V_{\pi_{k},\mathcal{E}^{k}}^{\gamma}(s)\cdot\mathbf{1}\rangle\right|\mid\mathcal{E},\mathcal{E}^{k}\Big{]}\cdot\mathbbm{1}_{\\{\mathcal{E},\mathcal{E}^{k}\in\mathcal{M}_{k}\\}}\cdot\mathbbm{1}_{\mathcal{B}_{k}}$
$\displaystyle=\mathbb{E}\sum_{k=1}^{K}\sum_{i=1}^{|E_{k}|}\mathbb{E}\Big{[}\gamma\left|\langle
P_{\pi_{k}(s_{k,i})s_{k,i}}-P^{k}_{\pi_{k}(s_{k,i})s_{k,i}},V_{\pi_{k},\mathcal{E}^{k}}^{\gamma}-\min_{s\in\mathcal{S}}V_{\pi_{k},\mathcal{E}^{k}}^{\gamma}(s)\cdot\mathbf{1}\rangle\right|\mid\mathcal{E},\mathcal{E}^{k}\Big{]}\cdot\mathbbm{1}_{\\{\mathcal{E},\mathcal{E}^{k}\in\mathcal{M}_{k}\\}}\cdot\mathbbm{1}_{\mathcal{B}_{k}}$
$\displaystyle\leq\mathbb{E}\sum_{k=1}^{K}\sum_{i=1}^{|E_{k}|}\gamma\left\|P_{\pi_{k}(s_{k,i})s_{k,i}}-P^{k}_{\pi_{k}(s_{k,i})s_{k,i}}\right\|_{1}\left\|V_{\pi_{k},\mathcal{E}^{k}}^{\gamma}-\min_{s\in\mathcal{S}}V_{\pi_{k},\mathcal{E}^{k}}^{\gamma}(s)\cdot\mathbf{1}\right\|_{\infty}\cdot\mathbbm{1}_{\\{\mathcal{E},\mathcal{E}^{k}\in\mathcal{M}_{k}\\}}\cdot\mathbbm{1}_{\mathcal{B}_{k}}$
$\displaystyle\leq\mathbb{E}\sum_{k=1}^{K}\sum_{i=1}^{|E_{k}|}\min\\{4\tau\gamma\beta_{k}(s_{k,i},a_{k,i}),1\\}\cdot\mathbbm{1}_{\mathcal{B}_{k}}.$

where the second equality follows since $P_{\pi_{k}(s_{k,i})s_{k,i}}$ and
$P^{k}_{\pi_{k}(s_{k,i})s_{k,i}}$ are probability distributions, in the
second-to-last inequality we apply Hölder’s inequality, and in the last
inequality we apply Lemma 5.3. We proceed to bounding the first term. Recall
that
$\beta_{k}(s,a)=\sqrt{\frac{14S\log(2SAKt_{k})}{\max\\{N_{t_{k}}(s,a),1\\}}}$,
then

$\displaystyle\quad\sum_{k=1}^{K}\sum_{i=1}^{|E_{k}|}\min\\{4\tau\gamma\beta_{k}(s_{k,i},a_{k,i}),1\\}\cdot\mathbbm{1}_{\mathcal{B}_{k}}\leq
4\tau\sum_{k=1}^{K}\sum_{i=1}^{|E_{k}|}\mathbbm{1}_{\mathcal{B}_{k}}\sqrt{\frac{14S\log(2SAKt_{k})}{\max\\{1,N_{t_{k}}(s_{k,i},a_{k,i})\\}}}.$

Under the event $\mathcal{B}_{k}=\\{N_{t_{k+1}-1}(s,a)+1\leq
2N_{t_{k}}(s,a)~{}\forall(s,a)\in\mathcal{S}\times\mathcal{A}\\}$, for any
$t\in E_{k}$, $N_{t}(s,a)+1\leq N_{t_{k+1}-1}(s,a)+1\leq 2N_{t_{k}}(s,a)$.
Therefore,

$\displaystyle\sum_{k=1}^{K}\sum_{t\in
E_{k}}\sqrt{\frac{\mathbbm{1}_{\mathcal{B}_{k}}}{N_{t_{k}}(s_{t},a_{t})}}$
$\displaystyle\leq\sum_{k=1}^{K}\sum_{t\in
E_{k}}\sqrt{\frac{2}{N_{t}(s_{t},a_{t})+1}}$
$\displaystyle=\sqrt{2}\sum_{t=1}^{T}(N_{t}(s_{t},a_{t})+1)^{-1/2}$
$\displaystyle\leq\sqrt{2}\sum_{s,a}\sum_{j=1}^{N_{T+1}(s,a)}j^{-1/2}$
$\displaystyle\leq\sqrt{2}\sum_{s,a}\int_{x=0}^{N_{T+1}(s,a)}x^{-1/2}dx$
$\displaystyle\leq\sqrt{2SA\sum_{s,a}N_{T+1}(s,a)}$
$\displaystyle=\sqrt{2SAT}.$

Since all rewards and transitions are absolutely constrained in $[0,1]$, our
term of interest

$\displaystyle\quad\sum_{k=1}^{K}\sum_{i=1}^{|E_{k}|}\min\\{4\tau\gamma\beta_{k}(s_{k,i},a_{k,i}),1\\}\cdot\mathbbm{1}_{\mathcal{B}_{k}}\leq
4\tau\cdot S\sqrt{28AT\log(2SAT)}.$

∎

##  Appendix B Supporting Lemmas

###  B.1 Proof of Lemma 5.1

###### Proof.

By definition, $t_{k}$ is a stopping time, so it is
$\sigma(H_{t_{k}})$-measurable. Since $\mathcal{E}^{k}$ is sampled from the
posterior distribution $\mathbb{P}(\mathcal{E}\in\cdot|H_{t_{k}})$,
$\mathcal{E}^{k}$ and $\mathbb{P}(\mathcal{E}\in\cdot|H_{t_{k}})$ are also
measurable with respect to $\sigma(H_{t_{k}})$. Conditioning on $H_{t_{k}}$,
the only randomness in $g(\mathcal{E}^{k})$ is the random sampling in the
algorithm. The proof follows by integrating over
$\mathbb{P}(\mathcal{E}\in\cdot|H_{t_{k}})$. ∎

###  B.2 Proof of Lemma 5.4

###### Proof.

By the $L_{1}$-deviation bound for empirical distributions in [18], when
$N_{t_{k}}(s,a)>0$,

$\displaystyle\mathbb{P}\left(\left\|\hat{P}_{as}-P_{as}\right\|_{1}\geq\beta_{k}(s,a)\right)$
$\displaystyle\leq(2^{S}-2)\exp\left(-\frac{N_{t_{k}}(s,a)\beta_{k}^{2}(s,a)}{2}\right)$
$\displaystyle\leq 2^{S}\exp\left(-7S\log(2SAKt_{k})\right)\leq
2^{S}\exp(-\log(4\cdot 2^{S}SAKt_{k}^{2}))=\frac{1}{4SAKt_{k}^{2}},$

where the second line is due to
$\sum_{s^{\prime}\in\mathcal{S}}\hat{P}_{as}(s^{\prime})=\sum_{s^{\prime}\in\mathcal{S}}P_{as}(s^{\prime})=1$,
and the third line follows from Hölder’s inequality. When $N_{t_{k}}(s,a)=0$,
the bounds trivially hold. Applying a union bound over all possible values of
$t_{k}=1,\dots,\infty$, we get

$\displaystyle\mathbb{P}\left(\left|\langle\hat{P}_{as}-P_{as},V^{\gamma}_{\pi_{k},\mathcal{E}^{k}}\rangle\right|\geq\beta_{k}(s,a)\right)$
$\displaystyle\leq\sum_{t=1}^{\infty}\frac{1}{4SAKt^{2}}=\frac{\pi^{2}}{24SAK}\leq\frac{1}{2SAK}.$

We may conclude the proof with a union bound over all $(s,a)$. ∎