$^*$ Work was done during the intern at 4Paradigm Inc..

$^\dagger$ Corresponding authors.

Recent advancements in large language models (LLMs) have revealed their potential for achieving autonomous agents possessing human-level intelligence. However, existing benchmarks for evaluating LLM Agents either use static datasets, potentially leading to data leakage, or focus only on single-agent scenarios, overlooking the complexities of multi-agent interactions. There is a lack of a benchmark that evaluates the diverse capabilities of LLM agents in multi-agent, dynamic environments. To this end, we introduce , a novel and easily extensible framework for evaluating the diverse capabilities of LLM in multi-agent dynamic environments.   encompasses seven distinct gaming environments, employing scoring to assess crucial abilities in LLM agents, including spatial reasoning, strategic planning, numerical reasoning, risk assessment, communication, opponent modeling, and team collaboration. We conduct an extensive experiment and human evaluation among different sizes and types of LLMs, showing that LLMs still have a significant journey ahead in their development towards becoming fully autonomous agents, especially in opponent modeling and team collaboration. We hope   could guide future research towards enhancing these capabilities in LLMs, ultimately leading to more sophisticated and practical applications in dynamic, multi-agent settings. The code and data will be available.

§ INTRODUCTION

Recent large language models (LLMs) have greatly promoted the progress of the field of natural language processing (NLP) due to their excellent zero-shot capabilities in various downstream tasks <cit.>. LLMs not only excel in comprehending and generating intricate text but also demonstrate remarkable adaptability, even without training tailored to specific tasks <cit.>. They possess the ability to analyze, strategize, and respond effectively to unfamiliar scenarios using minimal guiding prompts. This has opened new avenues for researchers to consider LLMs as autonomous agents, providing automated assistance in complex real-world tasks such as software development and knowledge integration<cit.>.

To better understand the skills needed by LLM as an agent, researchers are now concentrating on creating and using various scenarios to assess LLM's performance in specific settings <cit.>. For instance, AgentBench introduced eight distinct environments, such as operating systems and databases, to examine LLM's proficiency in code generation and lateral thinking. Similarly, SmartPlay tests LLM in a gaming context as a solo agent to gauge its reasoning and strategic planning abilities. Nonetheless, these benchmarks have their constraints. Firstly, static datasets used in benchmarks like AgentBench might lead to issues such as data leakage and overfitting, as LLMs could have already encountered this data during their pre-training phase <cit.>. Secondly, evaluation systems that focus solely on a single agent also have evident limitations, particularly in analyzing an agent's performance in intricate and dynamically interactive settings. Such single-agent environments tend to concentrate on the interactions between the agent and its environment, thereby overlooking the complex dynamics of interactions that occur among multiple agents in a shared environment <cit.>.

Examples of seven different game environments in .

To this end, we proposed , a dynamic evaluation benchmark specially designed for multi-agent interaction. As illustrated in Figure <ref>,   covers seven different types of dynamic, multi-agent game environments. For example, the Texas Hold'em poker game environment automatically generates a new hand for each game, and the complexity of each round's state increases exponentially. This dynamic nature of the game serves to mitigate the issue of data leakage. In the Undercover environment, the LLM agents need to point out the “undercover” during the communication process with other agents, which measures the LLM agents' communication ability and opponent modeling ability when facing different agents. Based on these environments, we can comprehensively evaluate LLM's spatial comprehension, strategic planning, numerical reasoning, risk assessment, communication, opponent modeling, and team collaboration capabilities in the dynamic multi-agent environment.

To more accurately evaluate LLM's performance in these multi-agent environments, we adopted the  <cit.> scoring system, which can better help   evaluate other metrics besides win rate, such as the relative skill level between agents, to provide a more comprehensive assessment under different scenarios and opponent configurations.

We conduct an extensive experiment and human evaluation among 14 different sizes and types of LLMs. The results indicated significant potential for improvement in LLM's teamwork and opponent modeling skills within multi-agent environments.  Based on these results, we hope   can inspire future research focused on enhancing the core capabilities of LLM in multi-agent settings to promote the widespread use of LLM agents in real-world applications.

§ BENCHMARK DETAIL

In this section, we provide a detailed overview of LLMArena's composition, which includes its seven distinct game environments, evaluation metrics, and the methodologies used for assessment.

§.§ Benchmark Overview

Figure <ref> illustrates the seven distinct environments within . Within each specific environment, LLMs may need to utilize a unique combination of capabilities to effectively tackle these challenges. For instance, in the Undercover environment, LLMs are required to possess a multifaceted skill set, including opponent modeling, communicating effectively, and team collaboration. The absence of any one of these abilities could result in ultimate failure in this environment.

§.§ Benchmark Construction

To ensure user-friendliness and robust scalability in , we have developed the environment using PettingZoo <cit.> as a foundation. This approach enables subsequent researchers to effortlessly integrate new environments into this framework. By simply creating environments that adhere to the PettingZoo interface specifications[<https://pettingzoo.farama.org/content/environment_creation/>], they can seamlessly add these to  for evaluating the diverse capabilities of LLMs. Every environment within  offers system prompts that outline the game rules and prompt templates designed to guide LLM agents in gameplay. These templates include information on the current status of the game, historical data, and a range of optional actions, facilitating a more structured and informed gaming experience for the LLM agents. All the prompts are shown in Appendix <ref>.

§.§ Metrics

In this section, we outline the evaluation metrics used by , followed by a comparative analysis with metrics utilized in prior research.

is a scoring system developed by <cit.> that evaluates multiple agents' skill levels in competitive gaming. In contrast to static, opponent-independent metrics employed in previous research, such as Win Rate and Completion Rate <cit.>, offers a more nuanced assessment. It goes beyond merely accounting for wins and losses by also considering the quality of the game and the skill disparities between players. Within the framework, defeating higher-skilled opponents yields more points compared to victories over lower-skilled adversaries. This approach stands in stark contrast to simple win rate calculations, which do not account for the skill level of the opponent. Such opponent-related metrics provide an accurate evaluation of an agent's real competencies in a multi-agent environment.

Reward Currently, a substantial amount of research employs expert LLMs to assess the capabilities of other LLMs, yet this approach frequently lacks interpretability  <cit.>.   addresses the gap by leveraging the concept of reward from reinforcement learning to measure the quality of each action performed by agents. The method allows for a quantitative and interpretable evaluation of LLMs' capabilities, offering a more nuanced and understandable analysis.

§.§ Environment Settings

In this section, we give a comprehensive explanation of the diverse game environments included in the   benchmark, highlighting the specific challenges that language models encounter while engaging with these environments.

TicTacToe: TicTacToe[<https://pettingzoo.farama.org/environments/classic/tictactoe/>] is a strategy game where two LLM agents alternate in placing their marks on a 3$\times$3 grid. Victory is achieved when one agent successfully aligns three of their marks in a row, either horizontally, vertically, or diagonally. The game results in a draw if all cells are filled without any player achieving a winning alignment. This game examines LLM's strategic planning and spatial reasoning capabilities. We adopt the ratings as the evaluation metrics.

As a more complex case of the board game, ConnectFour[<https://pettingzoo.farama.org/environments/classic/connect_four/>] uses a 6$\times$7 chessboard. Here, two LLM agents alternately choose one of the seven columns with available empty cells. Each piece placed will descend to the lowest available space in the selected column, either resting at the bottom or atop a previously placed token. An agent secures victory by aligning four of their pieces either horizontally, vertically, or diagonally. The game concludes in a draw if all cells are filled without a winner. Similar to TicTacToe, in ConnectFour, the LLMs primarily encounter challenges in strategic reasoning and spatial reasoning. We adopt the ratings as the evaluation metrics.

Texas Hold’em
Texas Hold'em[<https://pettingzoo.farama.org/environments/classic/texas_holdem_no_limit/>] is a well-known card game. In , each game is played by two LLM agents. At the beginning of each game, players are dealt two private cards, known as hole cards. Subsequently, five community cards are dealt across three stages - the flop, the turn, and the river. Players aim to construct the best possible five-card hand using a combination of their hole cards and the community cards. Throughout the game, there are four betting rounds. In each round, players have the option to choose from the following actions: Fold, Check & Call, Raise Half Pot, Raise Full Pot, and All-In. This game environment demands a range of capabilities from LLMs, including numerical reasoning, opponent modeling, and risk assessment. We adopt the ratings as the evaluation metrics.

Undercover is a party game, where players are divided into two groups: undercover and non-undercover. Two groups of players each receive a pair of similar but distinct words. The game has two stages per round: a communication stage where players describe their words, followed by a voting stage to identify an undercover. At this time, if all undercovers are eliminated, the non-undercovers win, otherwise the next round will proceed. In , 5 LLM agents play in each game, which includes four non-undercover agents using GPT-3.5-Turbo and one undercover LLM undergoing evaluation. The game lasts up to two rounds, and if the undercovers remain undetected, they win. Given the superior capabilities of GPT-4, employing it as the non-undercover agent would render it nearly impossible for other models to win. Therefore, we choose GPT-3.5-Turbo as non-undercover agents. This game tests an LLM's proficiency in communication, opponent modeling, and team collaboration. The evaluation metric used here is the winning rate of each LLM when playing as the undercover against GPT-3.5-Turbo.

Bargain <cit.> is a semi-cooperative game where two LLM agents are required to devise a distribution strategy for a pool of items. Each item holds a distinct, undisclosed value for both agents. The game aims to reach a consensus on the allocation. When an agreement on the allocation is achieved, the agent with the maximum total value from the items secured emerges victorious. Bargain requires LLM to have the ability of numerical reasoning, communication, and opponent modeling. We adopt the ratings as the evaluation metrics.

A first-price sealed-bid auction[<https://en.wikipedia.org/wiki/First-price_sealed-bid_auction>] is a widely used auction format in which all participants place bids without knowledge of each other's bids, and the highest bidder wins. In , two LLM agents are participating in each auction. Each agent receives a random inner valuation of the item. The winning LLM in the auction will receive their inner valuation minus the actual bid as a reward. This environment evaluates the LLM's numerical reasoning and opponent modeling abilities. We measure the LLM's performance using the average reward it achieves as the evaluation metric.

Hanabi Hanabi is a cooperative card game wherein two LLM agents can only view each other's hand of cards. They use info tokens to “reveal cards” to each other, “discard cards” to acquire more information tokens, and “play cards” in a certain order to form fireworks. This requires team collaboration, strategic planning, and numerical reasoning skills from the LLMs. Upon successfully setting up a firework, both LLM agents are rewarded with points equivalent to the sum of the card values in the firework. In , we form the same two LLMs into a cooperation team, and we employ the average reward obtained by various LLM teams as an evaluation metric.

§ EXPERIMENTS

§.§ Experiments Setup

We conduct experiments with the closed-source GPT family LLM by directly calling its API. As for the open-source LLM, we deploy it locally and encapsulate it as an OpenAI API call. To ensure reproducibility, we set the temperature of all LLMs to 0. In all environments except Undercover, we conducted  runs until the ratings between models reached convergence, with over 50 games played per environment per model. For the Undercover environment, we played 100 games of each LLM as an undercover agent in a game with four GPT-3.5-turbo as non-undercover agents. Initially, all LLM agents started with a  score of 25.0 and a variance of 8.33.

§.§ Main Result

In Table <ref>, we present the relative normalized scores for 14 different LLMs across 7 environments within . The original data before normalization can be found in Appendix <ref>. This table allows us to draw the following conclusions.

$\bullet$ As the scale of the model parameters increases, there is a noticeable improvement in the capabilities of LLMs. For instance, LLMs with around 70B parameters exhibit an average performance of 82.87. LLMs with approximately 30B and 10B parameters average 80.68 and 71.05 in performance, respectively. It's noteworthy that the performance enhancement observed when escalating the model size from 10B to 30B parameters (+9.63) is more pronounced than the improvement seen from 30B to 70B parameters (+2.19).

$\bullet$ While it's generally observed that LLMs with a larger scale of parameters tend to outperform their counterparts with fewer parameters within the same series, exceptions can arise in specific environments. A case in point is the performance of Qwen-72B in the Undercover environment is surprisingly 25.93 points lower than that of Qwen-14B, which notably diverges from this trend.

$\bullet$ The performance of LLMs in both the Bid and Hanabi environments significantly lags behind the average of all 7 environments, with deficits of 17.72 and 10.88 points, respectively. Smaller-scale LLMs ($\sim$10B) fared even worse, scoring 31.71 and 15.45 points below the average in these environments. This underscores that tasks involving numerical reasoning, opponent modeling, and team collaboration pose significant challenges for LLMs.

$\bullet$ There remains a significant disparity between GPT-4 and other models. GPT-4 has attained SOTA performance across all evaluated tasks, outperforming other models by an average margin of 16.76.

§ ANALYSIS

In this section, we will conduct a thorough analysis of the experimental results, evaluating LLMs from seven key perspectives: spatial comprehension, strategic planning, numerical reasoning, risk assessment, communication, opponent modeling, and team collaboration. We chose to experiment with 7 LLMs that demonstrate superior performance.

Spatial Comprehension To investigate the spatial comprehension capabilities of LLMs, we conducted 100 self-play games with 7 different LLMs each, recording winning rates and the frequency of hallucinations (instances of illegal moves). Simultaneously, we eliminated the prompts regarding the positioning of the pieces in the LLMs' input and executed another set of 100 self-games, again tallying the winning rates and the occurrences of hallucinations. The results are shown in Table <ref>, which indicates that in both scenarios, the absence of positional cues significantly escalates the likelihood of LLMs experiencing hallucinations, with an average increase of 59.5%. Consequently, this results in a substantial reduction in their win rates, which on average decline by 38.3%.

Through a meticulous case study, we discovered that LLMs demonstrate a limited grasp of the vertical dimension on 2D chessboards. This limitation likely arises because we transform the 2D chessboard into a 1D string input for the LLMs via line breaks. Grasping the vertical concept requires the LLM to correlate two tokens separated by a specific distance in the one-dimensional input. Consequently, even though ConnectFour's chessboard is larger and its state space more complex, TicTacToe's 2D action space demands a higher level of spatial comprehension from the LLM. Hence, in the absence of positional prompts, the performance deterioration in TicTacToe is more pronounced. A case study can be found in Appendix <ref>

Strategic Planning

Average reward received by Human and 7 LLMs per game.

To delve into the strategic planning capabilities of LLMs within a multi-agent environment, we crafted a specialized board valuation function tailored for the ConnectFour environment as follows:

\begin{equation}
\begin{aligned}
V(s) &= 10 \times ( My_4(s) - Oppo_4(s) )\\
&+ 5\times ( My_3(s) - Oppo_3(s) ) \\
&+ 2\times ( My_2(s) - Oppo_2(s) ),
\end{aligned}
\end{equation}

where $s$ represents the board status, $My_4(s)$, $My_3(s)$, and $My_2(s)$ represent the count of four, three, and two consecutive pieces of the player on the chessboard, respectively. Conversely, $Oppo_4(s)$, $Oppo_3(s)$, and $Oppo_2(s)$ represent the similar formations for the opponent's pieces
. We defined the reward as the change in board valuation between the state after the agent's move $s'$ and the state following the previous move $s$:

\begin{equation}
\begin{aligned}
R(a,s,s') = V(s') - V(s),
\end{aligned}
\end{equation}
where $a$ represents the LLM agent's action.
We conducted random battles between seven LLM agents until the rewards converged, and the results are shown in Figure <ref>. It is evident that LLMs with a larger number of parameters consistently demonstrate superior strategic planning abilities. Each decision made by these LLMs propels them towards a more advantageous position, as indicated by the predominantly positive rewards they receive on average. Conversely, LLMs with a smaller parameter scale tend to earn, on average, negative rewards. This suggests an inability to accurately assess the current state of the chessboard and to formulate effective strategies, ultimately leading the game to progress in a direction that favors its opponent. To further explore the gap between LLM's strategic planning capabilities and humans, we manually played five games with seven LLMs each and human players emerged victorious in every game. Simultaneously, we observe that even GPT-4 rarely prioritizes reward maximization (such as turning a blind eye to winning positions). This tendency could stem from the fact that LLMs predominantly base their decisions on textual data. Consequently, the model must translate the game state into text descriptions before making decisions. This process of conversion may result in information loss, affecting the model's strategic performance. An error analysis can be found in Appendix <ref>

To explore the communication capabilities of LLM, we followed the settings in Section <ref> and manually analyzed 50 game records for each LLM, calculating the percentage of their in-game clues that accurately described their secret word (“Description” in Table <ref>). As illustrated in Table <ref>, LLMs demonstrated outstanding proficiency in this task. All LLMs achieved a description success rate of 95.30% on average, with four of them reaching a perfect 100% success rate. This high level of performance can be attributed to the LLMs being trained on extensive textual datasets, which equip them with a nuanced understanding of word associations and contextual meanings, allowing them to more easily delineate the meanings of different words.
However, we also observed that receiving information poses a greater challenge for LLMs compared to giving information. When interpreting messages from other LLMs, they often make cognitive errors, leading to misinterpretations or distortions of the original clues. This may be because their interpretations are often based on their knowledge base rather than relying entirely on input information. This can lead them to misinterpret the intent or context of the original message, thus tampering with the original clue, which shows that LLMs still have limitations in handling complex, multi-level communications. A case study can be found in Appendix <ref>

Opponent Modeling
Moreover, the Undercover environment demands that LLMs possess not only communication skills but also the capability to model opponents. Building upon the settings established in Section <ref>, we further tasked each LLM agent with deducing the secret words of others during the voting phase. We recorded the instances where each LLM accurately guessed the secret word of any one agent (“Guess” in Table <ref>), as well as the occasions where they successfully identified the secret words of all other agents (“Guess (strict)” in Table <ref>). The results are shown in Table <ref>, where we can find that inferring the secret words of others through their descriptions is more challenging than describing oneself. Through manual analysis, we discovered that only GPT-4 possesses the analytical and reasoning skills necessary to identify itself as an undercover agent. Subsequently, it adjusts the clues it provides in the following round for more effective camouflage. This advanced ability to model opponents also enables GPT-4 to more accurately guess the secret words of all other agents, resulting in superior performance.

Numerical Reasoning

Scores obtained by 7 LLMs in 100 bid games.

Bid represents a typical problem in incomplete information games. In such scenarios, the Bayesian Nash equilibrium for two rational agents is theoretically set at $\frac{v}{2}$, where $v$ denotes each agent's valuation of the item  <cit.>. We study the numerical reasoning ability of LLMs in this situation. We play 100 self-games of seven types of LLMs in the Bid environment, and count the difference between their bids $v'$ and the Nash equilibrium $\frac{v}{2}$, and calculate the normalized score $score = \frac{v'-v/2}{v/2}$. The results are shown in the Figure <ref>.
The data presented in the figure allows us to deduce that nearly all LLMs, except Deepseek-7B, tend to place bids that exceed the Nash equilibrium, with their median bids being on average 52% higher. Notably, Deepseek-67B exhibits an extreme behavior: it opts for bids that significantly sacrifice its profits, ostensibly to guarantee a win in the auction. Consequently, its overall performance in this particular environment is notably subpar as illustrated in Table <ref>.

Risk Assessment

The average estimated win rate corresponding to each action in 100 Texas Hold'em games for 7 LLMs.

To investigate the risk assessment capabilities of LLMs in an incomplete information environment, we sampled 100 static card games from the dynamic Texas Hold'em environment. In each game, the LLMs are equipped with only two private cards and three public cards as their information basis. We use Monte Carlo sampling to estimate the winning rate of LLM in each game, then record the actions taken by each LLM under these specific conditions. The specific actions of each LLM, along with the average estimated winning rate are shown in Figure <ref>, where we can observe that LLMs tend to adopt a more conservative approach in their risk assessments. Additionally, three of the LLMs consistently opted for “Check and Call” strategies, and all models except GPT-4 refrained from selecting the most aggressive course of action, “All in”. This may be because LLMs received caution in treating gambling-related scenarios during the pre-training and security alignment phase. Simultaneously, we noted that GPT-4 exhibits a robust risk assessment capability. It tends to choose “All in” when the winning rate is exceptionally high. Moreover, GPT-4 adapts its strategy as the winning rate of the hand decreases, opting for relatively low-risk actions. Notably, when the hand's winning rate falls below 40%, GPT-4 is the sole LLM that selects “Fold” as a strategic decision to mitigate losses on time.

Team Collaboration
As outlined in Section <ref>, within the Hanabi environment, LLMs are required to alternate between “discarding cards” and “revealing cards” to cooperate to obtain more information, and then build fireworks through “play cards”. To investigate the efficacy of LLMs in executing team cooperation, we analyzed the frequency of each type of action performed by LLMs. As shown in Figure <ref>, although most LLMs frequently utilize the “reveal cards” action to share hand information with their opponent, they seldom use the “discard cards” action, which would give the opponent a chance to “reveal cards” for more information, thus rashly choosing “play cards” when there is insufficient information, causing the game to fail.

The proportion of three types of actions when playing Hanabi among 7 LLMs.

§ RELATED WORKS

LLM Evaluation With the rapid development of LLMs, the evaluation practices of traditional NLP tasks <cit.> limit their performance. Instead, the use of human-written exam questions as an assessment paradigm <cit.> has become increasingly mainstream, focusing primarily on testing the world knowledge and reasoning capabilities in a multi-task benchmark. In addition, some newly proposed benchmarks and methods examine large language models from multiple dimensions, such as adaptability to professional fields <cit.>, real-world application <cit.>, robustness <cit.>, multi-modal capabilities <cit.>, etc. Recently, the trend of treating large language models as agents has become increasingly evident in academia, and a series of studies <cit.> aimed to evaluate the performance of these models when acting as agents in games. However, most of these studies are limited to a single agent, thus failing to fully capture the characteristics of large language models in game or cooperative scenarios and group behavior.

LLM-based Agents Reinforcement learning has been extensively employed in the training of autonomous agents <cit.>. With the superior capabilities of LLMs, the utilization of LLMs as cognitive entities and controllers for agents has garnered widespread acclaim <cit.>. <cit.> initially introduced the CoT technology, which notably amplifies the reasoning and planning abilities of LLM-based agents, consequently leading a research surge dominated by reasoning strategies <cit.>. Furthermore, empirical studies indicate that collaborative and adversarial frameworks <cit.> involving multiple LLMs surpass the capabilities of singular agents across various tasks and may lead to the emergence of social phenomena <cit.>.

§ CONCLUSION

In our study, we introduced , a benchmark designed to assess the diverse abilities of LLM agents in dynamic, multi-agent environments. Through comprehensive analysis of seven game environments that require necessary abilities for LLM agents, our findings reveal that LLMs exhibit weaknesses in spatial reasoning, opponent modeling, and team collaboration. Enhancing the performance of LLM agents in dynamic multi-agent settings remains an unresolved challenge. We anticipate that future researchers will utilize  to conduct evaluations in a broader range of scenarios.

§ LIMITATION

While our research primarily focuses on assessing the capabilities of LLM agents within dynamic multi-agent environments, it is important to acknowledge two limitations. Firstly, in the journey towards achieving autonomous agents, an LLM agent's ability extends beyond merely analyzing textual information. It necessitates engaging with a variety of modal inputs, including video and audio. The capabilities of LLMs within such multi-modal dynamic contexts remain an untapped area of exploration. Secondly, our study did not delve into the potential of LLMs that leverage external tools. We anticipate and encourage further research in both of these promising dimensions to broaden our understanding and capabilities of LLM agents.

§ ETHICAL CONSIDERATIONS

The ethical landscape surrounding LLM agents is marked by significant challenges, particularly in the realms of responsible usage, and the potential for misuse. The deployment of autonomous LLM agents in decision-making roles raises questions about accountability and the need for robust frameworks to prevent unethical applications. The potential for misuse, such as manipulating scenarios or exploiting systems, underscores the necessity for stringent guidelines and monitoring.

outer arc=0pt,
before upper==1.5em

§ COMPLETE PROMPT DESIGN

In this section, we provide complete prompts for all seven game environments in LLM Arena. As the agent in the LLM Arena must consistently interact with the environment, similar to the reinforcement learning setting, various prompts are required to guide the agent in comprehending the rules and taking action. Specifically, three types of prompts work:

* System Prompt. System prompts are special messages used to steer the behavior of LLM. They allow to prescribe the agent's style and task within certain bounds, making it more customizable and adaptable for various use cases.

In LLM Arena, we stipulate the role of the agent and the rules of the game in the system prompt.

* Observation Prompt. Observation Prompt provides the necessary state information for the agent to interact with the environment, including the opponent's actions, current game status, legal actions, etc. We use {} to frame these changing information.

* Action Prompt. Action Prompt guides the Agent to choose from legal actions and output regularized actions. In addition, to stimulate the agent's reasoning ability, in some environments, we also add CoT Prompt.

§.§ TicTacToe

In TicTacToe, the content in {} can be obtained from the interaction between the agent and the environment. For example, {player_type} includes "X" and "O", {board_status} represents the current chessboard, and we describe the entire chessboard in the form of text, as the example in System Prompt. {available} represents the current legal action list of the agent.

The detailed prompt template of TicTacToe is as follows.

[System Prompt]
You are playing TicTacToe.

TicTacToe is played on a three-by-three grid by two players, who alternately place the marks X and O in one of the nine spaces in the grid.

The player who succeeds in placing three of their marks in a horizontal, vertical, or diagonal row is the winner.

In the following example, the first player (X) wins the game in seven steps:

1. [Player 1]: X: (1, 3)

,, ,
, ,

2. [Player 2]: O: (1, 1)

,, ,
, ,

3. [Player 1]: X: (3, 1)

,, ,
X, ,

4.  [Player 2]: O: (2, 2)

,O, ,
X, ,

5. [Player 1]: X: (3, 3)

,O, ,
X, ,X

6. [Player 2]: O: (2, 3)

,O, O,
X, ,X

7. [Player 1]: X: (3, 2)

,O, O,
X,X ,X

X plays first. Players will specify the position of the stone and the moderator will plot the board status.

If a position has been marked, future marks cannot be put in the same position.

The players interact with the game by specifying the position of the stones (x, y), where x indicates the row and y indicates the column, so (1, 1) is the top left corner and (3, 3) is the bottom right corner."

[Observation Prompt]
You play {player_type}.

The board status is {board_status}.

You can only put the mark on [{available}].

[Action Prompt]
You should only output {player_type} and the position of the move, for example: "{player_type}: (1, 3)"

The position you put the mark on must be empty.

Don't say anything besides mark position.

§.§ ConnectFour

In ConnectFour, the observation prompt and action prompt are similar to TicTacToe. We also use text to describe the chessboard.

The detailed prompt template of Texas Hold’em is as follows.

[System Prompt]
You are playing ConnectFour.

ConnectFour is played on a six-by-seven grid by two players, who alternately drop their makers X and O into one of the seven columns. Each marker will fall to the lowest available space within the selected column.

The player who succeeds in placing four of their makers in a horizontal, vertical, or diagonal row is the winner.
X plays first. Players interact with the game by specifying the column number where they want to drop their marker. If a column is already full, players cannot drop a marker into that column.

The columns are numbered from 1 to 7, from left to right. Players cannot place a token outside this range.

[Observation Prompt]
You play {player_type}.

The board status is {board_status}.

You can only choose one of the following columns: [ {available} ].

[Action Prompt]
You should only output {player_type} and the column of the move you choose to put your mark, for example: "{player_type}: 1"

The column you put the mark on cannot be full.

Don't say anything besides mark position.

§.§ Texas Hold’em

In Texas Hold'em, the status information of the environment mainly includes three types: hand cards({private}), community cards ({public}), and chips ({chips}).

The detailed prompt template of Texas Hold’em is as follows.
[System Prompt]
You are playing Texas Hold'em No Limit.

Here are the basic rules for Texas Hold'em Poker:

In this game, you are requested to attend 1 game with your opponent. Both players start with 100 chips, and the player with the most chips at the end of the game wins. If your chips drop to 0, you lose the game. The objective is to obtain more chips than your opponent.

Texas Hold'em hands are ranked from highest to lowest as follows:

Royal Flush: A, K, Q, J, 10 all of the same suit.

Straight Flush: Five consecutive cards of the same suit. The higher top card wins.

Four of a Kind: Four cards of the same rank. The higher rank wins; if the same, compare the fifth card.

Full House: Three cards of one rank and two cards of another rank. A higher three-card rank wins; if the same, compare the two-card rank.

Flush: Five non-consecutive cards of the same suit. Compare the highest card, then the second-highest, and so on.

Straight: Five consecutive cards of different suits. The higher top card wins.

Three of a Kind: Three cards of the same rank. Higher rank wins.

Two Pair: Two cards of one rank and two cards of another rank. Compare the higher pair first, the lower pair, and then the fifth card.

One Pair: Two cards of the same rank. Compare the pair first, then the highest non-paired card, then the second highest, and so on.

High Card: If no hand can be formed, the highest card wins. If the highest cards are the same, compare the second highest, and so on.

If the hands are of equal rank, the pot is split.

[Observation Prompt]
Your observation now is:

The cards in your hands are [{private}]

The community cards are [{public}]

You now have 100-chips chips, the chips that you have put in until now is {chips}

Now you can choose one of the following actions:[{available}]

[Action Prompt]
You should think step by step and output your action. For example: 'Action: Check and Call'

You should explain why you chose the action

§.§ Undercover

In Undercover, unlike other environments, it involves more than two agents, and the game has two stages. Therefore, we designed two prompts respectively for the Giving clues stage and the Accusation stage.

The detailed prompt template of Undercover is as follows.
[System Prompt]
You are playing a game of the Undercover. Here are the game rules:

In Undercover, players are divided into two groups: undercovers and non-undercovers.

Each player receives a secret word, but the secret word given to the undercover is different from the rest.

The main aim is to identify the undercover based on the clues provided by all players.

Be cautious with your clues; being too specific might reveal your identity.

As a non-undercover, you need to unmask the undercover without revealing your own secret word.

As an undercover, your task is to seamlessly integrate with others and avoid detection.

Undercover is played in two phases:

The Giving Clue Phase: Players give hints about their words over several rounds.

The Accusation Phase: Players vote on who they think the undercover is. The undercover should vote for non-undercovers.

[Observation Prompt]

* Giving clues stage

Now is the giving clues stage:

You are {player_name}. Your secret word is "{word}".

This round the other players say: {messages}

* Accusation stage

Now is the accusation stage:

You are {player_name}. Your secret word is {word}.

This round the other players say:{messages}

[Action Prompt]

* Giving clues stage

Now you give one clue (but never include the secret word). You cannot repeat what other players have said.

You should only output {player_name} and the clue, for example: "{player_name}: It's a fruit.".

* Accusation stage

Now vote which of the other players (excluding yourself) is undercover.

You should only output "vote" and the undercover name, for example: "vote: player_1.".

§.§ Bargain

In bargain, both parties need to give a plan and bargain. The quantity and price of goods owned by the agent are represented by {item_nums} and {value} respectively, and the plan proposed by the agent is represented by {oppo_plan}

The detailed prompt template of Bargain is as follows.

[System Prompt]
You are participating in a game of "Bargaining."  Here are the game rules:

(1) Information and Roles

The game involves two players, Player A and Player B.
A variety of items are available for bargaining, each having a different value to both players. However, the value of each item for the other player is unknown.

Players engage in a series of up to 10 bargaining rounds to reach a consensus.

If a consensus is not reached within these 10 rounds, the negotiation is considered a failure, and it results in a stalemate where both players leave without any rewards.

(2) Objectives

The goal for both Player A and Player B is to negotiate and share these items.

The challenge is that the same item has different values for each player, and they do not know the item's value for their counterpart.

Each player aims to maximize the total value of the items they acquire through negotiation.

[Observation Prompt]
(The game begins. You start to give a plan.)

Now is round {round}:

You are {player_name}.

There are {item_nums[0]} hats, {item_nums[1]} balls and {item_nums[2]} apples.

The value for each hat is {value[0]}, for each ball is {value[1]} and for each apple is {value[2]}.

This round your opponent says:"{bargaining}"

He will get {oppo_plan[0]} hats, {oppo_plan[1]} balls and {oppo_plan[2]} apples.

And you will get {item_nums[0] - oppo_plan[0]} hats, {item_nums[1] - oppo_plan[1]} balls and {item_nums[2] - oppo_plan[2]} apples.

[Action Prompt]
Do you agree with his plan? If you agree, You should only output {player_name} and "Deal", for example: "{player_name}: Deal.".

If you do not agree, you should bargain with your opponent first and then output {player_name} and your plan in the following format:

"{player_name}: x hats y balls z apples." x, y, z are Arabic number.

For example: "I'd like 1 hat, 2 balls, and 0 apples. {player_name}: 1 hat 2 balls 0 apples".

Do not tell your opponent the value of each item.

§.§ Bid

In Bid, the status information is only the agent's valuation of the product ({value}) and the income ({value}-bid). The agent needs to maximize the income.

The detailed prompt template of Bid is as follows.
[System Prompt]
You are participating in a game of "First-price Sealed-Bid Auction." Here are the game rules:

(1) Information and Roles

Participants act as bidders in the auction.

Each bidder has an opportunity to submit one sealed bid for the item being auctioned, without knowing the bids of other participants.

(2) Objectives

The primary objective is to win the auction by submitting the highest bid.

Bidders must balance their desire to win the item against the risk of overpaying.

Each bidder aims to strategically determine their bid based on their valuation of the item and assumptions about other bidders' valuations.

(3) Strategy

The challenge for bidders is in deciding how much to bid. Bid too low, and they risk losing the auction; bid too high, and they risk paying more than the item's value to them (the winner's curse).

Bidders must assess not only their valuation of the item but also try to anticipate the bids of others.

In this game of strategy and valuation, the key is to make a smart bid that balances the desire to win with the risk of overpaying.

[Observation Prompt]
Your valuation of the current auction item is ${value}, your bid must be lower than your valuation.

You will get rewards equal ${value} - your bid

[Action Prompt]
You should think step by step and then output your bid in the following format:

"{player_name}: $x.xx"

For example: {player_name}: $1.08

§.§ Hanabi

In Hanabi, the status information of the environment is more complex and challenging than in other environments. For example, the opponent's hand ({other_hands}), current fireworks ({fireworks}), current tokens ({tokens}), known hinted hands ({first_card, second_card}), etc. The agent needs to integrate this information to make reasonable decisions.

The detailed prompt template of Hanabi is as follows.
[System Prompt]
You are playing a Hanabi game.

There are the basic rules for Hanabi with a small structure:

Hanabi is a 2 player-cooperative game where you should work together to form fireworks. A firework is a set of cards of the same color, ordered from 1 to 5. Cards in the game have both a color and a number; there are two colors and five numbers in total. Each player can only view the cards another player holds, but not their own. Players cannot directly communicate with each other, but must instead remove an info token from play to give information. Players can tell other players which of the cards in their hand is a specific color, or a specific number. You must point out all the cards of this color or number. There are initially 3 info tokens, but players can discard cards in their hand and draw a new card from the deck to return an info token into play. Players can also play a card from their hand: the card must either begin a new firework or be appended to an existing firework. However, 2 fireworks cannot have the same color, and a single firework cannot repeat numbers. If the played card does not satisfy these conditions, a life token is placed. The game ends when either 3 life tokens have been placed, all 2 fireworks have been completed, or all cards have been drawn from the deck. Points are awarded based on the largest card value in each created firework.

In this game, you and your opponent are players. Each person has two hand cards, each with two colors and five possible numbers from 1 to 5. Players share 3 info tokens and 1 life token.

[Observation Prompt]
Your observation now is :

The cards in another player's hands are:{other_hands}

The current fireworks is:{fireworks}

The current number of tokens is {tokens}

The information of your own cards that was revealed is:{first_card, second_card}

The current deck size is {deck_size}

Your opponent's action is {opponent_action}

The card that the opponent last played or discarded is {last_played}

Now you can choose one of the following actions: {available}

[Action Prompt]
You should think step by step and output your action. For example: "Reveal Yellow Cards for another player"

You will respond with an action, formatted as:

"Action: <action>"

where you replace <action> with your actual action.

You should explain why you chose the action.

§ CASE STUDY

In this section, we present a detailed case study and conduct an error analysis within the ConnectFour and Undercover environments.

§.§ ConnectFour

As demonstrated in Section <ref>, models with smaller parameter sizes, on average, received negative rewards and engaged in actions detrimental to their own position. An illustrative example of this is as follows:

,,, ,
,,X, ,
X,O,X, O,

In the patial chessboard of ConnectFour, “X” has successfully aligned three pieces diagonally. Upon reaching “O”'s turn, the model with a smaller parameter scale tends to make the counterintuitive choice of placing a piece in the fourth column, inadvertently assisting its opponent, “X”, in securing a diagonal victory.

X,O,X, O,
,,X, O,
X,O,X, O,

Simultaneously, our findings reveal that even a robust model such as GPT-4 is not always capable of executing actions that maximize rewards. For instance, in the aforementioned scenario, “X” opts for a suboptimal move by placing a piece in the first column, instead of strategically securing a win by placing it in the fourth column.

X,O,X, O,
X,,X, O,
X,O,X, O,

§.§ Undercover

During our research, we observed that LLMs can sometimes misinterpret information received from other agents. Here is an example, the secret word of undercover is “sun” and the secret word of non-undercovers is “moon”:
[Action Prompt]
Now is the accusation stage:

You are player_2. Your secret word is "Moon".

This round the other players say:

player_0: It's big and hot.

player_1: It's a source of energy.

player_2: It's a celestial body.

player_3: It's associated with tides.

player_4: It's a natural satellite.

Now vote which of the other players (excluding yourself) is the undercover.

You should think step by step first and then output "vote" and the undercover name, for example: "vote: player_1.".

[Response from AgenLM-7B]
As player_2, I will start by analyzing the statements made by the other players.

player_0 mentioned that the secret word is a source of energy. This could be a misleading statement, as the word "Moon" is not typically associated with energy. However, it's possible that player_0 is trying to throw off the other players by giving an unrelated answer.

player_1 said that the secret word is a celestial body. This is a more directly related answer, but it's still not a very specific one. It's possible that player_1 is trying to be vague in order to throw off the other players.

player_3 mentioned that the secret word is associated with tides. This is a more specific answer, and it's one that only a few players might guess. It's possible that player_3 is the undercover player.

player_4 said that the secret word is a natural satellite. This is an even more specific answer, and it's one that only a few players might guess. It's possible that player_4 is the undercover player.

Based on my analysis, I think it's possible that either player_1 or player_4 is the undercover player. However, I need more information to make a definitive decision. I will wait for the next round of statements before voting.

vote: player_4

In this example, player_0 is undercover, and its clue is “It’s big and hot” but AgentLm turns a blind eye to it and matches the wrong clues with player_0 and player_1, leading to wrong inferences.

Simultaneously, we observed that GPT-4 stands out as the sole LLM that is able to identify itself as undercover in the given scenario. In the following example, the secret word obtained by GPT4 as player_4 is “Kangaroo” and the other agents' secret words are “Camel”.
[Action Prompt]
Now is the accusation stage:

You are player_2. Your secret word is "Camel".

This round the other players say:

player_0: It's a desert animal.

player_1: It's known for its humps.

player_2: It's often found in the Middle East.

player_3: It's often used for transportation.

player_4: It's a great jumper.

Now vote which of the other players (excluding yourself) is the undercover.

You should think step by step first and then output "vote" and the undercover name, for example: "vote: player_1.".

[Response from GPT-4]
Based on the clues given by the other players, it seems that their secret words are related to camels, which are desert animals known for their humps, commonly found in the Middle East, and used for transportation. Since my secret word is "Kangaroo," which is unrelated to camels, it's likely that I am the undercover.

However, since the game requires me to blend in and avoid being caught, I should vote for another player who I think might be suspected of being the undercover by the other players. Since all the other players' clues align well with the camel theme, it's difficult to determine who might be suspected by others. In this case, I might choose to vote randomly or choose the player whose clue was the least specific.

vote: player_0

§ ORIGIN RESULT

In this section, we show the original data corresponding to Table <ref>.


Gamma | $\lambda\in\mathbb{R}_{+}$ |  $\frac{S_{n}}{\lambda}\\!-\\!((n\\!+\\!c)k\\!+\\!1)\log\\!\left(\\!\frac{S_{n}}{\lambda}\\!+ck\\!\right)$ $\quad\leqslant\log\frac{1}{\delta}\\!+\\!\log\frac{\Gamma(ck)}{\Gamma((n\\!+\\!c)k)}\\!-\\!\log((n\\!+\\!c)k)-ck\log ck$
Weibull | $\lambda\in\mathbb{R}_{+}$ |  $\frac{S_{n}^{(k)}}{\lambda^{k}}-(n+c+1)\log\left(\frac{S_{n}^{(k)}}{\lambda^{k}}+c\right)$ $\quad\leqslant\log\frac{1}{\delta}+\log\frac{\Gamma(c)}{\Gamma(n+c)}-\log(n+c)-c\log c$
Pareto | $\alpha\in\mathbb{R}$ |  $\alpha L_{n}-(n\\!+\\!c\\!+\\!1)\log\left(\alpha L_{n}+c\right)$ $\quad\leqslant\log\frac{1}{\delta}+\log\frac{\Gamma(c)}{\Gamma(n+c)}-\log(n+c)-c\log c$
Poisson | $\lambda\in\mathbb{R}_{+}$ |  $n\lambda\\!-\\!S_{n}\log\lambda$ $\quad\leqslant\log\frac{1}{\delta}\\!+\\!\log I\left(c,c\lambda\right)-\log I\left(n\\!+\\!c,S_{n}\\!+\\!c\lambda\right)$
Chi-square |  $k\in\mathbb{N}$ or $k\in\mathbb{R}_{+}$ |  $n\log\Gamma\left(\frac{k}{2}\right)\\!-\\!\frac{k}{2}K_{n}\\!-\\!\log J\left(c,c\psi_{0}\left(\frac{k}{2}\right)\right)$ $\quad+\log J\left(n\\!+\\!c,K_{n}\\!+\\!c\psi_{0}\left(\frac{k}{2}\right)\right)\leqslant\log\frac{1}{\delta}$

##  Appendix D Empirical Comparison with Existing Time-uniform Confidence
Sequences

We illustrate the time-uniform confidence sequences derived from Bregman
concentration on several instances of classical exponential families detailed
in 3.2. In each setting, when available, we also report confidence sequences
based on existing methods in the literature555The code is provided in the
supplementary material for reproducibility..

In what follows, we fix $\delta\in(0,1)$ the uniform confidence level. For
each confidence sequence $\left(\Theta_{n}\right)_{n\in\mathbb{N}}(\delta)$,
we report in the figures the intersection sequence $\left(\cap_{k\leqslant
n}\Theta_{k}(\delta)\right)_{n\in\mathbb{N}}$, which also holds with
confidence $1-\delta$, for $n$ up to $200$. Typical realizations of Bregman
confidence sequences are reported in Figure 3 (Gaussian), Figure 4 (Bernoulli,
Poisson), Figure 5 (Exponential, Gamma, Weibull, Pareto), and Figure 6 (Chi-
square).

Figure 3: Examples of confidence upper and lower envelopes around unknown
expectation $\mu=0$ for $\mathcal{N}\left(\mu,1\right)$ (left, cf. Table 2)
and unknown standard deviation $\sigma=1$ for
$\mathcal{N}\left(1,\sigma\right)$ (right, cf. Table 2), as a function of the
number of observations $n$. The thick lines indicate the median curve over
1000 replicates.

Figure 4: Examples of confidence upper and lower envelopes around expectation
$\mu$ for discrete distributions. From top to bottom: $\text{Bernoulli}(p)$,
$p\in\\{0.2,0.5,0.8\\}$ (cf. Table (2)) and $\text{Poisson}(3)$ (cf. Table 2)
on several realizations (each dashed lines) as a function of the number of
observations $n$. The thick lines indicate the median curve over 1000
replicates.

Figure 5: Examples of confidence upper and lower envelopes (from top to
bottom) around scale parameter $\lambda$ for $\text{Exp}(1)$ (cf. Table (2)),
fixed shape $\text{Gamma}(3,2)$ (cf. Table 2), fixed shape
$\text{Weibull}(3,2)$ (cf. Table 2), and exponent $\alpha$ for
$\text{Pareto}(\frac{1}{2})$ (cf. Table 2), on several realizations (each
dashed lines) as a function of the number of observations $n$. The thick lines
indicate the median curve over 1000 replicates.

Figure 6: Examples of confidence upper and lower envelopes around expectation
$\mu$ for (continuous prior) $\text{Gamma}\left(\frac{k}{2}\right)$ with
unknown shape $\frac{k}{2}>0$ and (discrete prior) Chi-square $\chi^{2}(k)$,
$k\in\mathbb{N}^{*}$ (cf. Table (2) and Remark 9) on several realizations
(each dashed lines), as a function of the number of observations $n$. In
particular for the Chi-square, confidence lower and upper bounds are ceiled
and floored to integers. The thick lines indicate the median curve over 1000
replicates.

###  D.1 Gaussian with unknown mean and variance

Figure 7: Example of time-uniform, joint confidence sets around $(\mu,\sigma)$
for $\mathcal{N}\left(1,1\right)$ (cf. Table 2 for
$n\in\left\\{10,25,50,100\right\\}$ observations (smaller confidence sets
correspond to larger sample sizes). The red star indicates the true parameters
$(\mu,\sigma)=(1,1)$.

We consider the two-dimensional family
$\left\\{\mathcal{N}\left(\mu,\sigma^{2}\right),\left(\mu,\sigma\right)\in\mathbb{R}\times\mathbb{R}^{*}_{+}\right\\}$.
To the best of our knowledge, there does not exist time-uniform joint
confidence sets for $\left(\mu,\sigma\right)$ prior to this work. In order to
compare ourselves against some baseline, we derive a crude one based on Chi-
square quantiles and a union bound.

Let $n\in\mathbb{N},\delta\in(0,1)$, $X_{1},\dots,X_{n}$ i.i.d samples from
$\mathcal{N}(\mu_{0},\sigma_{0}^{2})$. The standardized sum of squares

$Z_{t}(\mu_{0},\sigma_{0})=\sum\limits_{s=1}^{t}\left(\frac{X_{t}-\mu_{0}}{\sigma_{0}}\right)^{2}$

follows a $\chi^{2}(t)$ distribution, therefore, denoting by $q_{\chi^{2}(t)}$
the corresponding quantile function, we have:

$\mathbb{P}\left(q_{\chi^{2}(t)}\left(\frac{\delta}{2}\right)\leqslant
Z_{t}(\mu_{0},\sigma_{0})\leqslant
q_{\chi^{2}(t)}\left(1-\frac{\delta}{2}\right)\right)\geqslant 1-\delta\,.$

By a union bound argument, the intersection of $n$ such events with confidence
$\frac{\delta}{n}$, i.e

$\Theta^{Z}_{t,n}(\delta)=\bigcap\limits_{s=1}^{t}\left\\{(\mu,\sigma)\in\mathbb{R}\times\mathbb{R}_{+}^{*}\colon\
q_{\chi^{2}(s)}\left(\frac{\delta}{2n}\right)\leqslant
Z_{s}(\mu,\sigma)\leqslant
q_{\chi^{2}(s)}\left(1-\frac{\delta}{2n}\right)\right\\}\,$

describes a sequence of confidence sets at level $\delta$ that hold uniformly
over $t\in\\{1,\dots,n\\}$.

We report our confidence sets (cf. Equation 2) and the above on Figure 7. The
most striking drawback of $\Theta^{Z}_{t,n}(\delta)$ is that it is not convex
nor even bounded; in particular, projecting onto the axes of $\mu$ and
$\sigma$ only provides trivial confidence sets, $\mathbb{R}$ and
$\mathbb{R}_{+}^{*}$ respectively, rendering this result vacuous. To better
grasp this phenomenon, let us informally consider $\mu=\alpha+\mu_{0}$ and
$\sigma=\alpha$ for some $\alpha>0$. We have:

$\displaystyle Z_{n}(\mu,\sigma)$
$\displaystyle=\sum\limits_{t=1}^{n}\left(\frac{X_{t}-\mu_{0}}{\alpha}-1\right)^{2}$
$\displaystyle=\underbrace{\frac{1}{\alpha^{2}}\sum\limits_{t=1}^{n}\left(X_{t}-\mu_{0}\right)^{2}}_{\approx\frac{\sigma_{0}^{2}}{\alpha^{2}}n}-\underbrace{\frac{2}{\alpha}\sum\limits_{t=1}^{n}\left(X_{t}-\mu_{0}\right)}_{\approx\frac{2}{\alpha}\sqrt{n}}+n\,.$

Hence, for $\alpha\rightarrow+\infty$, $Z_{n}(\mu_{0}+\alpha,\alpha)\approx
n$. On the other hand, Lemma 1 in Laurent and Massart (2000) shows that
$q_{\chi^{2}(n)}\left(1-\delta/2n\right)=\mathcal{O}\left(n+\sqrt{n\log
n}\right)$ and
$q_{\chi^{2}(s)}\left(\delta/2n\right)=\mathcal{O}\left(n\right)$. Therefore,
even with increasing the sample size $n$, there exists arbitrary large
$\alpha$ such that $(\mu_{0}+\alpha,\alpha)$ may belong to
$\Theta^{Z}_{t,n}(\delta)$.

By contrast, our Bregman confidence sets are convex and bounded, which we
interpret as the result of exploiting the true geometry of the two-dimensional
Gaussian family. In addition to the unboundedness, $\Theta^{Z}_{t,n}(\delta)$
is built using a crude union bound, which is not anytime (depends on the
terminal time $n$) and rather loose.

###  D.2 Bernoulli

We consider the Bernoulli distribution $\text{Bernoulli}(\mu)$ for some
unknown $\mu\in[0,1]$. Confidence bounds are displayed in Figure 8 for
$\mu\in\\{0.2,0.5,0.8\\}$. We detail below a few alternative state-of-the-art
bounds.

#### Chernoff-Laplace method for sub-Gaussian distributions

We recall that $B(\mu)$ being supported in $[0,1]$, it is $1/2$-sub-Gaussian
(Hoeffding lemma, Hoeffding (1963)). The method of mixtures for exponential
martingales (Peña et al., 2008) shows that $\mathbb{P}\left(\forall
n\in\mathbb{N},\mu\in\Theta^{\text{Laplace}}_{n}(\delta)\right)\geqslant
1-\delta$, with

$\Theta^{\text{Laplace}}_{n}(\delta)=\left[\widehat{\mu}_{n}-\sqrt{\left(1+\frac{1}{n}\right)\frac{\log\left(2\sqrt{1+n}/\delta\right)}{2n}},\widehat{\mu}_{n}+\sqrt{\left(1+\frac{1}{n}\right)\frac{\log\left(2\sqrt{1+n}/\delta\right)}{2n}}\right].$

Note that a sharper sub-Gaussian control holds for $B(\mu)$, see Kearns and
Saul (1998), Berend and Kontorovich (2013). However, the optimal sub-Gaussian
parameter they suggest ($\frac{1/2-\mu}{\log(1/\mu-1)}$ instead of $1/2$) is a
function of the unknown $\mu$.

#### Bentkus concentration with geometric time-peeling

Kuchibhotla and Zheng (2021, Theorem 4) show that $\mathbb{P}\left(\forall
n\in\mathbb{N},\mu\in\Theta^{\text{Bentkus}}_{n}(\delta)\right)\geqslant
1-\delta$ with

$\Theta^{\text{Bentkus}}_{n}(\delta)=\left[\widehat{\mu}_{n}-\frac{1}{n}q\left(\frac{\delta}{2h(k_{n})};c_{n},1/2,1\right),\widehat{\mu}_{n}+\frac{1}{n}q\left(\frac{\delta}{2h(k_{n})};c_{n},1/2,1\right)\right].$

Here $q(\delta^{\prime};N,A,B)$ is the Bentkus bound, where $\delta^{\prime}$
is the confidence level, $N$ is the sample size, $B$ is the _almost sure_
upper bound of the random variables and $A^{2}$ is the variance upper bound.
The function $h(k)$ is defined as $h(k)=\zeta(1.1)(k+1)^{1.1}$, where
$\zeta(\cdot)$ is the Riemann-zeta function. The integer $k_{n}$ and the real
$c_{n}$ are defined as
$k_{n}=\min\\{k\in\mathbb{N}:\lceil\eta^{k}\rceil\leqslant
n\leqslant\lfloor\eta^{k+1}\rfloor\\}$ and
$c_{n}=\lfloor\eta^{k_{n}+1}\rfloor$, with $\eta=1.1$. The referenced theorem
is stated with an empirical overestimate of the standard deviation instead of
the fixed bound $1/2$, which would lead to replace the $\delta/2$ present in
the confidence set with $\delta/3$ by union bound; we found this step to be of
negligible, and even slightly detrimental impact, in the case of Bernoulli
distributions.

#### Hedged Capital martingale method

Waudby-Smith and Ramdas (2023, Theorem 3) present a nonnegative martingale
construction from observations $X_{1},\dots,X_{n}$ bounded in $[0,1]$.
Following the recommendations of the authors, we define the following
quantities:

$\displaystyle\mathcal{K}_{n}(m)=\max(\mathcal{K}_{n}^{+},\mathcal{K}_{n}^{-}(m)),$
$\displaystyle\mathcal{K}_{n}^{\pm}(m)=\prod_{k=1}^{n}\left(1\pm\lambda_{k}^{\pm}(m)\left(X_{k}-m\right)\right),$
$\displaystyle\lambda_{k}^{+}(m)=\min\left(\lvert\lambda_{k}\rvert,\frac{1/2}{m}\right),\lambda_{k}^{-}(m)=\min\left(\lvert\lambda_{k}\rvert,\frac{1/2}{1-m}\right),$
$\displaystyle\lambda_{k}=\sqrt{\frac{2\log(2/\delta)}{\widehat{\sigma}_{k-1}^{2}k\log(k+1)}},$
$\displaystyle\widehat{\sigma}_{k}^{2}=\frac{1/4+\sum_{i=1}^{k}\left(X_{i}-\widehat{\mu}_{i}\right)^{2}}{k+1},$
$\displaystyle\widehat{\mu}_{k}=\frac{1/2+\sum_{i=1}^{k}X_{i}}{k+1}.$

Then, it holds that $\mathbb{P}\left(\forall
n\in\mathbb{N},\mu\in\Theta^{\text{HC}}_{n}(\delta)\right)\geqslant 1-\delta$,
where
$\Theta^{\text{HC}}_{n}(\delta)=\left\\{m\in[0,1]:\mathcal{K}_{n}(m)<1/\delta\right\\}$.

Figure 8: Confidence upper and lower envelopes built for
$\text{Bernoulli}(\mu)$, $\mu\in\\{0.2,0.5,0.8\\}$, as a function of the
number of observations $n$, averaged over $1000$ independent simulations. Grey
lines are trajectories of empirical means $\widehat{\mu}_{n}$. Confidence
bounds are clipped between $0$ and $1$.

###  D.3 Gaussian

We consider Gaussian distributions $\mathcal{N}(\mu,\sigma^{2})$ for some
unknown $\mu\in\mathbb{R}$ and known variance $\sigma^{2}$. The confidence
bounds are displayed in Figure 9 for $\mu=0$.

#### Chernoff-Laplace

Similarly to the Bernoulli case, $\mathcal{N}(\mu,\sigma^{2})$ is
$\sigma$-sub-Gaussian, therefore
$\mathbb{P}\left(\forall
n\in\mathbb{N},\mu\in\Theta^{\text{Laplace}}_{n}(\delta)\right)\geqslant
1-\delta$, with

$\Theta^{\text{Laplace}}_{n}(\delta)=\left[\widehat{\mu}_{n}-\sigma\sqrt{\left(1+\frac{1}{n}\right)\frac{\log\left(2\sqrt{1+n}/\delta\right)}{n}},\widehat{\mu}_{n}+\sigma\sqrt{\left(1+\frac{1}{n}\right)\frac{\log\left(2\sqrt{1+n}/\delta\right)}{n}}\right].$

#### Kaufmann-Koolen

Kaufmann and Koolen (2021) introduces a martingale construction for
exponential families to derive time-uniform deviation inequalities under
bandit sampling. However, application of their result is limited to Gaussian
distribution with known variance and Gamma distribution with known shape,
which is just a scaled version of exponential distribution. Restricting
Corollary 10 of Kaufmann and Koolen (2021) to the case of a single arm yields
$\mathbb{P}\left(\forall
n\in\mathbb{N},\mu\in\Theta^{\text{KK}}_{n}(\delta)\right)\geqslant 1-\delta$,
with

$\displaystyle\Theta^{\text{KK}}_{n}(\delta)=\left\\{\mathcal{B}_{\mathcal{L}}\left(\widehat{\mu}_{n},\mu\right)\leqslant\frac{2}{n}\log\left(4+\log(n)\right)+\frac{1}{n}C^{g}\left(\log
1/\delta\right)\right\\},$ $\displaystyle g\colon\lambda\in(1/2,1]\mapsto
2\lambda\left(1-\log(4\lambda)\right)+\log\zeta(2\lambda)-\frac{1}{2}\log(1-\lambda),$
$\displaystyle C^{g}\colon
x\in(0,+\infty)\mapsto\min_{\lambda\in(1/2,1]}\frac{g(\lambda)+x}{\lambda},$
$\displaystyle\mathcal{L}(\theta)=\frac{\theta^{2}}{2\sigma^{2}}\quad\text{(log-
partition function of $\mathcal{N}(\cdot,\sigma^{2})$)}.$

Figure 9: Confidence upper and lower envelopes built for Gaussian
distributions $\mathcal{N}(0,1)$ as a function of the number of observations
$n$, averaged over $1000$ independent simulations. Grey lines are trajectories
of empirical means $\widehat{\mu}_{n}$.

###  D.4 Exponential

We now consider exponential distributions $\text{Exp}(1/\mu)$ for some unknown
mean $\mu\in\mathbb{R}$. We report in Figure 10 the confidence bounds for the
case when $\mu=1$.

#### Kaufmann-Koolen

Kaufmann and Koolen (2021, Corollary 12) show that $\mathbb{P}\left(\forall
n\in\mathbb{N},\mu\in\Theta^{\text{KK}}_{n}(\delta)\right)\geqslant 1-\delta$,
with the same definition as for the Gaussian case except

$\displaystyle g\colon\lambda\in(1/2,1]\mapsto
2\lambda\left(1-\log(4\lambda)\right)+\log\zeta(2\lambda)-\log(1-\lambda),$
(13) $\displaystyle\mathcal{L}(\theta)=\log(-1/\mu)\quad\text{(log-partition
function of $\mathcal{E}(1/\mu)$)}.$ (14)

Figure 10: Confidence upper and lower envelopes built for Exponential
distributions $\text{Exp}(1)$ as a function of the number of observations $n$,
averaged over $1000$ independent simulations. Grey lines are trajectories of
empirical means $\widehat{\mu}_{n}$.

###  D.5 Chi-square

We consider $\text{Gamma}\left(\frac{k}{2},\frac{1}{2}\right)$ and
$\chi^{2}\left(k\right)$ distributions for some unknown $k>0$ and
$k\in\mathbb{N}^{*}$ respectively. They are in fact the same distributions,
however we distinguish both as the restriction on the domain for $k$ (real or
integer) bears two consequences:

  * •

the mixture distribution in the martingale construction is either continuous
or discrete, resulting in integrals or sums in the expression of the
confidence sequence (Equation 2);

  * •

confidence bounds are constrained to be integers in the discrete case, thus
ceiling and flooring the lower and upper bounds respectively.

We find that the former is negligible as both the continuous and discrete
mixtures yield the same bound within numerical precision. The latter however
allows to drastically shrink the size of the confidence sequences, resulting
in perfect identification the mean within $95\%$ confidence with less than
$100$ observations in half the simulations (see Figure 11).

###  D.6 Key Observations

On the studied examples, confidence intervals based on time-uniform Bregman
concentration are either comparable with state-of-the art methods for the
corresponding setting or result in sharper bounds, especially for small sample
sizes (lower bounds for Bernoulli compared to Hedged Capital, upper bound for
Exponential compared to Kaufmann-Koolen). In particular, due to the
formulation in terms of Bregman divergence, our intervals are naturally
asymmetric when the underlying distribution is, and respect the support
constraints (for instance Bernoulli Bregman bounds are in $[0,1]$ without the
need for clipping). Moreover, we also provide bounds in novel settings for
which, to the best of our knowledge, time-uniform confidence sets are lacking
(Chi-square, Poisson, Weibull, Pareto, mean-variance for Gaussian).

Figure 11: Confidence upper and lower envelopes built for
$\text{Gamma}\left(\frac{5}{2},\frac{1}{2}\right)$ (blue) and
$\chi^{2}\left(5\right)$ (red) distributions as a function of the number of
observations $n$, over $1000$ independent simulations (colored lines are
median of simulated bounds). Grey lines are trajectories of empirical means
$\widehat{\mu}_{n}$.

###  D.7 Tuning of The Regularization Parameter $c$

In this section, we provide additional experiments regarding the local
regularization parameter $c$. We study the sensitivity of the bounds to the
values of $c$, reported in Figure 12. Then, we report in Figure 13 plots
showing a tuning of parameter $c$ for each fixed $n=n_{0}$ illustrated for
Bernoulli, Gaussian, exponential and Chi-square distributions. Specifically,
$c$ is chosen to minimize the width of the confidence set at $n=n_{0}$, i.e.,
$c_{n_{0}}=\min_{c>0}\lvert\Theta_{n_{0},c}\left(\delta\right)\rvert$. Let us
recall that such a tuning is only valid for a single value. Hence, while using
$c=c_{n_{0}}$ for a fixed $n_{0}$ is allowed by the theory to produce time-
uniform bounds for all $n$, using $c=c_{n}$, that is a different value for
different $n$, is not supported by the theory as it would break the martingale
property necessary for the mixture construction to hold, which is manifested
by a contradiction with the law of iterated logarithm (see Section 3.1).

(a) Bernoulli

(b) Gaussian

(c) Exponential

(d) Chi-square

Figure 12: Confidence envelopes for varying $c\in[0.1,30]$ for
$\mathcal{B}(0.5)$ (top left), $\mathcal{N}(0,1)$ (top right),
$\mathcal{E}(1)$ (bottom left) and $\chi^{2}(5)$ (bottom right). The dotted
black line corresponds to the heuristics $c_{n}\approx 0.12n$.

Figure 13: Optimal (smallest confidence interval diameter) local
regularization parameter
$c^{*}_{n}=\mathop{\mathrm{argmin}}_{c}\lvert\Theta_{n,c}\left(\delta\right)\rvert$
for $\delta=5\%$ on Bernoulli (top left), Gaussian (top right), exponential
(bottom left) and Chi-square (bottom right). Note the apparent common linear
trend $c^{*}_{n}\approx 0.12n$. Results are averaged over $1000$ independent
simulations.

##  Appendix E Application: Generalized Likelihood Ratio Test in Exponential
Families

In this section, we apply our result to revisit GLR tests in exponential
families. The Generalized Likelihood Ratio (GLR) in the exponential family
model $\mathcal{E}$ writes a follows

$\displaystyle G^{\mathcal{E}}_{1:s:t}$ $\displaystyle=$
$\displaystyle\log\bigg{(}\frac{\sup_{\theta_{1},\theta_{2}}\prod_{t^{\prime}=1}^{s}p_{\theta_{1}}(X_{t^{\prime}})\prod_{t^{\prime}=s+1}^{t}p_{\theta_{2}}(X_{t^{\prime}})}{\sup_{\theta}\prod_{t^{\prime}=1}^{t}p_{\theta}(X_{t^{\prime}})}\bigg{)}$
$\displaystyle=$
$\displaystyle\sup_{\theta_{1},\theta_{2}}\sum_{t^{\prime}=1}^{s}\log
p_{\theta_{1}}(X_{t^{\prime}})+\sum_{t^{\prime}=s+1}^{t}\log
p_{\theta_{2}}(X_{t^{\prime}})-\sup_{\theta}\sum_{t^{\prime}=1}^{t}\log
p_{\theta}(X_{t^{\prime}})$ $\displaystyle=$ $\displaystyle
s\mathcal{L}^{\star}(F_{1:s})+(t-s)\mathcal{L}^{\star}(F_{s+1:t})-t\mathcal{L}^{\star}(F_{1:t})$
$\displaystyle=$ $\displaystyle
s(\mathcal{L}^{\star}(F_{1:s})-\mathcal{L}^{\star}(F_{1:t}))+(t-s)(\mathcal{L}^{\star}(F_{s+1:t})-\mathcal{L}^{\star}(F_{1:t}))\,,$

where $F_{s+1:t}=\frac{1}{t-s}\sum_{t^{\prime}=s+1}^{t}F(X_{t^{\prime}})$, and
it makes sense to introduce $\theta_{s+1:t}$ such that
$\nabla\mathcal{L}(\theta_{s+1:t})=F_{s+1:t}$. The GLR test is then defined,
for a threshold $\alpha$ as

$\displaystyle\tau(\alpha;\mathcal{E})$ $\displaystyle=$
$\displaystyle\min\\{t\in\mathbb{N}:\max_{s\in[0,t)}G^{\mathcal{E}}_{1:s:t}\geqslant\alpha\\}$

An alternative formulation of the GLR shows that

$\displaystyle G^{\mathcal{E}}_{1:s:t}$
$\displaystyle=\inf_{\theta}\sup_{\theta_{1},\theta_{2}}\log\bigg{(}\frac{\prod_{t^{\prime}=1}^{s}p_{\theta_{1}}(X_{t^{\prime}})\prod_{t^{\prime}=s+1}^{t}p_{\theta_{2}}(X_{t^{\prime}})}{\prod_{t^{\prime}=1}^{t}p_{\theta}(X_{t^{\prime}})}\bigg{)}$
$\displaystyle=\inf_{\theta}\sup_{\theta_{1},\theta_{2}}s\Big{(}\langle\theta_{1},F_{1:s}\rangle-\mathcal{L}(\theta_{1})-\langle\theta,F_{1:t}\rangle+\mathcal{L}(\theta)\Big{)}$
$\displaystyle\quad+(t-s)\Big{(}\langle\theta_{2},F_{s+1:t}\rangle-\mathcal{L}(\theta_{2})-\langle\theta,F_{1:t}\rangle+\mathcal{L}(\theta)\Big{)}\,.$

The first supremum is obtained for
$\theta_{1}=[\nabla\mathcal{L}]^{-1}(F_{1:s})$, with value equal to
$\mathcal{B}_{\mathcal{L}}(\theta,\theta_{1})+\langle\theta-\theta_{1},\nabla\mathcal{L}(\theta_{1})\rangle+\langle\theta_{1},F_{1:s}\rangle+\langle\theta_{1},F_{1_{t}}\rangle$,
that is
$\mathcal{B}_{\mathcal{L}}(\theta,\theta_{1:s})+\langle\theta,F_{1:s}-F_{1:t}\rangle$.
Likewise, the the second supremum is obtained for
$\theta_{2}=[\nabla\mathcal{L}]^{-1}(F_{s+1:t})$, with value equal to
$\mathcal{B}_{\mathcal{L}}(\theta,\theta_{s+1:t})+\langle\theta,F_{s+1:t}-F_{1:t}\rangle$.
Combining these two results, and remarking that
$s(F_{1:s}-F_{1:t})+(t-s)(F_{s+1:t}-F_{1:t})=0$, we obtain that

$\displaystyle G^{\mathcal{E}}_{1:s:t}$ $\displaystyle=$
$\displaystyle\inf_{\theta}s\mathcal{B}_{\mathcal{L}}(\theta,\theta_{1:s})+(t-s)\mathcal{B}_{\mathcal{L}}(\theta,\theta_{s+1:t})$
(15)

We further note that a solution to this optimization problem is obtained for
$\theta$ such that $s(\nabla L(\theta)-\nabla L(\theta_{1:s}))+(t-s)(\nabla
L(\theta)-\nabla L(\theta_{s+1:t}))=0$. Reorganizing the terms, this entails
that $\nabla L(\theta)=\frac{1}{t}(sF_{1:s}+(t-s)F_{s+1:t})=F_{1:t}$, and thus
(without surprise) $\theta=\theta_{1:t}$.

Written in the form (15), the GLR satisfies for any $\theta^{\prime}$,

$\displaystyle G^{\mathcal{E}}_{1:s:t}$ $\displaystyle\leqslant$
$\displaystyle
s\mathcal{B}_{\mathcal{L}}(\theta^{\prime},\theta_{1:s})+(t-s)\mathcal{B}_{\mathcal{L}}(\theta^{\prime},\theta_{s+1:t})\,.$

In particular, the false alarm rate of the GLR test, when all observations are
generated from parameter $\theta$, can be bounded using

$\displaystyle\mathbb{P}_{\theta}(\tau(\alpha;\mathcal{E})<\infty)$
$\displaystyle=$
$\displaystyle\mathbb{P}_{\theta}\big{(}\exists(t,s)\in\mathbb{N}^{2},s<t:G^{\mathcal{E}}_{1:s:t}\geqslant\alpha\big{)}$
$\displaystyle\leqslant$
$\displaystyle\mathbb{P}_{\theta}\Big{(}\exists(t,s)\in\mathbb{N}^{2},s<t:s\mathcal{B}_{\mathcal{L}}(\theta,\theta_{1:s})+(t-s)\mathcal{B}_{\mathcal{L}}(\theta,\theta_{s+1:t})\geqslant\alpha\Big{)}\,.$

At this point, provided that for appropriate terms $\alpha_{1},\alpha_{2}$,

$\displaystyle\mathbb{P}_{\theta}\Big{(}\exists
s\in\mathbb{N}:s\mathcal{B}_{\mathcal{L}}(\theta,\theta_{1:s})\geqslant\alpha_{2}\Big{)}\leqslant\frac{\delta}{2}\,,$
$\displaystyle\mathbb{P}_{\theta}\Big{(}\exists(t,s)\in\mathbb{N}^{2},s<t:(t-s)\mathcal{B}_{\mathcal{L}}(\theta,\theta_{s+1:t})\geqslant\alpha_{1}\Big{)}\leqslant\frac{\delta}{2}\,.$

we deduce by a simple union bound argument, and for
$\alpha=\alpha_{1}+\alpha_{2}$ that
$\mathbb{P}_{\theta}(\tau(\alpha:\mathcal{E})<\infty)\leqslant\delta$.

#### A regularized GLR test

Our concentration result shows that such a controlled can be obtained for a
penalized version of the maximum likelihood parameter estimates
$\theta_{1:s},\theta_{s+1,t},\theta_{1,t}$. Namely, let us consider the set

$\displaystyle\Theta_{s,c}(\delta)$ $\displaystyle=$
$\displaystyle\bigg{\\{}\theta\in\Theta:\exists
s\in\mathbb{N}:s\mathcal{B}_{\mathcal{L}}(\theta,\theta_{1:s,c}(\theta))\geqslant\alpha_{1}\bigg{\\}}\,,$
$\displaystyle\Theta_{s+1:t,c}(\delta)$ $\displaystyle=$
$\displaystyle\bigg{\\{}\theta\in\Theta:\exists(t,s)\in\mathbb{N}^{2},s<t:(t-s)\mathcal{B}_{\mathcal{L}}(\theta,\theta_{s+1:t,c}(\theta))\geqslant\alpha_{2}\bigg{\\}}\,.$

Provided that $\alpha_{1}$ and $\alpha_{2}$ are defined to ensure that these
are high-probability confidence sets for the parameter $\theta_{0}$, then they
should have non-empty intersections under $\mathbb{P}_{\theta}$. This
motivates the following definition of the regularized GLR-test:

$\displaystyle\tau^{\delta}_{c}(\mathcal{E})$ $\displaystyle=$
$\displaystyle\min\left\\{t\in\mathbb{N}:\exists
s\\!<\\!t,\Theta_{s,c}(\delta/2)\cap\Theta_{s+1:t,c}(\delta/2)=\emptyset\right\\}\,.$

The appropriate quantity for $\alpha_{1}$ is immediately obtained by Theorem 3
as $\frac{s}{s+c}(\log(1/\delta)+\gamma_{1:s,c}(\theta))$. Now for
$\alpha_{2}$, we need to study doubly-time uniform concentration inequalities
over both $s$ and $t$.

###  E.1 Doubly-time uniform concentration inequalities for exponential
families

See 5

Proof of Theorem 5:

We consider that all the $(X_{t^{\prime}})_{t^{\prime}\in\mathbb{N}}$ come
from a distribution with same parameter $\theta$. Let $t\in\mathbb{N}$ and
$s\in\\{0,\dots,t-1\\}$. We introduce the scan-mean
$\mu_{s+1:t}=\frac{1}{t-s}\sum_{t^{\prime}=s+1}^{t}F(X_{t^{\prime}})$ and its
mean $\mu=\nabla\mathcal{L}(\theta)$. We define as in the proof of Theorem 3,
for each $\lambda$ the martingale

$\displaystyle M_{s+1:t}^{\lambda}$ $\displaystyle=$
$\displaystyle\exp\bigg{(}\langle\lambda,(t-s)(\mu_{s+1:t}-\mu)\rangle-(t-s)\mathcal{B}_{\mathcal{L},\theta}(\lambda)\bigg{)}\,.$

Then, applying the method of mixture and replacing each term with its scan
version from $s+1$ to $t$, we introduce the quantity

$\displaystyle M_{s+1,t}$ $\displaystyle=$
$\displaystyle\exp\big{(}(t\\!-\\!s\\!+\\!c)\mathcal{B}_{\mathcal{L},\theta}^{\star}(x)\big{)}\frac{G(\theta,c)}{G(\theta_{s+1:t,c}(\theta_{0}),t-s+c)}$

where
$x=\frac{t\\!-\\!s}{t\\!-\\!s\\!+\\!c}(\mu_{s+1:t}-\nabla\mathcal{L}(\theta))$
and $\theta_{s+1:t,c}(\theta)$ is the regularized estimate from the scan
samples

$\displaystyle\theta_{s+1:t,c}(\theta)=(\nabla\mathcal{L})^{-1}\bigg{(}\frac{\sum_{t^{\prime}=s+1}^{t}F(X_{t^{\prime}})+c\nabla\mathcal{L}(\theta)}{t\\!-\\!s\\!+\\!c}\bigg{)}\,.$

Remarking that $\mathbb{E}[M_{t,t}]\leqslant\mathbb{E}[M_{t+1,t}]=1$ and that
$(M_{s+1,t})_{s}$ is a nonnegative supermartingale, we can now control its
doubly-time uniform deviations following the proof of Maillard (2019b)[Th.3.2,
p.58]. More precisely, for any non-decreasing function $g$, it can be shown
that

$\displaystyle\mathbb{P}_{\theta}\big{[}\exists t,\exists
s<t:M_{s+1,t}\geqslant\frac{g(t)}{\delta}\big{]}\leqslant\delta\mathbb{E}_{\theta}\Big{[}\max_{t}\max_{s<t}\frac{M_{s+1:t}}{g(t)}\Big{]}\leqslant\delta\sum_{t=1}^{\infty}\frac{1}{g(t)}\,.$

Rewriting the terms thanks to the duality formulas, yields

$\displaystyle\mathbb{P}_{\theta}\bigg{[}\exists t,\exists
s<t:(t\\!-\\!s\\!-\\!c)\mathcal{B}_{\mathcal{L}}(\theta,\theta_{s+1:t,c}(\theta))\geqslant\log\Big{(}\frac{g(t)}{\delta}\Big{)}+\gamma_{s+1:t,c}(\theta)\bigg{]}\leqslant\delta\sum_{t=1}^{\infty}\frac{1}{g(t)}\,.$

This suggests to set
$\alpha_{2}=\frac{t\\!-\\!s}{t\\!-\\!s\\!-\\!c}\left(\log\left(\frac{g(t)}{\delta}\right)+\gamma_{s+1:t,c}(\theta)\right)$
in the definition of the regularized GLR test. Putting all terms together,
this leads to the definition of the following regularized GLR test, for a
given false-detection error probability $\delta\in[0,1]$ and regularization
parameter $c$,

$\displaystyle\Theta_{s,c}(\delta)=\left\\{\theta\in\Theta:(s\\!+\\!c)\mathcal{B}_{\mathcal{L}}(\theta,\theta_{1:s,c}(\theta))\leqslant\log(1/\delta)+\gamma_{1:s,c}(\theta)\right\\}\,,$
$\displaystyle\Theta_{s+1:t,c}(\delta)=\left\\{\theta\in\Theta:(t\\!-\\!s+\\!c)\mathcal{B}_{\mathcal{L}}(\theta,\theta_{s+1:t,c}(\theta))\leqslant\log(g(t)/\delta)+\gamma_{s+1:t,c}(\theta)\right\\}\,,$
$\displaystyle\tau^{\delta}_{c}(\mathcal{E})=\min\left\\{t\in\mathbb{N}:\exists
s\\!<\\!t,\Theta_{s,c}(\delta/2)\cap\Theta_{s+1:t,c}(\delta/2)=\emptyset\right\\}\,.$

The factor $g(t)$ that inflates the width of the confidence set can be tuned
to satisfy $\sum_{t=1}^{+\infty}1/g(t)\leqslant 1$, thus controlling the above
deviation probability by at most $\delta$ (ideally,
$\sum_{t=1}^{+\infty}1/g(t)$ should be close to $1$ to avoid overinflating the
confidence width). A natural choice for this is
$g(t)=\kappa(1\\!+\\!t)\log^{2}(1\\!+\\!t)$ where
$\kappa=2.10974\geqslant\sum_{t=1}^{\infty}\frac{1}{(1\\!+\\!t)\log^{2}(1\\!+\\!t)}$
(for completeness, we derive in the next section an elementary way to
computing suitable values for $\kappa$). By construction, this test is
guaranteed to have a false-detection probability controlled by $\delta$ (that
is,
$\mathbb{P}_{\theta}(\tau^{\delta}_{c}(\mathcal{E})<\infty)\leqslant\delta$).

#### Doubly time-uniform control of supermartingale sequences

For completeness, we reproduce below the derivation from Maillard
(2019b)[Th.3.2, p.58], applied to our setup. First, let us note that

$\displaystyle\mathbb{P}\bigg{(}\exists t\\!\in\\!\mathbb{N}_{\star},\exists
s\\!\in\\![0,t-1],\,\,M_{s+1:t}\geqslant\frac{g(t)}{\delta}\bigg{)}$
$\displaystyle=$
$\displaystyle\mathbb{P}\bigg{(}\max_{t\in\mathbb{N}_{\star}}\max_{s\in[0,t-1]}\frac{M_{s+1:t}}{g(t)}\geqslant\frac{1}{\delta}\bigg{)}$
$\displaystyle\leqslant$
$\displaystyle\delta\mathbb{E}\bigg{[}\max_{t\in\mathbb{N}_{\star}}\max_{s\in[0,t-1]}\frac{M_{s+1:t}}{g(t)}\bigg{]}\,.$

Let us also denote $\tau$ the random stopping time corresponding to the first
occurrence $t$ of the event
$\max_{s\in[0,t-1]}\frac{M_{s+1:t}}{g(t)}\geqslant\frac{1}{\delta}$. It is
convenient to introduce the quantity
$\overline{M}_{t}=\frac{\sum_{s\in\\{0,\dots,t-1\\}}M_{s+1,t}}{g(t)}$ for each
$t\in\mathbb{N}_{\star}$. Since each $M_{s+1,t}$ and $g(t)$ is nonnegative, we
first get that for every random stopping time $\tau\in\mathbb{N}_{\star}$, the
following inequality holds:

$\displaystyle\mathbb{E}\bigg{[}\frac{\max_{s<\tau}M_{s+1,\tau}}{g(\tau)}\bigg{]}$
$\displaystyle\leqslant$
$\displaystyle\mathbb{E}\bigg{[}\overline{M}_{\tau}\bigg{]}=\mathbb{E}\bigg{[}\overline{M}_{1}+\sum_{t=1}^{\infty}(\overline{M}_{t+1}-\overline{M}_{t})\mathbb{I}\\{\tau>t\\}\bigg{]}\,.$

Furthermore, we note that, conveniently

$\displaystyle\overline{M}_{t+1}-\overline{M}_{t}$ $\displaystyle=$
$\displaystyle\frac{M_{t+1,t+1}}{g(t+1)}+\sum_{s=0}^{t-1}\bigg{(}\frac{M_{s+1,t+1}}{g(t+1)}-\frac{M_{s+1,t}}{g(t)}\bigg{)}\,.$

Next, by assumption, we note that
$\displaystyle{\mathbb{E}[M_{s+1,t+1}|\mathcal{F}_{t}]\leqslant M_{s+1,t}}$.
Thus, since $\mathbb{I}\\{\tau>t\\}\in\mathcal{F}_{t}$, we deduce that

$\displaystyle\mathbb{E}\bigg{[}\frac{\max_{s<\tau}M_{s+1,\tau}}{g(\tau)}\bigg{]}$
$\displaystyle\quad\leqslant\mathbb{E}\big{[}\overline{M}_{1}\big{]}+\sum_{t=1}^{\infty}\frac{\mathbb{E}[M_{t+1,t+1}]}{g(t+1)}+\sum_{t=1}^{\infty}\sum_{s<t}\mathbb{E}\bigg{[}\bigg{(}\frac{1}{g(t+1)}-\frac{1}{g(t)}\bigg{)}M_{s+1,t}\mathbb{I}\\{\tau>t\\}\bigg{]}$
$\displaystyle\quad=\mathbb{E}\big{[}\overline{M}_{1}\big{]}+\sum_{t=1}^{\infty}\frac{\mathbb{E}[M_{t+1,t+1}]}{g(t+1)}+\sum_{t=1}^{\infty}\sum_{s<t}\bigg{(}\frac{1}{g(t+1)}-\frac{1}{g(t)}\bigg{)}\underbrace{\mathbb{E}\bigg{[}M_{s+1,t}\mathbb{I}\\{\tau>t\\}\bigg{]}}_{\geqslant
0}\,.$

Hence, the assumption that $g$ is non-decreasing ensures that the last sum is
upper bounded by $0$. Since on the other hand
$\mathbb{E}[M_{t+1,t+1}]\leqslant 1$ holds for all $t$ (and thus
$\mathbb{E}\big{[}\overline{M}_{1}\big{]}\leqslant 1/g(1)$), we deduce that
the following inequality holds:

$\displaystyle\mathbb{E}\bigg{[}\frac{\max_{s<\tau}M_{s+1,\tau}}{g(\tau)}\bigg{]}$
$\displaystyle\leqslant$
$\displaystyle\frac{1}{g(1)}+\sum_{t=1}^{\infty}\frac{1}{g(t+1)}=\sum_{t=1}^{\infty}\frac{1}{g(t)}\leqslant
1\,.$

$\hfill\square$

###  E.2 Computing the inflating factor $g(t)$

The right-hand side of the doubly time-uniform confidence set of Theorem 5
involves a $\log g(t)/\delta$ term instead of $\log 1/\delta$ as in Theorem 3,
which is a by-product of the union-like argument used in the proof. Ideally,
$g(t)$ should grow as slow as possible with $t$ to avoid unnecessary looseness
in the confidence bound. That is however limited by the constraint
$\sum_{t=1}^{\infty}1/g(t)\leqslant 1$, which prohibits the use of a linearly
growing $g(t)$ (since $\sum_{t=1}^{\infty}1/t$ diverges). The choice
$g(t)=\kappa(1\\!+\\!t)\log^{1\\!+\\!\eta}(1\\!+\\!t)$ for some $\eta>0$ and
$\kappa>0$ guarantees that the series of inverses converges, although its
limit is not available in closed-form. However, it is sufficient to set
$\kappa$ to an upper bound on
$\sum_{t=1}^{\infty}\frac{1}{(1\\!+\\!t)\log^{1\\!+\\!\eta}(1\\!+\\!t)}$. The
following elementary lemma explains how to compute a tight value for $\kappa$.

###### Lemma 12

Let $f\colon t\in\mathbb{N}\mapsto(1\\!+\\!t)\log^{1\\!+\\!\eta}(1\\!+\\!t)$
and define $S_{p}=\sum_{t=1}^{p}1/f(t)$ for $p\in\mathbb{N}\cup\\{+\infty\\}$.
Then $S_{\infty}\leqslant S_{p}+\frac{1}{\eta\log(1+p)^{\eta}}$.

Proof of Lemma 12:

The function $f$ is nondecreasing and positive, therefore for $t\in\mathbb{N}$
and $x\in[t,t+1)$, it holds that $1/f(t+1)\leqslant 1/f(x)$. Integrating both
terms as functions of $x$ over the interval $[t,t+1)$ yields
$1/f(t+1)\leqslant\int_{t}^{t+1}1/f(x)dx$. Summing starting at $t=p$, we
further get the following sum-integral comparison:

$S_{\infty}-S_{p}\leqslant\int_{p}^{\infty}\frac{dx}{f(x)}\,.$

Finally, note that
$\frac{d}{dx}\frac{1}{\eta\log^{\eta}(1+x)}=-\frac{1}{f(x)}$, and thus
$\int_{p}^{\infty}\frac{dx}{f(x)}=\frac{1}{\eta\log(1+p)^{\eta}}$.
$\hfill\square$

This lemma shows that $\kappa=S_{p}+1/\log(1\\!+\\!p)$ for some $p\geqslant 1$
($\eta=1$) is a valid choice for the definition of the inflating factor
$g(t)$, and is straightforward to compute numerically. For $p=100$, we obtain
$\kappa\lesssim 2.10974$ and increasing $p$ only changes further digits.

###  E.3 Experiments on change point detection for Gaussian with unknown
variance

We illustrate the change point GLR test above in a numerical experiment as
follows. We consider the one-dimensional exponential family of centered
Gaussian distributions with unknown variance
$\mathcal{E}=\left\\{\mathcal{N}(0,\sigma^{2}),\sigma>0\right\\}$. A sequence
of independent random variables $(X_{t})_{t\in\mathbb{N}}$ is drawn from
$X_{t}\sim\mathcal{N}(0,\sigma_{0}^{2})$ if $t\leqslant t^{*}$ and from
$X_{t}\sim\mathcal{N}(0,\sigma_{1}^{2})$ if $t>t^{*}$, where $t^{*}=50$ and
$\sigma_{0}=1$ and $\sigma_{1}\in[1,2,3,4]$. Of note, this setting corresponds
to an open question in Maillard (2019a), which studies GLR tests in sub-
Gaussian families, which are adapted to the detection of changing means but
not variances. Detection times are reported as
$\min(\tau^{\delta}_{c}(\mathcal{E}),T)$ with $T=100$, and
$\tau^{\delta}_{c}(\mathcal{E})>T$ is interpreted as no change being detected.
For the doubly time-uniform confidence set in the definition of the
regularized GLR test, we use the factor
$g(t)=\kappa(1\\!+\\!t)\log^{2}(1\\!+\\!t)$ with $\kappa=2.10974$.

A practical motivation for this setting is, for instance, the design of
maintenance models for equipment: with time, a component of a physical system
(mechanical component, measuring instrument…) starts to wear off and while it
is still functioning (same output on average), it is more imprecise or less
stable (higher output variance); the goal of the maintenance agent is to
detect as early as possible such changes of regime in order to replace the
failing component before it breaks completely.

In Figure 14, we report the histograms of detection times across $1000$
independent simulations for increasingly abrupt changes of variance
($\sigma_{1}\in\\{1,2,3,4\\}$). As expected, the distribution of detection
times shifts closer to the actual change point $t^{*}$ when $\sigma_{1}$
increases, i.e., more obvious changes are detected earlier. This is confirmed
in Figure 15, where we report the median and interquartile range of detection
times for $\sigma_{1}\in[1,4]$.

We empirically validate in Figure 14(a) the control of the false positive
probability by at most $\delta=5\%$. However, the actual false positive rate
appears much lower ($0.2\%$), which is a consequence of the looseness of the
union bound involving the factor $g(t)$ in the doubly time-uniform confidence
set. Following Maillard (2019a), a sharper approach would involve a direct
concentration result on the pair $\left(\theta_{s,c},\theta_{s+1:t,c}\right)$
(i.e., in the terminology of Maillard (2019a), a joint bound, as opposed to
the current disjoint one). This is a nontrivial result which we leave for
future work. Finally, note that the high false negative rate of Figure 14(b)
(27.6%) is an artifact of thresholding the detection time at $T=100$;
increasing $T$ would enable later detections, thus reducing the number of
observed false negatives, at the cost of increasing the average detection
delay (as well as the computational burden of the experiment).

(a) $\sigma_{0}=\sigma_{1}=1$ (no change)

(b) $\sigma_{0}=1,\sigma_{1}=2$

(c) $\sigma_{0}=\sigma_{1}=3$

(d) $\sigma_{0}=1,\sigma_{1}=4$

Figure 14: Histograms of detection times $\tau^{\delta}_{c}(\mathcal{E})$ in
the Gaussian setting described in Appendix E.3. Green: correct detection
(negative in (a), positive in (b), (c) and (d)). Red: incorrect detection
(positive in (a), negative in (b), (c) and (d)). Black dashed line: change
point $t^{*}$. Figure 15: Detection time $\tau^{\delta}_{c}(\mathcal{E})$ in
the Gaussian setting described in Appendix E.3. Solid line: median detection
time. Shaded area: interquartile range of detection times (25th and 75th
percentiles). Black dashed line: change point $t^{*}$.

##  Appendix F Application: Linear Contextual Bandits

In this section, we apply Theorem 7 to build confidence sets in the well-known
linear bandit setting. We consider the setting of linear contextual bandits
(Auer et al., 2002; Abbasi-Yadkori et al., 2011), but with possibly arm-
dependent noise variance (heteroscedastic noise). An algorithm for this
problem chooses, at each round $t\in\mathbb{N}$, an action or arm
$A_{t}\\!\in\\!\mathcal{A}$, and subsequently observes a reward
$X_{t}=\theta^{\top}\varphi(A_{t})+\varepsilon_{t}$, where
$\varphi\\!:\mathcal{A}\to\mathbb{R}^{d}$ is a (fixed) map from actions to
their context vectors, $\theta\in\mathbb{R}^{d}$ is a vector of weights
unknown to the algorithm and given the action $A_{t}$,
$\varepsilon_{t}\sim\mathcal{N}(0,\sigma_{A_{t}}^{2}I)$ is a Gaussian noise
with known variance $\sigma^{2}_{A_{t}}$. The goal is to select actions to
maximize the expected cumulative reward $\sum_{t}\theta^{\top}\varphi(A_{t})$.
Any rational agent would choose the action $A_{t}$ causally depending upon the
history of arms and reward sequences available before the start of round $t$.
Naturally, for each $n\\!\in\\!\mathbb{N}$, it boils down to controlling the
deviation between the unknown parameter $\theta$ and a suitable estimate
$\theta_{n}$ built from $n$ observations $(A_{t},X_{t})_{t\leqslant n}$.

Under this observation model, the feature function and the log-partition
function are given by $F_{t}(x)=\frac{x}{\sigma_{A_{t}}^{2}}\varphi(A_{t})$
and
$\mathcal{L}_{t}(\theta)=\frac{1}{2\sigma_{A_{t}}^{2}}\|\theta\|^{2}_{\varphi(A_{t})\varphi(A_{t})^{\top}}$.
Let us define the matrix

$\displaystyle
V_{n}=\sum_{t=1}^{n}\frac{1}{\sigma_{A_{t}}^{2}}\varphi(A_{t})\varphi(A_{t})^{\top}\,,$

and introduce the Legendre function
$\mathcal{L}_{0}(\theta)=\frac{1}{2}\|\theta\|^{2}_{V_{0}}$, where $V_{0}$ is
some fixed positive definite matrix. Then, the parameter estimate and the
Bregman information gain take the form

$\displaystyle\theta_{n,\mathcal{L}_{0}}=\left(V_{n}+V_{0}\right)^{-1}\sum_{t=1}^{n}\frac{X_{t}}{\sigma_{A_{t}}^{2}}\varphi(A_{t})~{},\quad\gamma_{n,\mathcal{L}_{0}}=\log\frac{\det(V_{0}+V_{n})^{1/2}}{\det(V_{0})^{1/2}}~{}.$

Now, defining
$\mathcal{H}_{t-1}:=\\{A_{1},X_{1},\ldots,A_{t-1},X_{t-1},A_{t}\\}$ to be the
set of all information available before observing $X_{t}$, one can see that
the confidence set $\Theta_{n,\mathcal{L}_{0}}(\delta)$ given by Theorem 7 is
the set of all $\theta\in\Theta$ satisfying

$\displaystyle\|\theta-\theta_{n,\mathcal{L}_{0}}\|^{2}_{V_{n}+V_{0}}\leqslant\|\theta\|^{2}_{V_{0}}+2\log\frac{\det(V_{0}+V_{n})^{1/2}}{\delta\det(V_{0})^{1/2}}.$

#### Comparison with Existing Results

Under the assumption that the noise $\varepsilon_{t}$ is $\sigma_{A_{t}}$-sub-
Gaussian conditioned on $\mathcal{H}_{t-1}$, Abbasi-Yadkori et al. (2011);
Kirschner and Krause (2018) obtain a high-probability confidence set
$\widetilde{\Theta}_{n,\mathcal{L}_{0}}(\delta)$, which is the set of all
$\theta\in\Theta$ satisfying

$\displaystyle\|\theta-\theta_{n,\mathcal{L}_{0}}\|_{V_{n}+V_{0}}\leqslant\|\theta\|_{V_{0}}+\sqrt{2\log\frac{\det(V_{0}+V_{n})^{1/2}}{\delta\det(V_{0})^{1/2}}}.$

Interestingly, since $\sqrt{a+b}\leqslant\sqrt{a}+\sqrt{b}$ for positive
$a,b$, it is then clear that
$\Theta_{n,\mathcal{L}_{0}}(\delta)\subset\widetilde{\Theta}_{n,\mathcal{L}_{0}}(\delta)$.
In particular, as a side result of our approach, we obtain a tighter
confidence set compared to them.