Partition Tree Weighting for Non-Stationary Stochastic Bandits

ArXiv: 2502.19325

🎯 Pitch

Sampling actions from a universal code for agent–environment interactions creates a bandit policy that quietly self-destructs when feedback is deceptive—unless explicit countermeasures against self-delusion are baked in. The authors show that a forced-exploration variant of their ActivePTW algorithm not only avoids this trap but slashes regret 4–10× below Sliding Window UCB on problems where the best arm’s reward never changes.

---

1. Executive Summary

This paper introduces ActivePTW, a universal source coding approach to the non-stationary stochastic Bernoulli bandit problem that generalizes the Partition Tree Weighting technique from passive prediction to interactive control. Operating on synthetic bandit environments with up to 50 arms and geometrically distributed change-points, ActivePTW performs Bayesian inference over a hierarchical class of binary temporal partitions (efficiently aggregating posterior beliefs across all possible restart schedules via the PTW-KT environment measure) and samples actions from either a Maximum Expected Utility policy or a forced-exploration variant. The MEU variant reduces to classic Thompson Sampling in stationary settings and achieves 4–10× lower regret than Sliding Window UCB and MASTER across moderate change-point rates (e.g., 4873 vs. 8697 cumulative regret for 2 arms at change rate p=0.01), while the forced-exploration variant proves essential on adversarial change-point regimes where the optimal arm's expected reward remains unchanged across segments, establishing that principled compression-based control policies can match or exceed specialized non-stationary bandit algorithms — but only when the reference policy class includes mechanisms for distinguishing informative from deceptive action feedback.

2. Context and Motivation

The Core Problem: Making Sequential Decisions When the World Keeps Changing

This paper addresses a fundamental challenge in sequential decision-making: how should an agent choose actions to maximize reward when the underlying reward probabilities can change abruptly at unknown times? This is the non-stationary stochastic bandit problem — a generalization of the classic multi-armed bandit where the environment is not static but instead undergoes structural shifts. In a stationary bandit, each arm has a fixed (but unknown) reward probability; the agent's job is to balance exploration (trying arms to learn their values) against exploitation (playing the arm that currently seems best). In the non-stationary version, these probabilities can jump at arbitrary change-points, forcing the agent not only to learn arm values but also to detect when the world has changed and discard outdated information.

The problem is "challenging" in the specific sense the authors emphasize (Section 1): the agent must "provide algorithms with good worst-case guarantees without unrealistic knowledge of the change-point structure in advance." If you knew exactly when changes would occur, you could simply restart a stationary algorithm at each change-point. If you knew nothing and treated the environment as stationary, you would eventually converge to an arm and stop exploring, missing subsequent changes entirely. The practical reality sits between these extremes — changes happen, but their timing and structure are unknown.

Why This Problem Matters

Practical significance. Non-stationary bandit problems appear pervasively in real-world applications where environments drift or shift. Consider:

• Online advertising and recommendation systems: User preferences evolve over time (seasonal trends, life events, cultural shifts). An ad placement algorithm optimized for last month's click-through rates may perform poorly this month. The abrupt-change model captures regime shifts like a new competitor entering the market or a product going viral.
• Clinical trials and adaptive treatment allocation: Patient populations change across sites or over time. A treatment that appears optimal in early trial phases may prove less effective as the study population broadens.
• Dynamic pricing and revenue management: Consumer demand functions shift with economic conditions, competitor actions, or supply chain disruptions.
• Automated A/B testing: When running continuous experiments, the baseline conversion rate can drift due to external factors, requiring algorithms that don't naively average over stale data.

In all these settings, an algorithm that assumes stationarity will gradually stop exploring as its confidence in arm estimates grows, making it blind to subsequent changes. The practical cost is missed revenue, suboptimal treatments, or incorrect experimental conclusions.

Theoretical significance. The non-stationary bandit problem sits at the intersection of several important theoretical areas: online learning, change-point detection, and Bayesian inference over temporal structure. It forces us to confront a tension that stationary bandits avoid: how much of the past should influence current decisions? The answer depends on how quickly the environment changes, which the agent doesn't know. This makes the problem fundamentally harder — there is no static optimal policy, and algorithms must be adaptive in a stronger sense than just tuning exploration rates.

The paper also positions the problem within a broader intellectual tradition: using compression and universal source coding as a foundation for building agents. This perspective, traced back to Wiener's cybernetic model, views an agent as "a type of entropy-constrained adaptive process coupled to an input/output channel" (Section 7). Rather than appealing to expected utility maximization (as in standard RL and bandit theory), the compression view asks: can we construct a universal coding scheme that losslessly describes agent-environment interactions, then sample from that coding distribution to generate a control policy? This reframes the bandit problem not as regret minimization per se, but as a coding problem where the agent tries to minimize the number of bits needed to describe the history of actions and percepts. The non-stationary bandit becomes a testbed for whether this philosophical stance produces practically useful algorithms.

Where Existing Approaches Fall Short

The paper identifies several families of prior approaches and their limitations (Section 1):

Windowing and discounting methods (passive adaptation). The simplest response to non-stationarity is to restrict attention to recent data. Sliding Window UCB (Garivier and Moulines, 2008) computes its upper confidence bounds using only the last $W$ observations — older data simply falls out of the window. Discounted variants weight recent data more heavily. Thompson Sampling has been adapted similarly (Trovò et al., 2020).

The critical weakness: these methods require knowing a good hyperparameter in advance. The window size $W$ or discount factor must be matched to the expected rate of change. If $W$ is too small, the algorithm cannot accumulate enough data within a stable segment to identify the best arm — it's perpetually exploring. If $W$ is too large, stale data from previous segments contaminates current estimates — the algorithm is slow to adapt. The paper explicitly notes that in their experiments, Sliding Window UCB's window size was "set assuming that we knew the expected length of each segment in advance" (Section 6), making its results "somewhat best-case." In practice, this information is rarely available, and poor hyperparameter choices can devastate performance.

More subtly, windowing methods make a binary, hard-cutoff decision about which data to include. In reality, when a change-point occurs, the agent may not need to discard all pre-change data — some arms might have unchanged reward probabilities, and even changed arms provide partial information about their new values if the change is small. Windowing throws away potentially useful information indiscriminately.

Stochastic restarting meta-algorithms. A more recent and promising approach, exemplified by MASTER (Wei and Luo, 2021), takes a stationary bandit algorithm as a black box and superimposes a stochastic restarting schedule on top. The idea is elegant: rather than manually tuning a window size, run the base algorithm and periodically restart it (discard all history and begin fresh) with some probability. The restarting probability is derived from the base algorithm's known regret properties, providing theoretical guarantees without requiring advance knowledge of the change-point structure.

The limitation: MASTER essentially runs one restarting schedule at a time — it makes a stochastic decision about whether to restart and commits to it. If the base algorithm has been running too long and missed a change-point, the meta-algorithm must wait for the next probabilistic restart opportunity. More fundamentally, the stochastic restarting approach doesn't maintain a posterior over which restart schedule is likely correct given the observed data. It's a forward-sampling approach, not a Bayesian inference approach.

Stationary algorithms applied naively. Standard algorithms like UCB1, Thompson Sampling, and KL-UCB are designed for stationary environments and have no mechanism for detecting or adapting to change-points. Their exploration rates decrease over time (UCB's confidence bounds narrow, Thompson Sampling's posteriors concentrate), meaning they become increasingly committed to their current estimates and increasingly blind to new information. In non-stationary settings, these algorithms can suffer linear regret — perpetually playing a suboptimal arm because they stopped exploring before a change made it optimal.

A concrete illustration the paper provides (Section 6, the "adversarial case"): in an environment where the optimal arm in segment 1 has the same expected reward in segment 2, but a different arm becomes superior in segment 2, a standard Thompson Sampling agent will keep playing the former best arm (since it continues yielding the same rewards), never discovering that another arm now offers higher returns. The agent gets no negative feedback that would trigger re-exploration — the old-best arm still looks good, so why look elsewhere? This is a failure mode specific to the interaction between exploration and non-stationarity: the agent's own policy choice (exploiting what appears best) prevents it from gathering the data needed to detect a change.

The self-delusion problem. The paper highlights a deeper conceptual issue that arises when trying to apply compression-based approaches to control (Section 1, Section 3). In the passive prediction setting — where you only observe a stream of data without taking actions — universal source coding techniques like Partition Tree Weighting (Veness et al., 2013) work beautifully for non-stationary sources. You maintain a Bayesian mixture over all possible temporal partitions of the data stream and use the posterior predictive distribution for coding. The technique has strong theoretical guarantees and efficient algorithms.

The problem when moving to control: the agent's actions determine which data it observes. If you naively apply the same compression framework — treating actions and observations symmetrically, just coding the combined stream — you run into the self-delusion problem (Ortega et al., 2021). The agent can "delude" itself into believing it's in an environment where its policy is optimal, because it never collects the data that would falsify that belief. Formally, the agent's own policy choice affects the observations, and the posterior over environments can become pathological if the policy doesn't ensure sufficient exploration.

The paper's Section 2 notation clarifies the distinction: an agent-environment interaction measure $\nu_\pi(h_{1:t})$ decomposes into an environment component $\mu(e_{1:t} || a_{1:t})$ (the probability of percepts given interventions on actions) and a policy component $\pi(a_{1:t} || e_{1:t})$ (the probability of actions given interventions on percepts). The $||$ notation signals that these are interventions, not conditionals — the actions are chosen by the agent, not observed from nature. In the passive prediction case, there are no actions (or equivalently, there's only one "action" — just observe), so this distinction collapses. In the control case, failing to distinguish actions from observations means you might code the agent's own policy choices as if they were informative about the environment, creating circular reasoning.

This is why the paper cannot simply apply Partition Tree Weighting directly to the combined action-percept stream. The environment model (PTW-KTE) must be built only on the percepts, conditioned on the actions (which are treated as interventions). The policy must be constructed separately, and must respect the informational constraints of the reinforcement learning setup — it can only condition on data the environment has actually revealed, not on counterfactual data from actions it didn't take.

How This Paper Positions Itself

The paper occupies a specific and novel intersection: it adapts the Partition Tree Weighting technique — originally developed for passive prediction of non-stationary sources (Veness et al., 2013) — to the control setting while carefully handling the self-delusion problem. This is not a straightforward generalization, as the previous paragraph explains. The key intellectual move is to separate the coding problem into two parts:

1. Environment coding (passive prediction on percepts given actions): Use a hierarchical Bayesian model over temporal partitions, where within each segment, each arm's reward probability is modeled by a Krichevsky-Trofimov (KT) estimator. This yields the PTW-KTE environment measure (Equation 7), which maintains a posterior over all possible segmentations of the history and efficiently computes predictive probabilities. This part is a direct adaptation of Veness et al. (2013) but applied to a structured percept space (one KT estimator per arm) rather than a simple binary sequence.

2. Policy construction (sampling actions that work well across possible environments): Use the posterior over environments to construct a policy via the Bayesian Control Rule (Ortega and Braun, 2008, 2012). At each step, the agent samples a segment from the PTW posterior, samples arm parameters for that segment, and then acts according to a reference policy (either greedy with respect to the sampled parameters, or greedily with forced exploration). This is the component that generalizes Thompson Sampling to the non-stationary setting — the PTW posterior over segments replaces the standard Beta-Bernoulli posterior over fixed arm parameters.

The paper explicitly connects this to Thompson Sampling: "structurally, the ActivePTW algorithm is very similar to the classic Thompson Sampling algorithm for stationary environments, only with the additional step of first sampling an active segment from the PTW posterior" (Section 5.2). This is not a coincidence — it's a consequence of the Bayesian Control Rule formulation, where the policy that minimizes expected coding cost is equivalent to Thompson Sampling when the reference policy is the greedy optimal policy for each environment.

Relative to MASTER: Both ActivePTW and MASTER can be seen as meta-algorithms that handle non-stationarity by running multiple virtual instances of a stationary algorithm. But they differ fundamentally in how they combine these instances. MASTER runs one instance at a time and stochastically restarts based on regret bounds — it's a sampling-based approach. ActivePTW maintains a posterior over all possible segmentation structures simultaneously and uses Bayesian model averaging — it's an inference-based approach. The PTW posterior implicitly runs all possible restart schedules in parallel, weighted by their posterior probability given the data. When the environment is stationary, the posterior concentrates on segmentations that cover the entire history with a single segment, and ActivePTW collapses to classic Thompson Sampling (as shown in Figure 3). When change-points occur, the posterior shifts toward segmentations that place boundaries at the change-points, and the algorithm naturally adapts.

Relative to Sliding Window methods: ActivePTW replaces the hard-coded window size with a Bayesian prior over segment lengths. The PTW prior (encoded in the tree structure and the $\gamma$ parameter) assigns higher prior probability to certain types of segment structures, but the posterior updates based on the actual observed data. A key insight from Section 5.3: the parameter $\gamma$ in the PTW recurrence (Equation 9) controls the bias toward simple (few segments) versus complex (many segments) partition structures. The paper sets $\gamma = A/(A+1)$ based on a worst-case redundancy argument, making the prior adapt to the number of arms — with more arms, simpler partition structures are favored because learning within each segment is harder. This is a principled way to trade off the difficulty of detecting change-points against the difficulty of learning arm values, without requiring the user to specify a window size.

Relative to stationary bandit algorithms: ActivePTW is designed to gracefully degrade to stationary performance when the environment is actually stationary, rather than incurring an unnecessary penalty for being change-point-aware. Figure 3 demonstrates this: in the stationary setting, ActivePTW with the MEU policy achieves "nearly identical" performance to Thompson Sampling. This is not automatic — many change-point-aware algorithms (like windowing methods with fixed windows) pay a permanent efficiency cost because they intentionally ignore older data. The PTW posterior's ability to recognize that a single-segment partition best explains the data is what prevents this degradation.

The broader philosophical positioning (Section 7): The paper situates itself within a line of work that views agents as compression systems — building on Ortega and Braun's Bayesian Control Rule, which in turn builds on Wiener's cybernetic model. This perspective is offered as an alternative to the standard decision-theoretic framework (maximize expected utility) that dominates reinforcement learning and bandit research. The appeal is that compression is a "norm-free" objective — it doesn't require specifying a reward function or utility, only the goal of efficiently describing interaction data. The paper suggests that this perspective is "a promising avenue for further investigation" beyond just the bandit setting, hinting that other universal source coding techniques could similarly be generalized to yield agents with interesting properties.

What the paper is NOT claiming: The paper does not claim to solve the non-stationary bandit problem in general. Section 5 acknowledges this: "A general solution is of course impossible, since the change-point structure might be too rapid to allow for sufficient periods of exploitation." The focus is on regimes "where the change-point structure is simple enough" — specifically, regimes where a binary temporal partition of depth $D$ can approximately capture the true change-point structure. This is an important scope limitation: if changes occur too frequently relative to the number of arms, no algorithm can identify optimal arms within the short stable periods. The theoretical analysis (Section 5.3) provides concentration results under forced exploration that suggest when ActivePTW should work well, but these are plausibility arguments rather than finite-time regret bounds for the general case.

3. Technical Approach

3.1 Reader Orientation

This paper constructs a control algorithm for non-stationary bandits by treating the agent-environment interaction as a compression problem: the agent maintains a hierarchical Bayesian model over all possible ways the reward statistics could change over time (encoded as temporal partitions), computes the posterior probability of each possible segmentation given the observed rewards, and then samples actions from a policy that minimizes expected coding cost — which reduces to Thompson Sampling generalized across an ensemble of possible restart schedules. The system solves the problem of unknown change-point structure by running all possible restart schedules in parallel, weighted by their posterior probability given the data, so that the agent naturally adapts to the actual change-point regime without requiring the user to specify a window size, discount factor, or restart rate in advance.

3.2 Big-Picture Architecture

The ActivePTW system has four major components that interact in a cycle:

1. PTW-KT Environment Measure — a hierarchical Bayesian model that assigns a probability to every possible temporal partition of the interaction history (up to some maximum depth $D$), where within each segment, each arm's reward probability is modeled by a Krichevsky-Trofimov (KT) estimator. This component consumes the stream of action-percept pairs and maintains a posterior over all segment structures.

2. Active Segment Posterior — a computationally efficient extractor that, at each time step $t$, computes the posterior probability $q_t((c,d))$ of each "active segment" — the $D+1$ segments of varying lengths ($2^0, 2^1, \ldots, 2^D$) that could cover the current time point under any binary temporal partition in the model class. This collapses the exponentially many possible partitions into a tractable set of $D+1$ hypotheses.

3. Reference Policy Class — a specification of what action the agent should take if it knew the true segment structure and arm parameters. Two variants are provided: the Maximum Expected Utility (MEU) policy, which greedily plays the arm with highest expected reward; and the Maximum Expected Utility with Forced Exploration (MEUFE) policy, which adds segment-length-dependent random exploration to prevent the agent from becoming stuck on a previously-optimal arm.

4. Hierarchical Thompson Sampling — the action-generation mechanism that first samples an active segment from $q_t(\cdot)$, then samples arm parameters for that segment from the posterior Beta distributions (conditioning only on data within that segment), constructs a virtual environment matching those parameters, and finally acts according to the reference policy for that environment. This procedure exactly implements the Bayesian Control Rule for the PTW-KT posterior.

Information flows cyclically: the agent samples an action via hierarchical Thompson Sampling → transmits it to the environment → receives a percept (reward) → updates the PTW-KT environment measure's sufficient statistics → recomputes the active segment posterior → repeat. The environment measure is updated using dynamic programming in $O(D)$ time per step, keeping the whole system online and efficient.

3.3 Roadmap for the Deep Dive

• First, the foundations: the Krichevsky-Trofimov estimator and the KT Environment (KTE), which provides the universal environment measure for a single stationary Bernoulli bandit segment. This is the base learner that sits at the leaves of the partition tree — understanding it is prerequisite for everything else, and it establishes the redundancy bound (Equation 5) that drives the theoretical analysis.
• Second, the PTW-KTE environment measure (Equation 7), which hierarchically combines KTE instances using the Partition Tree Weighting recurrence. We'll explain the class of binary temporal partitions, the tree-structured prior, the recursive computation, and the redundancy guarantee (Theorem 4) that extends the stationary bound to the piecewise-stationary case.
• Third, the active segment posterior — how the posterior over partitions collapses to a posterior over $D+1$ active segments, why this is both computationally tractable and statistically sufficient for action selection, and the recurrence (Lemma 5, Equation 9) that enables $O(D)$ updates.
• Fourth, the ActivePTW algorithm itself (Algorithm 1 and its efficient implementation), showing how hierarchical Thompson Sampling emerges from the Bayesian Control Rule applied to the PTW-KT posterior, and distinguishing the two reference policy variants (MEU vs. MEUFE).
• Fifth, the theoretical analysis (Section 5.3), which provides concentration arguments for the forced-exploration variant using Hoeffding bounds and KT posterior tail inequalities, and explains the modified PTW prior ($\gamma = A/(A+1)$) that improves worst-case redundancy by adapting the partition-structure bias to the number of arms.

3.4 Detailed, Sentence-Based Technical Breakdown

This is primarily a methodology paper that adapts a universal source coding technique (Partition Tree Weighting) from passive prediction to interactive control, with the specific application to non-stationary stochastic bandits. The core idea is that by maintaining a Bayesian mixture over all binary temporal partitions of the interaction history, the agent can implicitly run all possible restart schedules in parallel — and by sampling actions from the induced posterior over current-segment parameters, it obtains a natural generalization of Thompson Sampling to the non-stationary setting.

---

Krichevsky-Trofimov Estimator (KT Estimator)

The KT estimator is the atomic unit of universal modeling in this paper — it provides a probability distribution over binary sequences that performs well (in a redundancy sense) for any unknown Bernoulli parameter $\theta$, without needing to know $\theta$ in advance. Every arm in every segment of the PTW-KT model uses a separate KT estimator to track its observed successes and failures.

Bayesian derivation. The KT estimator arises from a Bayesian analysis that combines a Binomial likelihood with Jeffreys prior. Jeffreys prior for a Bernoulli parameter is:

$w_J(\theta) := \frac{1}{\pi}[\theta(1-\theta)]^{-1/2}$

where $\theta \in [0,1]$ is the unknown success probability of the Bernoulli distribution. This prior is the Jeffreys non-informative prior for the Bernoulli family — it is invariant under reparameterization and places higher density near 0 and 1 than a uniform prior, reflecting the fact that extreme probabilities are more informative.

What it computes: Jeffreys prior assigns a probability density to each possible value of the Bernoulli parameter $\theta$. The density is proportional to $1/\sqrt{\theta(1-\theta)}$, meaning it diverges (goes to infinity) as $\theta$ approaches 0 or 1. This encodes the prior belief that extreme success probabilities are more common than intermediate ones — or equivalently, that observing a string of identical outcomes is not strong evidence that the probability is extreme, because the prior already expects that possibility.

Why this form: Jeffreys prior is the unique prior that makes the Bayesian posterior depend only on the data (not on the parameterization), and it is the "least informative" prior in a formal information-geometric sense. For the Bernoulli family, using a uniform prior would produce different inferences than using a log-odds parameterization, but Jeffreys prior is invariant. This matters for universal coding because we want a single prior that works for any $\theta$ without tuning.

The KT probability of a binary string $x_{1:n} \in \{0,1\}^n$ is defined as the marginal likelihood under Jeffreys prior:

$\text{kt}(x_{1:n}) \equiv P_{\text{KT}}(\#0, \#1) := \int_0^1 w_J(\theta) \text{Binomial}_\theta(x_{1:n}) d\theta = \frac{1}{\pi} B\left(\#0 + \tfrac{1}{2}, \#1 + \tfrac{1}{2}\right)$

where:

• $\#0$ and $\#1$ are the counts of zeros and ones in $x_{1:n}$,
• $\text{Binomial}_\theta(x_{1:n}) := \theta^{\#1}(1-\theta)^{\#0}$ is the likelihood of observing the sequence $x_{1:n}$ under parameter $\theta$,
• $B(\alpha, \beta) = \Gamma(\alpha)\Gamma(\beta)/\Gamma(\alpha+\beta)$ is the Beta function (the normalizing constant of the Beta distribution),
• and the closed-form equality exploits that Jeffreys prior is $\text{Beta}(\tfrac{1}{2}, \tfrac{1}{2})$, making the posterior a $\text{Beta}(\#1 + \tfrac{1}{2}, \#0 + \tfrac{1}{2})$ distribution whose normalizing constant is $B(\#1 + \tfrac{1}{2}, \#0 + \tfrac{1}{2})$.

What it computes, operationally: given counts of successes ($\#1$) and failures ($\#0$) for a binary sequence, this formula produces a single probability — the marginal probability of observing that exact sequence of outcomes, averaged over all possible values of $\theta$ according to Jeffreys prior. It does NOT require knowing $\theta$; it automatically averages over the uncertainty. For a new observation $x_{n+1}$, the predictive probability is:

$\text{kt}(x_{n+1} = 1 \mid x_{1:n}) = \frac{\#1 + 1/2}{n + 1}$

which is simply the posterior mean of the Beta distribution — Laplace's rule of succession with pseudocounts of $1/2$ rather than $1$.

Why this form: the KT estimator's key property is its redundancy bound. For any binary string $x_{1:n}$ and any true parameter $\theta \in [0,1]$, the excess coding cost (in bits) of using the KT estimator instead of knowing $\theta$ exactly is bounded by:

$-\log_2 \text{kt}(x_{1:n}) + \log_2 \text{Binomial}_\theta(x_{1:n}) \leq \frac{1}{2}\log_2(n) + 1$

where the left-hand side is the KT redundancy: the difference between the ideal code length under the true $\theta$ and the code length under the universal KT estimator. This bound grows only logarithmically with the sequence length $n$ — it is $o(n)$, meaning the KT estimator is universal for the class of Bernoulli sources. The $1/2$ factor in front of the log is optimal; no universal code can achieve a smaller constant. The additive $+1$ is a small constant overhead.

The KT estimator can be updated online using $O(1)$ time and space per observation: maintain two counters ($\#0$ and $\#1$) and compute predictive probabilities using the closed form.

---

Krichevsky-Trofimov Environment (KTE)

The KTE generalizes the KT estimator from a single binary sequence to the bandit setting, where we observe a stream of percepts (rewards) that are interleaved with actions, and different actions have different unknown reward probabilities.

Construction. The KTE maintains an independent KT estimator for each arm $a \in \mathcal{A}$. At any time $t$, given the history of actions $a_{1:t}$ and percepts $e_{1:t}$, the KTE probability of the percept sequence is:

$\text{kte}(e_{1:t} \mid\mid a_{1:t}) := \prod_{a \in \mathcal{A}} \text{kt}(e^a_{1:t})$

where $e^a_{1:t}$ is the subsequence of percepts $e_i$ such that $a_i = a$ for all $1 \leq i \leq t$ — that is, it extracts only the rewards received when arm $a$ was pulled, preserving their order. Each arm's extracted subsequence is modeled by its own KT estimator.

What it computes, operationally: given the full history of actions and rewards, the KTE probability is the product of KT probabilities for each arm's reward subsequence. This treats arms as independent — pulling arm $a$ provides no information about arm $b$'s reward distribution. The product form means the total probability factorizes across arms; the $||$ notation emphasizes that actions are interventions (the agent chose which arms to pull) rather than random variables to be modeled.

Why this form: the factorization across arms is the natural extension of the stationary Bernoulli bandit model. Each arm's reward probability $\theta_a$ is an independent Bernoulli parameter with Jeffreys prior, and observations for different arms are independent given their parameters. The product structure means the KTE can be maintained with an $|\mathcal{A}|$-sized array of $(a, b)$ counters — two integers per arm tracking successes and failures. Update time is $O(1)$ per step (increment the counter for the pulled arm), and predictive probabilities for any arm can be computed on demand.

Redundancy guarantee (Proposition 2). The KTE's redundancy with respect to any stationary Bernoulli bandit environment $\mu$ with true parameters $\Theta = (\theta_1, \ldots, \theta_A)$ is bounded by:

$-\log_2 \text{kte}(e_{1:t} \mid\mid a_{1:t}) + \log_2 \mu(e_{1:t} \mid\mid a_{1:t}) \leq \frac{|\mathcal{A}'|}{2} \log_2\left(\frac{n}{|\mathcal{A}'|}\right) + |\mathcal{A}'|$

where $\mathcal{A}' := \{a \in \mathcal{A} : \ell(e^a_{1:t}) > 0\}$ is the set of arms that have been pulled at least once, and $n = t$ is the total number of time steps.

What this bound means: the excess cost of using the universal KTE instead of knowing the true $\theta_a$ values is at most $|\mathcal{A}'|/2$ bits per pulled arm times the log of the average number of pulls per arm, plus a linear overhead of $|\mathcal{A}'|$ bits. Arms that are never pulled ($a \notin \mathcal{A}'$) contribute zero redundancy because there is no data to code. The bound depends on $|\mathcal{A}'|$, not $|\mathcal{A}|$ — you only pay for arms you actually explore.

Proof sketch (from the paper): Step (a) expands the definition; step (b) rearranges to apply the per-arm KT bound from Equation 5; step (c) applies the KT redundancy bound to each arm's subsequence, giving $\frac{1}{2}\log_2(\ell(e^a_{1:t})) + 1$ per arm; step (d) maximizes the worst case over how the $n$ observations are distributed across the $|\mathcal{A}'|$ arms — by concavity of the logarithm, the sum is maximized when observations are split evenly, giving $\frac{|\mathcal{A}'|}{2}\log_2(n/|\mathcal{A}'|) + |\mathcal{A}'|$.

Why this form matters: this bound establishes that the KTE is a universal environment measure for stationary Bernoulli bandits. The redundancy is sublinear in $t$ (it grows logarithmically), meaning the KTE's predictions converge to the true environment's probabilities as more data is collected — for any sequence of arm pulls. This universality is the foundation on which the non-stationary extension is built.

---

Binary Temporal Partitions and the PTW Prior

The PTW-KT environment measure extends the KTE to non-stationary settings by placing a hierarchical prior over binary temporal partitions — ways of dividing the timeline into segments within which the environment is stationary.

Definition 3 (Binary Temporal Partitions). Given a depth parameter $D \in \mathbb{N}$ and a time $t \in \mathbb{N}$, the set $\mathcal{C}_D(t)$ of all binary temporal partitions from $t$ is defined recursively:

$\mathcal{C}_D(t) := \left\{ \{(t, t + 2^D - 1)\} \right\} \cup \left\{ S_1 \cup S_2 : S_1 \in \mathcal{C}_{D-1}(t), S_2 \in \mathcal{C}_{D-1}(t + 2^{D-1}) \right\}$

with the base case $\mathcal{C}_0(t) := \{\{(t, t)\}\}$.

What this defines: each element of $\mathcal{C}_D(t)$ is a set of non-overlapping segments (pairs $(c,d)$ with $c \leq d$) whose union covers the time interval $[t, t+2^D-1]$. The recursion says: either treat the entire interval as one segment (the first option), or split it at the midpoint $t + 2^{D-1}$ and recursively partition the left half and right half independently, then take their union (the second option).

Example ($D=2$, from the paper): $\mathcal{C}_2 = \{\{(1,4)\}, \{(1,2),(3,4)\}, \{(1,1),(2,2),(3,4)\}, \{(1,2),(3,3),(4,4)\}, \{(1,1),(2,2),(3,3),(4,4)\}\}$

The five partitions range from the coarsest (one segment of length 4) to the finest (four segments of length 1), with all possible binary refinements in between.

Tree representation. Each binary temporal partition corresponds to a binary tree (called a "partition tree") where internal nodes represent split decisions and leaf nodes represent the actual segments used. The root covers $\{1, \ldots, 2^D\}$; a split creates two children covering the left and right halves; leaves that are not split further become the segments in the final partition. This tree structure is what enables the efficient dynamic programming algorithms later.

Covering property (key fact). Given any arbitrary partition $P$ of consecutive time indices up to $2^D$, there exists some binary temporal partition $P' \in \mathcal{C}_D$ that "covers" $P$, meaning $\mathcal{T}(P) = \mathcal{T}(P')$ (they cover the same set of time indices) and every segment endpoint in $P$ appears in $P'$. Furthermore, there always exists a covering binary partition with no more than $|P|(\lceil \log n \rceil + 1)$ segments. This property, from Veness et al. (2013, Lemma 2), means that the class $\mathcal{C}_D$ is rich enough to approximate any change-point structure — you pay only a logarithmic factor in the number of segments relative to the true (unknown) partition.

Why this class: the binary tree structure is a computational sweet spot. Exhaustive search over all possible partitions would be intractable (the number of partitions grows exponentially with $2^D$), but the recursive binary decomposition enables $O(D)$ updates via dynamic programming while still covering essentially all partitions with only a mild overhead. The depth $D$ controls the maximum total time horizon ($T \leq 2^D$) and the granularity of detectable change-points (changes can only occur at dyadic boundaries — times that are multiples of powers of 2). This imposes a resolution constraint: if a real change-point occurs at time 7 in a $2^4 = 16$-step horizon, the PTW model cannot place a segment boundary exactly at 7; it can only approximate it with boundaries at 4, 8, or similar dyadic points. The redundancy bound accounts for this approximation cost via the $\lceil \log n \rceil$ factor.

---

The PTW-KT Environment Measure

The PTW-KT environment measure performs Bayesian model averaging over all binary temporal partitions in $\mathcal{C}_D$, where within each segment, the percepts are modeled using a KTE instance.

Definition (Equation 7). For $t \leq 2^D$:

$\text{ptw-kte}_D(e_{1:t} \mid\mid a_{1:t}) := \sum_{P \in \mathcal{C}_D} 2^{-\Gamma_D(P)} \prod_{(c,d) \in P} \text{kte}(e_{c:d} \mid\mid a_{c:d})$

where:

• $P$ ranges over all binary temporal partitions in $\mathcal{C}_D$,
• $2^{-\Gamma_D(P)}$ is the prior weight assigned to partition $P$,
• $\Gamma_D(P)$ is a function that returns the "description length" of the tree structure associated with $P$ under a natural encoding (smaller trees receive higher prior weight),
• $\text{kte}(e_{c:d} \mid\mid a_{c:d})$ is the KTE probability of the percept subsequence in segment $(c,d)$, given the actions taken during that segment.

What it computes: this is a mixture distribution — a weighted average of the KTE predictive distributions under each possible temporal partition, with weights given by the prior over partitions. For each partition, the likelihood term $\prod_{(c,d) \in P} \text{kte}(e_{c:d} \mid\mid a_{c:d})$ assumes the environment is piecewise-stationary: within each segment $(c,d)$, the arm parameters are constant (though unknown), and different segments have independent parameters. The product over segments reflects this independence assumption.

The prior $2^{-\Gamma_D(P)}$. This is the same tree-weighting prior introduced in the Context Tree Weighting method (Willems et al., 1995). The specific encoding works as follows: each segment $(c,d)$ in a partition tree is either a leaf (no further splits) or an internal node (split into two children). The prior encodes the tree structure by writing one bit per internal node: 0 for "stop splitting here" (this node is a leaf segment) and 1 for "split into two children." The total description length $\Gamma_D(P)$ is the number of bits written to describe the tree. The prior probability $2^{-\Gamma_D(P)}$ assigns higher weight to trees with fewer splits — a bias toward parsimonious segmentations (fewer change-points). This is the standard Occam's-razor property of compression-based methods: simpler explanations of the data get higher prior probability.

What this means in practice: the mixture contains $|\mathcal{C}_D|$ terms — the number of binary temporal partitions. This number grows super-exponentially with $D$ (for $D=3$, there are roughly 26 partitions; for $D=10$, there are millions), so direct summation would be impossible. The recursive structure of $\mathcal{C}_D$ makes dynamic programming feasible.

Recursive computation (Lemma 5). For any execution up to time $t \leq 2^D$, the PTW-KTE marginal probability can be computed recursively:

$\text{ptw-kte}_D(e_{1:t} \mid\mid a_{1:t}) = \frac{1}{2}\text{kte}(e_{1:t} \mid\mid a_{1:t}) + \frac{1}{2}\text{ptw-kte}_{D-1}(e_{1:k} \mid\mid a_{1:k}) \cdot \text{ptw-kte}_{D-1}(e_{k+1:t} \mid\mid a_{k+1:t})$

where $k = 2^{D-1}$ is the midpoint of the full temporal range, and $\text{ptw-kte}_0(e \mid\mid a) = \text{kte}(e \mid\mid a)$ by definition.

What this recurrence does: it decomposes the mixture over $\mathcal{C}_D$ into two cases. The first term ($\frac{1}{2}\text{kte}$) corresponds to all partitions where the entire interval $[1,2^D]$ is treated as a single segment — the prior weight for this case is $1/2$ (one "stop" bit), and the likelihood is just the KTE over all data. The second term ($\frac{1}{2}\text{ptw-kte}_{D-1} \cdot \text{ptw-kte}_{D-1}$) corresponds to all partitions where the root is split at position $k$ — the prior weight is $1/2$ (one "split" bit), and the likelihood factorizes as the product of independent PTW-KTE mixtures over the left and right halves, each of depth $D-1$.

Why this form is essential: this recurrence enables an $O(D)$ time and $O(D)$ space algorithm for computing the marginal probability and maintaining the sufficient statistics. At each time step $t$, the algorithm maintains an array of $D$ values: $\text{ptw-kte}_i$ values for depth $i = 0, 1, \ldots, D-1$, each corresponding to a specific nested segment containing position $t$. When a new observation arrives, only these $D$ values need updating, and each update uses the previous values at the next-lower depth. This is the same dynamic programming structure as the original Partition Tree Weighting for passive prediction (Veness et al., 2013), but here each leaf node is a KTE (multi-arm model) rather than a simple KT estimator (binary model).

Redundancy guarantee (Theorem 4). For any abruptly changing NSSBP with true partition $P$, the redundancy is bounded by:

$-\log_2\frac{\mu(e_{1:t} \mid\mid a_{1:t})}{\text{ptw-kte}_D(e_{1:t} \mid\mid a_{1:t})} \leq |P|(\lceil \log_2 t \rceil + 1)\left[\frac{|\mathcal{A}|}{2}\log_2\left(\frac{t}{|\mathcal{A}||P|(\lceil \log_2 t \rceil + 1)}\right) + |\mathcal{A}| + 2\right]$

for all $t \leq 2^D$, all percept sequences $e_{1:t}$, and all action sequences $a_{1:t}$.

What this bound says: the redundancy scales linearly with the true number of segments $|P|$, logarithmically with time $t$ (through $\log_2 t$), and linearly with the number of arms $|\mathcal{A}|$. The factor $(\lceil \log_2 t \rceil + 1)$ is the approximation cost from using binary partitions to cover arbitrary segment boundaries. The term inside the brackets is essentially $|\mathcal{A}|/2$ times the log of the average data per arm per segment, plus constant overhead.

Why the bound is action-independent: this bound holds for any sequence of actions — it does not assume the agent follows any particular policy. This makes it a property of the environment measure alone, separate from the policy. However, as the paper is careful to note (following Theorem 4), "this bound is only meaningful in a predictive sense, since although it holds with respect to any given sequence of actions, it implies nothing about whether the true environment will be identified or not." The bound guarantees that the PTW-KTE makes good probabilistic predictions of percepts given actions, but if the agent's policy never pulls certain arms, the environment measure may never receive the data needed to identify the true parameters — the bound still holds, but the predictions may be uninformative about unexplored arms. This is the self-delusion problem in action.

---

Active Segment Posterior

At any time $t$, the PTW posterior over all $|\mathcal{C}_D|$ partitions collapses to a posterior over just $D+1$ active segments — the segments of lengths $2^0, 2^1, \ldots, 2^D$ that could contain the current time point under any binary temporal partition.

Definition. The set of active segments at time $t$ is:

$\text{ActiveSegments}_D(t) := \{(c, d) \in \mathbb{N} \times \mathbb{N} : c \leq t \leq d, \exists P \in \mathcal{C}_D \text{ such that } (c, d) \in P\}$

These are exactly the $D+1$ segments encountered when walking down the binary partition tree from the root (covering $\{1, \ldots, 2^D\}$) to the leaf containing $t$. Appendix B provides an $O(D)$ algorithm to compute them: express $t-1$ in binary with $D$ bits, then follow the path from root to leaf — each node along the path (including the root and the leaf) is an active segment.

Posterior weight of an active segment. The posterior probability of partition $P$ is:

$w_t(P) := \frac{2^{-\Gamma_D(P)} \prod_{(c,d) \in P} \text{kte}(e_{c:d} \mid\mid a_{c:d})}{\text{ptw-kte}_D(e_{1:t} \mid\mid a_{1:t})}$

where the denominator is the normalizing constant from Equation 7. The posterior probability of a specific segment $(c,d)$ is the sum of the posteriors of all partitions containing it:

$w_t((c,d)) := \sum_{P' \in \{P \in \mathcal{C}_D : (c,d) \in P\}} w_t(P')$

The active segment posterior $q_t(\cdot)$ is then:

$q_t((c,d)) := \begin{cases} w_t((c,d)) & \text{if } (c,d) \in \text{ActiveSegments}_D(t); \\ 0 & \text{otherwise.} \end{cases}$

Why this sums to 1. Let $s_i := (c_i, d_i)$ be the active segment of length $2^i$, for $i \in \{0, \ldots, D\}$. For any $P \in \mathcal{C}_D$, exactly one $s_i$ belongs to $P$ (the active segments form a nested chain, and any partition that covers the timeline must include exactly one segment covering the current time point). Define $\mathcal{C}_D^i := \{P \in \mathcal{C}_D : s_i \in P\}$. These sets partition $\mathcal{C}_D$ (every partition belongs to exactly one $\mathcal{C}_D^i$), so:

$\sum_{(c,d)} q_t((c,d)) = \sum_i w_t(s_i) = \sum_i \sum_{P' \in \mathcal{C}_D^i} w_t(P') = \sum_{P' \in \mathcal{C}_D} w_t(P') = 1$

The active segment posterior is therefore a valid probability distribution over $D+1$ hypotheses — it weights how likely each segment length (from $1$ to $2^D$) is to be the correct "local" segment containing the current time step.

Efficient computation (Lemma 5, applied recursively). The active segment posterior can be computed in $O(D)$ time using the same recurrence as the marginal probability. For the longest active segment $s_D$ (covering the full range $\{1, \ldots, 2^D\}$):

$w_t(s_D) = \frac{1}{2} \frac{\text{kte}(e_{c_D:d_D} \mid\mid a_{c_D:d_D})}{\text{ptw-kte}_D(e_{c_D:d_D} \mid\mid a_{c_D:d_D})}$

This is the posterior probability that the full interval is a single segment — it's proportional to how well a single KTE explains all the data versus the PTW mixture.

For intermediate active segments $s_i$ with $0 < i < D$:

$w_t(s_i) = [1 - w_t(s_{i+1})] \times \frac{1}{2} \frac{\text{kte}(e_{c_i:d_i} \mid\mid a_{c_i:d_i})}{\text{ptw-kte}_i(e_{c_i:d_i} \mid\mid a_{c_i:d_i})}$

This computes the posterior of segment $s_i$ (length $2^i$) as: the probability that the data is NOT better explained by the longer segment $s_{i+1}$ (the $1 - w_t(s_{i+1})$ factor), times the relative likelihood of a single-segment model vs. the PTW mixture within the segment $s_i$.

The base case:

$w_t(s_0) := 1 - w_t(s_1)$

This is the posterior of the single-time-step segment (length 1) — whatever probability mass remains after allocating to all longer segments.

What the active segment posterior represents, intuitively. At any time $t$, the agent is uncertain about which time scale is currently relevant. If the environment has been stable for a long time, $w_t(s_D)$ will be high — the posterior favors a segment covering the entire history. If a change-point occurred recently, $w_t(s_i)$ for some small $i$ will be high — the posterior favors a short segment starting near the change-point. The active segment posterior automatically detects change-points in a Bayesian manner: when the data within the full range becomes inconsistent with a single stationary model, the posterior shifts toward finer segmentations. No explicit change-point detection test is needed.

---

Modified PTW Prior ($\gamma$-Weighting)

The standard PTW recurrence (Lemma 5) uses equal weights ($1/2$ each) for the "stop" and "split" decisions. The paper generalizes this to biased weights using a parameter $\gamma \in (0,1)$:

$\text{ptw-kte}_D(e_{1:t} \mid\mid a_{1:t}) = \gamma \cdot \text{kte}(e_{1:t} \mid\mid a_{1:t}) + (1-\gamma) \cdot \text{ptw-kte}_{D-1}(e_{1:k} \mid\mid a_{1:k}) \cdot \text{ptw-kte}_{D-1}(e_{k+1:t} \mid\mid a_{k+1:t})$

where $\gamma$ controls the prior bias: $\gamma > 1/2$ favors simpler partition structures (fewer segments — higher cost to split), while $\gamma < 1/2$ favors more complex partition structures (more segments — lower cost to split).

Why $\gamma$ matters: the redundancy of the PTW-KTE depends on the number of arms $|\mathcal{A}|$ (Theorem 4). Splitting a segment allows different arms' parameters to adapt independently in different subsegments, but each segment carries an overhead of roughly $|\mathcal{A}|/2 \log_2(\text{length}/|\mathcal{A}|)$ bits from the KTE redundancy bound. As $|\mathcal{A}|$ grows, the cost of maintaining a stationary model (stopping) increases faster than the cost of detecting a change-point (splitting), because learning $|\mathcal{A}|$ arm parameters within a segment requires more data.

Optimal $\gamma$ setting (from Section 5.3). The cost analysis proceeds recursively. At each decision point in the tree:

• Stopping costs $-\log_2 \gamma$ bits (the code length for the "stop" decision).
• Splitting costs $-\log_2(1-\gamma)$ bits (the code length for the "split" decision).

The environment redundancy from stopping (using a single KTE for the whole segment) is approximately $\frac{|\mathcal{A}|}{2}\log_2(2^D/|\mathcal{A}|) + |\mathcal{A}| \approx |\mathcal{A}|(D/2 + 1)$ bits. Ignoring the $D$ dependence, this is roughly $|\mathcal{A}|$ times larger than the split cost. For any partition $P$, the number of stops approximately equals the number of splits (each split creates two children that eventually become stops or further splits). To minimize worst-case redundancy independent of $P$, we solve:

$\gamma = \arg\min_\gamma \{-|\mathcal{A}|\log_2 \gamma - \log_2(1-\gamma)\} = \frac{|\mathcal{A}|}{|\mathcal{A}|+1}$

This makes the prior cost of stopping $|\mathcal{A}|$ times the prior cost of splitting, matching the ratio of their redundancy contributions. For $|\mathcal{A}| = 2$, $\gamma = 2/3$; for $|\mathcal{A}| = 10$, $\gamma = 10/11$; for large $|\mathcal{A}|$, $\gamma$ approaches 1, strongly favoring simple partitions.

Empirical effect: the paper reports that $\gamma = |\mathcal{A}|/(|\mathcal{A}|+1)$ "performed substantially better than $\gamma = 1/2$, and is used in all of our subsequent experiments in Section 6." This makes intuitive sense: with many arms, learning all arm parameters within a segment is difficult, so the system should be more conservative about detecting change-points — it requires stronger evidence (more data that is inconsistent with stationarity) before favoring a segmentation. The modified prior provides this adaptation automatically without requiring the user to specify the change-point rate.

---

Reference Policies for Known Environments

To completely specify the universal coding scheme, each environment $\rho$ (consisting of a partition $P$ and arm parameters $\Theta_{c,d}$ for each segment) must be associated with a reference policy $\pi_\rho$ — the policy the agent would follow if it knew $\rho$ to be the true environment. The paper defines two policy classes.

Maximum Expected Utility (MEU) policy $\pi^*_\rho$. For an NSSBP with known segment $(c,d)$ active at time $t \in [c,d]$:

$\pi^*_\rho(a \mid h_{<t}) := \begin{cases} 1/|\mathcal{A}^*_t| & \text{if } a \in \mathcal{A}^*_t; \\ 0 & \text{otherwise,} \end{cases} \quad \text{where } \mathcal{A}^*_t := \arg\max_{a \in \mathcal{A}} \{\theta^{c,d}_a\}$

This policy greedily plays an arm with the highest known expected reward. If there are ties, it randomizes uniformly among the tied arms. The policy does not explore — it always exploits. This is the standard optimal policy for a fully known stationary bandit.

Maximum Expected Utility with Forced Exploration (MEUFE) policy $\pi^\varepsilon_\rho$. This adds random exploration that decays with segment length:

$\pi^\varepsilon_\rho(a \mid h_{<t}) := \alpha(d-c) / |\mathcal{A}| + (1 - \alpha(d-c)) \pi^*_\rho(a \mid h_{<t})$

where $\alpha(l) := l^{-1/2}$ and $l = d-c$ is the current segment length. With probability $\alpha(l)$, a uniformly random arm is selected (forced exploration); with probability $1-\alpha(l)$, the MEU policy is followed.

What the forced exploration achieves: for a segment of length $n$, the probability any specific arm is forcibly explored at a given time step is $\alpha(n)/|\mathcal{A}| = n^{-1/2}/|\mathcal{A}|$. Over $n$ steps, the expected number of forced explorations of each arm is approximately $\sqrt{n}/|\mathcal{A}|$ — it grows with the square root of the segment length. This ensures that every arm gets pulled at least some minimum number of times within each segment, providing the data needed for the PTW-KTE posterior to distinguish environments and detect change-points.

Comparison of the two policies: $\pi^*$ works well when exploration is "automatic" — i.e., when pulling the arm that appears best will naturally reveal whether it's still best (for example, if its true parameter changes when a change-point occurs, the agent will observe a degradation in rewards and start exploring). $\pi^\varepsilon$ is necessary when the environment is "deceptive" — as in the adversarial case (Section 6, Figure 4) where the previously-optimal arm retains the same expected reward after the change-point, so exploiting it provides no signal that anything has changed. In that case, forced exploration ensures the agent eventually tries other arms and discovers the new optimum.

---

The ActivePTW Algorithm (Hierarchical Thompson Sampling)

The ActivePTW policy is the Bayesian Control Rule applied to the PTW-KT posterior. Recall from Section 3 (the universal coding of interaction sequences) that the Bayesian Control Rule minimizes the single-step expected coding cost:

$\hat{\pi}(a_t \mid h_{<t}) := \sum_{\rho \in \mathcal{M}} w^\rho_{t-1} \pi_\rho(a_t \mid h_{<t})$

where $w^\rho_{t-1}$ is the posterior weight of environment $\rho$ given the history, and $\pi_\rho$ is the reference policy for $\rho$.

Implementation via sampling (Algorithm 1). Rather than summing over all environments (which is intractable — there are exponentially many partitions), ActivePTW implements the BCR via a two-step sampling procedure that exactly produces actions from $\hat{\pi}$:

1. Sample an active segment: draw $(x,y) \sim q_t(\cdot)$ from the active segment posterior. This selects a segment length (from $1$ to $2^D$) with probability proportional to the posterior belief that the current time is governed by a segment of that length. This step collapses the exponentially many partitions into a single segment.

2. Sample arm parameters for that segment: draw $\Theta \sim w_t(\cdot \mid (x,y))$, where $w_t(\cdot \mid (x,y))$ is the posterior distribution over the arm parameters $\theta^{x,y}_a$ given that $(x,y)$ is the correct segment. Because the prior within each segment is Jeffreys prior (Beta($1/2$, $1/2$)) for each arm independently, the posterior given the observed data within $(x,y)$ is: $\theta^{x,y}_a \sim \text{Beta}\left(\#1^a_{x:y} + 1/2, \#0^a_{x:y} + 1/2\right)$ where $\#1^a_{x:y}$ and $\#0^a_{x:y}$ are the counts of successes and failures for arm $a$ within segment $(x,y)$.

3. Act according to the reference policy: construct a virtual environment $\rho$ with the sampled segment $(x,y)$ and arm parameters $\Theta$, then sample and execute $a_t \sim \pi_\rho(\cdot \mid h_{<t})$, where $\pi_\rho$ is either $\pi^*$ (MEU) or $\pi^\varepsilon$ (MEUFE).

Why this sampling procedure implements $\hat{\pi}$: this is the standard Thompson Sampling argument, extended to a hierarchical posterior. The total probability of selecting action $a_t$ under this procedure is:

$P(a_t) = \sum_{(x,y)} q_t((x,y)) \int_\Theta w_t(\Theta \mid (x,y)) \pi_{(x,y,\Theta)}(a_t \mid h_{<t}) d\Theta$

This is exactly the Bayesian Control Rule with the PTW-KT posterior, because $q_t((x,y))$ aggregates the posterior weights of all partitions containing $(x,y)$, and the integration over $\Theta$ with the Beta posteriors is the exact posterior over arm parameters given the segment. The hierarchical sampling simply reorganizes the computation: first marginalize over partitions to get the segment posterior, then sample from the Beta posteriors within that segment.

What this means in practice: ActivePTW generalizes Thompson Sampling to the non-stationary setting by adding one additional sampling step — choosing which temporal segment's data to condition on. In standard Thompson Sampling, you just sample arm parameters from Beta posteriors that use all historical data. In ActivePTW, you first sample a segment (which determines which historical data to use — only data within that segment), then sample arm parameters from Beta posteriors conditioned on that segment's data. When the posterior heavily favors a long segment covering the full history, the algorithm reduces to standard Thompson Sampling. When a change-point is detected, the posterior shifts toward shorter segments, and the algorithm effectively "restarts" by conditioning on only recent data — but in a soft, probabilistic way rather than a hard reset.

Computational complexity. The algorithm requires:

• $O(D)$ time per step to update the PTW-KT sufficient statistics (using the dynamic programming recurrence from Lemma 5/Equation 9).
• $O(D + |\mathcal{A}|)$ time per step for the sampling operations: $O(D)$ to compute the active segment posterior and sample a segment, $O(|\mathcal{A}|)$ to sample arm parameters (one Beta draw per arm) and find the arm(s) with maximum sampled parameter.

Space complexity is $O(D \cdot |\mathcal{A}|)$ to maintain the sufficient statistics — an array of size $D$ per arm, where each entry stores the $(a,b)$ counts for that arm within the corresponding nested segment. The reference implementation (linked in the paper) manipulates all probabilities in log-space for numerical stability.

"ParanoidPTW" naming: the paper's experiments refer to "ParanoidPTW" as the variant using the MEUFE reference policy ($\pi^\varepsilon$) — the name reflects that this variant is more "paranoid" about missing change-points, and therefore forces exploration to ensure it continues checking other arms.

---

Theoretical Analysis (Section 5.3)

The paper provides theoretical arguments supporting the MEUFE variant's behavior, though it does not provide a full finite-time regret bound for the general case.

Forced exploration concentration. For a segment of length $n = 2^D$ with forced exploration rate $\alpha = 1/\sqrt{n}$, the probability any specific arm $i$ is forcibly explored at a given time step is $p := \alpha/|\mathcal{A}|$. Let $V_i = \sum_{t=1}^n B_{t,i}$ be the number of times arm $i$ is forcibly explored, where $B_{t,i} \sim \text{Bernoulli}(p)$ and $\mathbb{E}[V_i] = \sqrt{n}/|\mathcal{A}|$.

By Hoeffding's inequality, for any $\varepsilon > 0$:

$P(|V_i - \mathbb{E}[V_i]| \geq \varepsilon n) \leq 2\exp\{-2\varepsilon^2 n\}$

Applying the union bound over all $|\mathcal{A}|$ arms:

$P\left(\bigcup_{i=1}^{|\mathcal{A}|} |V_i - \mathbb{E}[V_i]| \geq \varepsilon n\right) \leq 2|\mathcal{A}| \exp\{-2\varepsilon^2 n\}$

Therefore, with probability at least $1 - 2|\mathcal{A}| \exp\{-2\varepsilon^2 n\}$, every arm will have been explored at least $\lfloor \sqrt{n}/|\mathcal{A}| - \varepsilon n \rfloor$ times after $n$ draws from any sequence of MEUFE policies. This lower bound on exploration ensures that the PTW-KT posterior receives sufficient data for all arms within each segment.

KT posterior concentration (Lemma 6). For random variables $X_1, \ldots, X_n \sim \text{Bernoulli}(\theta)$ i.i.d., with $S_t := \sum_{i=1}^t X_i$ and posterior mean $\bar{\theta} := (1/2 + S_t)/(t+1)$:

$P\left(|\theta - \bar{\theta}| \geq \varepsilon \mid S_t = s\right) \leq \frac{1.25(t-1)^{3/2}}{\sqrt{(s-1/2)(t-s+1/2)}} e^{-2((t-1)\varepsilon^2)}$

provided $2 \leq s \leq t-2$.

What this bound says: after observing $t$ Bernoulli draws, the KT posterior mean concentrates around the true $\theta$ at an exponential rate in $t\varepsilon^2$. The prefactor is polynomial in $t$ but is dominated by the exponential for sufficiently large $\varepsilon$. The condition $2 \leq s \leq t-2$ excludes degenerate cases where nearly all observations are identical (which can happen when $\theta$ is very close to 0 or 1) — these are handled separately via the Beta tail bound derivation in Appendix A.

How Lemma 6 is derived (Appendix A): the proof bounds the Beta cumulative distribution function using tractable algebraic expressions. For $a, b > 0$, the maximum of $t^a(1-t)^b$ occurs at $\hat{\theta} := a/(a+b)$. The incomplete Beta function $B(x; a+1, b+1)$ is bounded above by $x \cdot x^a(1-x)^b$, and the complete Beta function $B(a+1, b+1)$ is bounded below using Stirling's approximation. The ratio gives an upper bound on the Beta CDF that involves a KL-divergence term $\text{KL}(\hat{\theta} || x)$, which by Pinsker's inequality is at least $2\varepsilon^2$ when $x = \hat{\theta} \pm \varepsilon$. The final bound (Equation 11 in Appendix A) is:

$P(|\theta - \mu| \geq \varepsilon \mid k; n, \alpha, \beta) \leq \frac{1.25(n+\alpha+\beta-2)^{3/2}}{\sqrt{(k+\alpha-1)(n-k+\beta-1)}} e^{-2(n+\alpha+\beta-2)\varepsilon^2}$

Setting $\alpha = \beta = 1/2$ (the KT prior) yields Lemma 6.

Putting it together (plausibility argument). The forced exploration ensures each arm receives approximately $\sqrt{n}/|\mathcal{A}|$ pulls per segment of length $n$, with high probability. Lemma 6 then implies that the posterior over each arm's parameter concentrates rapidly around its true value — the error decays exponentially in the number of pulls. As the segment posterior $q_t(\cdot)$ is computed from these concentrated per-arm posteriors, it will correctly identify the active segment boundary. In "many cases of interest," the ActivePTW algorithm will therefore enjoy low regret. The paper acknowledges that "making this precise is deferred to future work" — the current analysis provides the building blocks (forced exploration lower bounds, posterior concentration) but does not assemble them into a formal regret bound.

Why a full regret bound is difficult: the analysis must handle the interaction between the segment posterior and the policy. The policy determines which data is collected, which affects the segment posterior, which affects future policy choices. This circular dependence is exactly the self-delusion problem — if the policy doesn't explore enough, the segment posterior may never detect a change-point, leading to linear regret. The forced exploration mechanism breaks this circularity by guaranteeing a minimum data rate for each arm, but quantifying how quickly the segment posterior adapts requires analyzing the PTW dynamic programming in an adversarial setting, which is technically challenging.

---

Summary of Design Choices and Their Justifications

• Jeffreys prior (rather than uniform) for KT estimators: provides optimal redundancy constant ($1/2 \log_2 n$ rather than $\log_2 n$ for uniform), and is invariant under reparameterization — both properties matter for universal coding optimality.
• Binary temporal partitions (rather than arbitrary partitions): enables $O(D)$ dynamic programming through the recursive tree structure, while covering all possible partitions with only a logarithmic overhead in the number of segments. The tradeoff is that change-points can only be placed at dyadic boundaries.
• Product of per-arm KT estimators (KTE, rather than a joint model): factorizes the estimation problem across arms, reducing computational complexity to $O(|\mathcal{A}|)$ and avoiding the combinatorial explosion of modeling correlations between arms. The assumption is that arms' parameters are independent within each segment — standard in bandit problems.
• PTW mixture over partitions (rather than a single partition or fixed window): performs Bayesian model averaging rather than model selection, which is more robust — the posterior shifts gradually toward shorter segments as evidence accumulates, rather than making hard change-point decisions that could be wrong. This soft restarting is a key advantage over stochastic restart methods like MASTER.
• Active segment posterior (rather than full partition posterior): exploits the property that at any single time step, only $D+1$ segments matter — information from other segments is irrelevant for the current action choice. This collapses the exponential complexity of the full posterior to linear in $D$.
• Hierarchical Thompson Sampling (rather than posterior-weighted averaging): implements the Bayesian Control Rule exactly while avoiding the need to enumerate all environments. The two-step sampling procedure is computationally equivalent to standard Thompson Sampling with one additional sampling step, making it simple to implement.
• $\gamma = |\mathcal{A}|/(|\mathcal{A}|+1)$ prior weighting (rather than $\gamma = 1/2$): adapts the prior over partition complexity to the number of arms. With more arms, the cost of maintaining a stationary model increases, so the prior should favor simpler structures. The optimal $\gamma$ balances the redundancy costs of stopping vs. splitting.
• Forced exploration with $\alpha(l) = l^{-1/2}$: ensures that each arm receives at least $\Omega(\sqrt{l})$ pulls within a segment of length $l$, with high probability. The square-root rate balances exploration (which grows with segment length) against exploitation (which should dominate for long segments). A constant exploration rate would cause linear regret; an exponentially decaying rate might not explore enough for the posterior to detect change-points.
• Two-fold cross-validation across difficulty bins for strategy selection (Section 3.2): prevents overfitting the compute-optimal policy to the test data by selecting the best configuration on one fold and evaluating on the other, ensuring reported results reflect generalization rather than data reuse.

4. Key Insights and Innovations

Innovation 1: The Self-Delusion Problem as a First-Order Design Constraint — Not an Afterthought

The paper's most distinctive conceptual move is elevating the self-delusion problem from a footnote in prior work to the central architectural constraint that determines what kind of temporal models can be safely combined with control policies. This fundamentally distinguishes the contribution from a straightforward adaptation of Partition Tree Weighting to bandits.

What the field did before. In passive universal source coding, the data stream is externally generated — you observe bits, you build a mixture model over possible source structures, you compute predictive probabilities. There is no action choice, so there is no circularity between what the model believes and what data it receives. Veness et al. (2013) demonstrated that PTW works beautifully for non-stationary binary sources in this passive setting. A naive extension to bandits would simply replace the single binary source with $|\mathcal{A}|$ binary sources (one per arm) and apply PTW directly — after all, the KTE already handles the multi-arm structure within a segment via the product of per-arm KT estimators.

What this paper identifies as distinct. Section 1 and Section 3 explain why the naive extension fails: the agent's own actions determine which arms generate data, creating a feedback loop between the environment model's posterior and the policy. If the policy exploits a particular arm and that arm continues to yield good rewards, the PTW posterior may never receive evidence that the environment has changed — the agent is "deluded" into believing the world is stationary because it never collected the disconfirming data. The paper's notation formalizes this with the $||$ operator: actions are interventions, not observations. The environment measure $\mu(e_{1:t} \mid\mid a_{1:t})$ conditions on actions as given, but the policy $\pi(a_{1:t} \mid\mid e_{1:t})$ treats percepts as given. Mixing these causal directions — as a naive joint compression of the action-percept stream would do — creates exactly the circularity that Ortega et al. (2021) diagnosed.

Why this is a fundamental insight, not an incremental fix. The self-delusion problem is not a bug that can be patched with better modeling; it is a structural incompatibility between universal source coding (which assumes data is passively received) and interactive decision-making (where data is actively chosen). The paper's solution — the Bayesian Control Rule combined with the PTW-KT posterior — is not just "PTW applied to bandits." It requires carefully decomposing the agent-environment measure into environment and policy components, then constructing the policy from the posterior over environments in a way that respects the causal direction. This decomposition is what makes the work a genuine generalization of universal source coding to control, rather than an application of existing techniques to a new domain.

The paper's policy-class distinction (MEU vs. MEUFE) operationalizes this insight: MEU policies are sufficient when the environment provides natural feedback about change-points (exploiting the old-best arm reveals its degradation), but MEUFE policies are necessary when the environment can be "deceptive" — maintaining the same reward for the previously-optimal arm while another arm becomes superior. Figure 4 provides concrete evidence: ActivePTW with MEU fails catastrophically on the adversarial construction (a single change-point where the old-best arm retains its value), while MEUFE succeeds specifically because it forces data collection that breaks the delusion. This is not a performance tuning knob — it is a diagnosis of when the compression-to-control generalization works and when it structurally cannot.

---

Innovation 2: Bayesian Inference Over All Restart Schedules as a Unifying Framework

The paper reframes the non-stationary bandit problem as posterior inference over temporal segment structure, replacing the dominant paradigm of adaptively tuning window sizes or restart probabilities with a principled Bayesian alternative. This shift matters independently of the specific PTW implementation.

Contrast with the state of the art. The two leading approaches to non-stationary bandits take fundamentally non-Bayesian perspectives:

• Windowing methods (Sliding Window UCB, Discounted Thompson Sampling) make a hard decision about which data to include, discarding older observations entirely. This is a form of model selection with a fixed capacity constraint — the window size determines how many past observations count, and the algorithm commits to this choice uniformly across all arms and all time steps. The paper highlights (Section 1) that these methods "perform well when a good problem-dependent choice of hyperparameters is known in advance" — a condition that rarely holds in practice.

• Stochastic restarting (MASTER) makes a sequential sampling decision: at each step, with some probability derived from regret bounds, discard all history and begin fresh. This is an online restarting schedule but it does not maintain a posterior over which schedule is correct. MASTER runs one configuration at a time; it does not integrate over the uncertainty about where change-points occurred.

What ActivePTW does differently. The PTW-KT environment measure (Equation 7) maintains a posterior distribution over all binary temporal partitions simultaneously. At time $t$, the agent's belief about which time points are change-points is represented as a probability distribution over segment structures, not as a single committed segmentation. The active segment posterior $q_t(\cdot)$ then collapses this distribution to the $D+1$ hypotheses relevant for the current action — but critically, it does so fresh at each time step, and it aggregates evidence across all possible segmentations weighted by their posterior probability.

This is Bayesian model averaging over restart schedules. Instead of choosing one restart point or one window size, ActivePTW effectively runs every possible schedule in parallel, with each schedule's influence on the current action proportional to how well it explains the observed data. The computational efficiency comes from the binary tree structure, which enables the dynamic programming recurrence (Lemma 5) to compute the mixture without enumerating the exponentially many partitions.

Why this is a fundamental shift, not a better window-size heuristic. The Bayesian framework provides two properties that windowing and restarting cannot:

1. Soft, evidence-graded adaptation. When a change-point occurs, the PTW posterior does not abruptly discard all pre-change data. Instead, the posterior mass shifts gradually from long segments (covering the full history) toward shorter segments (starting near the change-point). The speed of this shift depends on how strongly the new data contradicts the stationary model — it is evidence-graded, not triggered by an arbitrary threshold. Figure 2's regret curves show this in action: ActivePTW adapts to change-points without the characteristic "regret spikes" that occur when a windowing method has the wrong window size.

2. Automatic collapse to stationary behavior. When the environment is actually stationary, the posterior concentrates on partitions with a single segment covering the full history, and ActivePTW reduces to classic Thompson Sampling — a property demonstrated in Figure 3, where "the performance of ActivePTW($\pi^*$) is nearly identical to that of Thompson Sampling." Windowing methods cannot replicate this: a fixed window size permanently discards older data even when it's still relevant, incurring a permanent efficiency cost. Restarting methods similarly pay a cost for unnecessary restarts.

This framework also provides a unified explanation for why different algorithms work well in different regimes. When the change-point rate is low, the posterior favors long segments, and ActivePTW behaves similarly to stationary Thompson Sampling (which is optimal in that regime). When the change-point rate is high, the posterior favors short segments, and ActivePTW behaves similarly to a rapidly-restarting algorithm. The transition is automatic and continuous — there is no regime-switching logic, just Bayesian inference.

---

Innovation 3: Diagnosing the Boundary Between Exploitative and Forced-Exploration Policies as a Structural Property of the Environment

The paper does more than propose two policy variants (MEU and MEUFE); it identifies a structural condition on the environment that determines which policy class is necessary, and provides both theoretical and empirical evidence that this condition is the right diagnostic for the self-delusion problem in bandit control.

The diagnostic condition. The question is: when a change-point occurs, does the previously-optimal arm's expected reward change? If yes (the arm degrades), then a purely exploitative policy will naturally detect the change-point — continuing to play the old-best arm will reveal lower rewards, causing the posterior to shift. If no (the arm stays the same while another arm improves), then exploitation provides no signal of change — the agent is trapped. This is the "adversarial case" from Section 6 and Figure 4.

Why this is a conceptual contribution, not just an engineering choice. Prior work on non-stationary bandits largely treats exploration as a generic requirement — algorithms explore to gather information, and the exploration rate is typically tuned as a hyperparameter (window size, restart probability, UCB exploration bonus). The paper's decomposition reveals that the necessity of explicit exploration depends on the environment's change-point structure in a precise way. This is analogous to the distinction in causal inference between observable and unobservable confounders — if the environment provides natural experiments (the old-best arm changes when the environment changes), the agent can learn passively; if not, the agent must actively intervene (force exploration).

The theoretical analysis in Section 5.3 operationalizes this: the forced exploration rate $\alpha(l) = l^{-1/2}$ guarantees $\Omega(\sqrt{l})$ pulls per arm per segment of length $l$, with high probability (via Hoeffding's inequality). This lower bound, combined with the KT posterior concentration result (Lemma 6), shows that the MEUFE policy ensures the posterior will eventually concentrate on the correct segment structure regardless of how deceptive the environment is. The MEU policy provides no such guarantee — it can fail permanently on deceptive environments, as Figure 4 demonstrates.

Why this matters beyond this paper. The distinction between environments where exploitation provides natural change-point detection and environments where it does not is a general property of interactive learning systems, not specific to bandits. Any agent that learns from its own actions faces the same structural question: does the existing policy generate the data needed to detect environmental shifts? The paper's forced-exploration solution — adding random exploration at a rate that decays with the square root of the segment length — is a specific instantiation of a broader principle: the agent's exploration rate must be calibrated to the worst-case information acquisition rate, not just the expected value of exploration. This principle connects to the literature on information-directed sampling and Bayesian experimental design, but the paper's diagnostic — asking whether the environment is "deceptive" with respect to the current policy — provides a sharper, more actionable condition than generic information-theoretic bounds.

The negative result with ReST$^{EM}$ (Appendix K, Figure 16) reinforces this: attempting to further optimize the revision model using on-policy data collection actually degrades performance, because on-policy data amplifies the very selection bias that forced exploration is designed to break. This is a cautionary result for the broader self-improving agents literature: if you train on data generated by your current policy, you may be reinforcing the delusion rather than escaping it.

---

Innovation 4: The Modified PTW Prior as an Instance of Meta-Learning the Change-Point Prior from Arm Cardinality

The paper's choice of $\gamma = |\mathcal{A}|/(|\mathcal{A}|+1)$ for the PTW prior weight is not an arbitrary tuning — it represents a principled meta-parameterization that makes the prior over temporal partition complexity adapt automatically to the difficulty of learning within each segment.

What the standard approach would be. In classic Context Tree Weighting and Partition Tree Weighting, the prior over tree structures is typically symmetric: $\gamma = 1/2$ gives equal weight to stopping and splitting at each node. This prior is "universal" in the sense that it works for any Markov order (in CTW) or any segment structure (in PTW) without needing to know the true complexity in advance. The standard argument is that any fixed $\gamma$ works, with the worst-case redundancy differing only by a constant factor — so there's no need to tune it.

Why the standard argument fails here. The redundancy analysis in Section 5.3 reveals a dependence that passive PTW does not have: the cost of maintaining a stationary model (stopping) scales with $|\mathcal{A}|$ (because learning $|\mathcal{A}|$ arm parameters requires $|\mathcal{A}|$ times more data than learning one binary source), while the cost of detecting a change-point (splitting) is independent of $|\mathcal{A}|$ (it's always a single binary decision). In the passive case, both the source and the change-point are binary, so the costs are symmetric. In the bandit case, the asymmetry means that the optimal $\gamma$ should depend on $|\mathcal{A}|$.

The derivation sets $\gamma = \arg\min_\gamma \{-|\mathcal{A}|\log_2 \gamma - \log_2(1-\gamma)\}$, which balances the worst-case redundancy contributions. The result, $\gamma = |\mathcal{A}|/(|\mathcal{A}|+1)$, has the property that the prior cost of stopping is $|\mathcal{A}|$ times the prior cost of splitting — matching the ratio of their data-dependent redundancy contributions.

Why this is a conceptual contribution, not curve-fitting. This parameterization means the algorithm automatically becomes more conservative about detecting change-points as the number of arms increases. With $|\mathcal{A}| = 2$, $\gamma = 2/3$ — a moderate bias toward simplicity. With $|\mathcal{A}| = 50$, $\gamma = 50/51$ — a very strong bias toward simplicity, meaning the algorithm requires substantially more evidence before favoring a segmentation. This makes intuitive sense: with 50 arms, identifying the best arm within a segment requires much more data, so the algorithm should be more reluctant to split the timeline into short segments where there isn't enough data to learn effectively.

The empirical results confirm this matters: the paper states that $\gamma = |\mathcal{A}|/(|\mathcal{A}|+1)$ "performed substantially better than $\gamma = 1/2$, and is used in all of our subsequent experiments." For a 50-arm problem, the difference between $\gamma = 50/51$ and $\gamma = 1/2$ is the difference between strongly favoring a single-segment model versus being indifferent — and that difference translates directly into regret when the environment is actually stationary or slowly-changing.

The meta-learning interpretation. From a higher level, the $\gamma$ parameterization can be seen as a form of meta-learning: the algorithm uses knowledge about the problem structure (the number of arms, which is known) to set a prior that is more informative than a generic universal prior would be. This is distinct from tuning $\gamma$ on a validation set — the formula $\gamma = |\mathcal{A}|/(|\mathcal{A}|+1)$ is derived from the worst-case redundancy analysis, not from cross-validation. It represents a principled way to inject domain knowledge (the action space size) into a universal algorithm without compromising its universality guarantees.

This connects to a broader theme in universal source coding: the transition from "fully universal" priors (which work for any source but may adapt slowly) to "structured universal" priors (which exploit known properties of the source class to adapt faster while still providing guarantees for a well-defined class). The PTW-KT with the modified prior is universal for the class of abruptly-changing NSSBPs, but its $\gamma$ adaptation makes it more efficient within that class than a symmetric prior would be — a form of minimax optimality within the defined problem class.

---

Innovation 5: Active Segments as a Computational-Statistical Bridge Between Exponential Partition Spaces and Tractable Action Selection

The concept of active segments — the $D+1$ segments of dyadic lengths that contain the current time point — is not just an algorithmic trick for efficiency. It represents a deeper insight about what information from the partition posterior is statistically sufficient for action selection at a single time step, and why the exponentially many partitions can be collapsed without loss of decision-relevant uncertainty.

Why the exponential-to-linear reduction is non-trivial. The PTW posterior $w_t(P)$ assigns probability to each of the $|\mathcal{C}_D|$ binary temporal partitions — a set whose size grows super-exponentially with $D$. A naive approach to implementing the Bayesian Control Rule would require summing over all these partitions to compute $\hat{\pi}(a_t \mid h_{<t})$. The paper's insight is that for the purpose of selecting an action at time $t$, only the $D+1$ segments that could contain $t$ under any partition matter. All other segments — those entirely in the past or entirely in the future — are irrelevant for the current decision.

Why this works. The argument in Section 5.2 (showing $\sum_i q_t(s_i) = 1$) exploits a structural property of binary temporal partitions: for any $P \in \mathcal{C}_D$, exactly one segment in $P$ covers the current time point $t$, and that segment must be one of the $D+1$ active segments. The sets $\mathcal{C}_D^i := \{P \in \mathcal{C}_D : s_i \in P\}$ therefore partition the full partition space. The active segment posterior $q_t(s_i)$ is the sum of the posterior weights of all partitions in $\mathcal{C}_D^i$ — it exactly captures the total posterior belief that $s_i$ is the correct current segment.

What this means statistically. The collapse from $|\mathcal{C}_D|$ partitions to $D+1$ segments is lossless for the purpose of current action selection under the MEU reference policy class. This is because MEU policies condition only on the current segment's arm parameters — they don't use information about past or future segments. If the reference policy class were different (e.g., a policy that plans ahead based on expected future change-points), the active segment posterior would no longer be sufficient, and you would need to retain more of the full partition posterior.

This is a concrete instance of a broader principle: the computational-statistical interface in Bayesian agents. The agent's policy class determines what information from the posterior is relevant for decision-making, and this relevance determines what can be safely compressed. The active segment concept makes this interface explicit — it shows exactly what structure must be preserved ($D+1$ segment hypotheses) and what can be discarded (the $|\mathcal{C}_D| - (D+1)$ degrees of freedom corresponding to how past and future segments are arranged). Without this insight, one might either attempt the intractable full summation or resort to heuristic approximations (like sampling a single partition) that lose valuable posterior uncertainty.

Empirical evidence of sufficiency. The strong performance of ActivePTW across all experiments (Tables 1-4, Figures 1-4) validates that the active segment posterior captures the decision-relevant uncertainty. If important information were being lost in the collapse, the algorithm would underperform relative to methods that use the full posterior — but it does not. Moreover, the fact that the algorithm reduces exactly to Thompson Sampling in the stationary limit (Figure 3) confirms that the active segment representation is a proper generalization, not an approximation.

5. Experimental Analysis

Evaluation Methodology

• Dataset. All experiments use synthetic non-stationary stochastic Bernoulli bandit (NSSBP) environments, not a fixed benchmark dataset. The environment parameters (number of arms, change-point rates, arm reward probabilities) are generated procedurally according to three distinct regimes (described below). There is no pre-existing train/test split; each experimental condition is evaluated by averaging over multiple independently generated episodes (typically 400–1600 runs) with 95% confidence intervals reported.

• Base model(s). There is no pretrained neural model — ActivePTW is a tabular Bayesian algorithm that maintains explicit count statistics (successes and failures per arm per segment) using the PTW-KT environment measure. The algorithm's "model" is the array of sufficient statistics of size $O(D \cdot |\mathcal{A}|)$ maintained via dynamic programming (Lemma 5/Equation 9). The maximum depth $D$ is set such that $T \leq 2^D$ for the given time horizon $T$; in the experiments, $T = 10^6$ for the geometric change-point regimes and $T = 5000$ or $T = 10000$ for the stationary and adversarial regimes.

• Metrics. The primary metric is cumulative regret — the total expected reward lost relative to an oracle that always plays the optimal arm at each time step. Formally, for an episode of length $T$, $\text{Regret}_T = \sum_{t=1}^T (\mu^*_t - \mu_{a_t,t})$, where $\mu^*_t$ is the expected reward of the optimal arm at time $t$ and $\mu_{a_t,t}$ is the expected reward of the arm actually pulled. All results report average regret across multiple episodes, with 95% confidence intervals (assuming asymptotic normality) either in tabular form (Tables 1–4) or as shaded regions on line plots (Figures 1–4).

• Baselines. The paper compares against six algorithms spanning stationary and non-stationary bandit methods:

  • Thompson Sampling (Chapelle and Li, 2011): standard Beta-Bernoulli posterior sampling without any change-point handling.
  • UCB1 (Auer et al., 2002): the canonical upper-confidence-bound algorithm for stationary bandits.
  • KL-UCB (Garivier and Cappé, 2011): a UCB variant that incorporates knowledge of the Bernoulli reward distribution; included in the stationary-baseline comparison (Figure 3).
  • Sliding Window UCB (SWUCB) (Garivier and Moulines, 2008): UCB1 applied to a fixed-length window of the $W$ most recent observations. The paper explicitly notes that the window size $W$ was set assuming knowledge of the expected segment length ($W = 1/p$ where $p$ is the geometric change-point rate), making these results "somewhat best-case."
  • MASTER (Wei and Luo, 2021): a meta-algorithm that stochastically restarts a base stationary algorithm (UCB1 in these experiments) based on known regret properties.
  • Uniform and Constant: trivial baselines that always pull a uniformly random arm or always pull a fixed arm, respectively. Included in Tables 1–4 for calibration.

• Generation budget / compute accounting. There is no neural generation budget — all algorithms are tabular and computationally lightweight. The comparison is standardized by identical interaction budgets: all algorithms interact with the same environment for the same number of time steps $T$ under the same random seeds (the paper uses Common Random Numbers for variance reduction where noted). Computational complexity of ActivePTW per step is $O(D + |\mathcal{A}|)$ for the sampling operations plus $O(D)$ for the PTW-KTE update; practical runtimes are not reported but the algorithm is described as maintaining arrays of $O(D \cdot |\mathcal{A}|)$ counters.

• Cross-validation / statistical protocol. There is no train/validation/test split because the environments are procedurally generated. Statistical reliability is assessed through repeated independent episodes (400, 1600, or more runs per condition) with 95% confidence intervals computed assuming asymptotic normality. For the Common Random Numbers procedure (Figure 3, stationary comparison; Figure 4, adversarial case), the same collection of environment-initializing random seeds is used across all algorithms to reduce variance in the relative comparisons.

---

Main Quantitative Results

The experiments are organized around three qualitatively distinct change-point regimes, each testing a different aspect of the algorithm's behavior. We follow the paper's structure: geometrically distributed change-points (regime a), stationary environments (regime b), and an adversarial construction (regime c).

Geometric Change-Point Regimes (Regime a): ActivePTW Dominates at Moderate Change Rates

Experimental setup. Regime (a) simulates an NSSBP where segment lengths are drawn independently from a geometric distribution with success probability $p \in \{0.01, 0.001, 0.0001, 0.00001\}$. Smaller $p$ means fewer change-points (longer expected segment length $\mathbb{E}[L] = 1/p$). At each change-point (including $t=1$), the Bernoulli parameters for all arms are resampled independently from $\text{Uniform}[0,1]$. This is the "uniform initialization" variant; the "adversarial initialization" variant (regime c) modifies the resampling to leave the previously-optimal arm's parameter unchanged. Four action-space sizes are tested: $|\mathcal{A}| \in \{2, 5, 10, 50\}$. Each condition is evaluated over $T = 10^6$ time steps.

Headline results. The summarizing figure is Figure 1 (line plots showing final regret vs. change-point rate for each $|\mathcal{A}|$) with exact numbers in Tables 1–4. The central pattern: ActivePTW variants achieve the lowest regret across nearly all conditions, with the margin being largest at moderate change rates ($p = 0.001$ to $0.0001$) and moderate arm counts ($|\mathcal{A}| = 2$ to $10$).

Detailed comparisons by arm count and change rate:

For $|\mathcal{A}| = 2$ arms (Table 1): ActivePTW (MEU) achieves 4×–10× lower regret than the best non-PTW baseline across all change rates. At $p = 0.01$ (fast changes, expected segment length 100): ActivePTW records 4872.67 ± 43 cumulative regret versus Sliding Window UCB at 8696.69 ± 112 (1.8× better) and MASTER at 10788.93 ± 288 (2.2× better). At $p = 0.00001$ (very slow changes, expected segment length 100,000): ActivePTW achieves 189.19 ± 111 — essentially near-zero regret — compared to MASTER at 1137.33 ± 194 (6× worse) and SWUCB at 2906.37 ± 141 (15× worse). The ParanoidPTW variant (forced exploration) trails ActivePTW slightly but still dominates all baselines (e.g., 5288.69 ± 45 vs. 8696.69 ± 112 for SWUCB at $p=0.01$).

For $|\mathcal{A}| = 5$ arms (Table 2): The qualitative pattern holds with quantitative decay. At $p = 0.01$: ActivePTW at 11688.19 ± 63 versus SWUCB at 13512.51 ± 76 (1.2× better) and MASTER at 14132.31 ± 226 (1.2× better). At $p = 0.0001$: ActivePTW at 1038.22 ± 100 versus SWUCB at 9738.46 ± 134 (9.4× worse for SWUCB, because its fixed window size of 10,000 is poorly matched to the 100,000 expected segment length, causing it to discard useful data) and MASTER at 6630.28 ± 480 (6.4× worse). Note that Sliding Window UCB's window was set to $W = 1/p$ (the expected segment length), so at $p = 0.0001$, $W = 10,000$ — but this is only a fraction of $T = 10^6$, meaning SWUCB is perpetually discarding older but still-relevant data from earlier parts of the same long segment. The fixed window size is a structural disadvantage at low change rates that ActivePTW avoids entirely.

For $|\mathcal{A}| = 10$ arms (Table 3): ActivePTW's advantage over SWUCB persists but narrows at higher change rates. At $p = 0.01$: ActivePTW at 16559.30 ± 74 versus SWUCB at 18909.91 ± 51 (SWUCB is only 1.14× worse — the window size of 100 approximately matches the fast change rate, and the problem is hard enough that all algorithms struggle). MASTER at 14855.74 ± 139 actually edges out ActivePTW slightly at this specific point (1.11× better), though the confidence intervals overlap substantially. At $p = 0.0001$: ActivePTW at 1384.77 ± 85 dramatically outperforms MASTER at 7512.62 ± 374 (5.4× better) and SWUCB at 17412.77 ± 219 (12.6× better).

For $|\mathcal{A}| = 50$ arms (Table 4): The results reveal the limits of ActivePTW's approach. At $p = 0.01$ (fast changes, 50 arms): UCB1 achieves the lowest regret at 15557.03 ± 81, substantially outperforming ActivePTW at 28429.17 ± 82 (1.8× worse for ActivePTW) and MASTER at 19597.48 ± 210. The paper explicitly notes this: "with the except when the number of actions is large and the change-point rate high, then UCB outperforms all alternatives." This is expected behavior: with 50 arms and segments of expected length only 100 time steps, there simply isn't enough data per segment to identify the best arm, so aggressive exploration (which UCB provides uniformly) dominates. ActivePTW's Bayesian approach tries to infer segment structure, but the segments are too short relative to the arm count for any structure to be reliably detected. At lower change rates ($p = 0.0001$ and $p = 0.00001$), ActivePTW regains leadership (2849.74 ± 143 and 624.28 ± 114 respectively), dramatically outperforming SWUCB (35595.94 and 36058.06 — 12.5× and 58× worse) and MASTER (12507.24 and 11449.53 — 4.4× and 18× worse).

Key pattern across all arm counts: The ParanoidPTW variant (with forced exploration) consistently trails the MEU variant in these geometric regimes. For example, at $|\mathcal{A}| = 5, p = 0.001$: ActivePTW at 3710.23 ± 71 versus ParanoidPTW at 4333.63 ± 69. This gap occurs because in regime (a), when a change-point occurs, all arms' parameters are resampled, including the previously-optimal arm. The MEU policy naturally detects this — continuing to exploit the previously-best arm yields lower rewards after the change, providing a signal that triggers exploration implicitly. The forced exploration in ParanoidPTW is an unnecessary cost in this regime — it pulls suboptimal arms when the MEU policy would have learned naturally. This validates the paper's diagnostic: forced exploration is only necessary when the environment is "deceptive" (the previously-optimal arm retains its value across a change-point).

Figure 2 (illustrative single-segmentation trace). To provide intuition, the paper shows a single fixed geometrically spaced segmentation (with success probability 0.0002, $T = 10^6$, $|\mathcal{A}| = 5$, averaged over 400 runs). The regret curves demonstrate that both ActivePTW variants maintain near-linear regret (indicating rapid adaptation to change-points), while MASTER and SWUCB accumulate regret more rapidly after each change. The MEU variant slightly outperforms ParanoidPTW in this trace, consistent with the aggregate results.

Stationary Environments (Regime b): ActivePTW Collapses to Thompson Sampling

Experimental setup. Regime (b) is a stationary Bernoulli bandit: arm parameters are sampled from $\text{Uniform}[0,1]$ at $t = 1$ and held fixed for the entire episode ($T = 5000$, $|\mathcal{A}| = 5$, 400 episodes). This tests whether ActivePTW pays an unnecessary cost for being change-point-aware when the environment is actually stationary.

Headline results from Figure 3. The paper reports: "the performance of ActivePTW($\pi^*$) is nearly identical to that of Thompson Sampling. This is the expected behaviour, as the environment redundancy of ptw-kte$_D(e_{1:t} \mid\mid a_{1:t})$ with respect to kte$_d(e_{1:t} \mid\mid a_{1:t})$ is upper bounded by $-\log\gamma$ bits for any $t \leq 2^D$ using a standard dominance argument." The ActivePTW(MEU) regret curve is visually indistinguishable from Thompson Sampling in Figure 3 — both achieve low cumulative regret consistent with the known logarithmic regret bounds for Thompson Sampling in stationary Bernoulli bandits.

ActivePTW($\pi^\varepsilon$) (the ParanoidPTW variant) performs "predictably worse than ActivePTW($\pi^*$), as the forced exploration is unnecessary in this simpler setting." The forced exploration adds regret by pulling suboptimal arms at a rate $\alpha(l) = l^{-1/2}$ when no such exploration is needed. However, the paper notes that ParanoidPTW still "substantially better than MASTER" in this stationary setting.

KL-UCB outperforms UCB1 in Figure 3, which is expected because KL-UCB exploits knowledge of the Bernoulli reward distribution to compute tighter confidence bounds. This comparison serves to calibrate the stationary baselines — it confirms that the experimental setup produces the expected ordering among well-known stationary algorithms.

Key insight. The stationary experiment validates a crucial property: ActivePTW gracefully degrades to stationary performance without requiring the user to specify whether the environment is stationary or not. The PTW posterior automatically concentrates on partitions with a single segment covering the full history, effectively reducing the non-stationary model to a stationary one. This is not true of windowing methods (which would permanently ignore older data if $W < T$) or restarting methods (which would occasionally restart unnecessarily). The paper quantifies this property theoretically: the redundancy of ptw-kte$_D$ relative to a single KTE is at most $-\log_2 \gamma$ bits — a constant cost that does not grow with time. In practice, this constant is small enough that the regret curves are "nearly identical."

Adversarial Change-Point Regime (Regime c): Forced Exploration Is Necessary — and Diagnosed

Experimental setup. This regime is designed to test the paper's central theoretical claim about the self-delusion problem. An NSSBP with $|\mathcal{A}| = 10$ arms and two equally sized segments (each of length 5000, so $T = 10000$) is constructed as follows:

• Segment 1 ($t = 1$ to $5000$): $\theta^{1,5000}_1 = 0.2$ (arm 1 is best), $\theta^{1,5000}_i = 0.1$ for all $i \neq 1$.
• Segment 2 ($t = 5001$ to $10000$): $\theta^{5001,10000}_i = 0.2$ for all $i \neq 2$, and $\theta^{5001,10000}_2 = 0.8$ (arm 2 is now dramatically best).

The critical property: arm 1's expected reward is 0.2 in both segments. After the change-point at $t = 5001$, arm 2 becomes superior (0.8 vs. 0.2), but continuing to play arm 1 yields the same expected reward as before (0.2). A greedy policy that converged to arm 1 in the first segment will see no degradation in rewards after the change-point — it has no signal that anything changed. This is the precise condition for the self-delusion problem.

Headline results from Figure 4 ($N = 1600$ runs). The regret curves reveal a stark divergence:

• ActivePTW($\pi^*$) (MEU) performs poorly — its regret after the change-point grows approximately linearly, indicating it continues playing arm 1 and never discovers arm 2. The paper states it "essentially perform[s] similarly to naive Thompson Sampling, and [is] outperformed by both MASTER and ActivePTW($\pi^\varepsilon$)."
• ActivePTW($\pi^\varepsilon$) (ParanoidPTW) adapts successfully — its regret curve shows a characteristic "recovery" shape after the change-point, indicating it discovers arm 2 and subsequently exploits it.
• MASTER also adapts successfully in this setting, because its stochastic restarting mechanism eventually triggers a restart after the change-point, and the fresh UCB1 instance explores enough to find arm 2.

The paper explicitly draws the theoretical conclusion: "This is a concrete example which justifies the need for forced exploration." Without it, the MEU policy is trapped by the informational structure of the environment — the agent's own policy choice (exploiting arm 1) prevents it from ever collecting the data that would reveal arm 2's superiority.

Contrast with regime (a). The paper notes that in regime (a) (geometric change-points with uniform reinitialization), ActivePTW($\pi^*$) works well because "whenever a change-point occurred, if the previously optimal arm's latent Bernoulli parameter changed by some non-trivial constant amount, then the change-point detection problem is very similar to the passive case of sequence prediction in which the Partition Tree Weighting technique is known to work well." This comparison is the empirical confirmation of the paper's diagnostic: the structural relationship between the pre-change and post-change arm parameters determines whether exploitation alone provides sufficient information for change-point detection.

---

Ablation Studies and Robustness Checks

The paper's ablation analysis is distributed across the main experiments and appendices, examining the effects of policy choice, prior weighting, forced exploration, and environmental parameters.

Reference policy class (MEU vs. MEUFE): The choice between $\pi^*$ and $\pi^\varepsilon$ is the paper's central ablation. The geometric regime (a) results (Tables 1–4, Figure 1) show that ParanoidPTW (MEUFE) consistently trails ActivePTW (MEU) when the environment provides natural change-point signals — the performance gap ranges from ~8% to ~200% depending on arm count and change rate, always in MEU's favor. The adversarial regime (c) results (Figure 4) show the inversion: MEU fails catastrophically (approximately linear regret after the change-point) while MEUFE recovers and achieves low asymptotic regret. This confirms that the policy choice is not a hyperparameter to be tuned but a structural decision contingent on the environment's change-point semantics — a diagnostic contribution, not a methodological one.

$\gamma$ parameter (modified PTW prior): Section 5.3 describes the theoretical motivation for $\gamma = |\mathcal{A}|/(|\mathcal{A}|+1)$ and states that this choice "performed substantially better than $\gamma = 1/2$, and is used in all of our subsequent experiments in Section 6." No quantitative ablation table is provided comparing $\gamma$ values — this is a limitation. However, the theoretical derivation (balancing stop vs. split redundancy costs as a function of $|\mathcal{A}|$) is presented as the justification. The improvement is attributed to the PTW prior's adaptation to arm count: with more arms, simpler partition structures should be favored because learning arm parameters within each segment is harder, requiring more data per segment before a change-point hypothesis is favored.

Forced exploration rate $\alpha(l) = l^{-1/2}$: The paper reports the exploration rate formula but does not ablate alternative rates (e.g., $\alpha(l) = l^{-1}$, $\alpha(l) = \text{constant}$). The theoretical justification in Section 5.3 (guaranteeing $\Omega(\sqrt{l}/|\mathcal{A}|)$ explorations per arm per segment of length $l$) provides the motivation, but empirical sensitivity to this rate is not tested. The concentration bound (Hoeffding + union bound) shows that the chosen rate ensures sufficient exploration with high probability; whether a different rate would improve performance in specific regimes is left unexplored.

Depth parameter $D$: The depth $D$ is set implicitly by the time horizon $T$ (such that $T \leq 2^D$). For $T = 10^6$, $D \geq 20$ (since $2^{20} \approx 10^6$), meaning the PTW-KTE maintains $D+1 = 21$ active segments. For $T = 5000$, $D \approx 13$. No ablation over $D$ is reported — $D$ is treated as a fixed capacity parameter rather than a tunable hyperparameter. This is consistent with the universal source coding perspective (the algorithm should work for any $D$ large enough to cover the horizon), but the computational cost scales with $D$, so the practical choice matters.

Common Random Numbers for variance reduction: In Figure 3 (stationary) and Figure 4 (adversarial), the same random seeds are used across algorithms to reduce variance in the relative comparisons. This is a standard technique but is not formally ablated against independent seeds. The confidence intervals in these figures account for the reduced variance appropriately.

Negative result: the failure regime at high arm counts and fast change rates. Table 4 ($|\mathcal{A}| = 50$, $p = 0.01$) shows ActivePTW at 28429.17 ± 82 versus UCB at 15557.03 ± 81 — a substantial underperformance (1.8× worse). The paper acknowledges this but does not deeply analyze why UCB beats the Bayesian approach here. A plausible mechanism: with segments of expected length 100 and 50 arms to learn, there are on average only 2 observations per arm per segment. The PTW posterior over segments cannot reliably distinguish between a stationary model and a segmented model with such little data per segment, so it may favor longer segments inappropriately. UCB's uniform exploration bonus does not attempt to infer segment structure and simply ensures all arms are pulled regularly — which is the right strategy when there's no hope of identifying the best arm within a segment anyway. This failure mode highlights a boundary condition for ActivePTW: when the segment length is comparable to or smaller than the number of arms, the Bayesian inference over segment structure provides no advantage over uniform exploration.

Regime (c) adversarial initialization (geometric spacing): The paper mentions but does not extensively report results for regime (c) — geometrically distributed change-points where the previously-optimal arm's parameter stays the same. This is described as "more challenging from an exploration point of view" but detailed regret tables are not provided. The adversarial construction in Figure 4 is a simplified version (single change-point, fixed lengths) designed to isolate the mechanism. How ActivePTW($\pi^\varepsilon$) performs on geometric adversarial regimes — where change-points occur randomly and the previously-optimal arm may or may not change — is not quantified, representing a gap between the diagnostic experiment and the more realistic setting.

---

Critical Assessment

The experimental section demonstrates several clear strengths: comprehensive comparison against relevant baselines (six algorithms covering stationary, windowing, restarting, and trivial policies), systematic variation of the key environmental parameters (arm count and change rate over multiple orders of magnitude), and targeted diagnostic experiments (Figures 3 and 4) that isolate specific theoretical claims. The confidence intervals on all main results and the use of Common Random Numbers for variance reduction in key comparisons are methodologically sound.

However, several genuine weaknesses and open questions remain:

The Sliding Window UCB baseline is evaluated in a best-case configuration. The paper explicitly states that SWUCB's window size $W$ was set to $1/p$ — i.e., assuming advance knowledge of the expected segment length. In practice, this knowledge is unavailable, and SWUCB's performance with a mismatched window would be substantially worse. The comparison is therefore fair to ActivePTW (which does not require this knowledge) but unfair to SWUCB as a practical benchmark — the reported numbers represent an upper bound on SWUCB's real-world performance, not a realistic head-to-head. A fairer comparison would include SWUCB with window sizes set by a heuristic or cross-validation, or at minimum would report sensitivity to $W$.

No comparison against Discounted Thompson Sampling or Sliding Window TS. The paper compares against Sliding Window UCB but not against sliding-window variants of Thompson Sampling (Trovò et al., 2020, cited in the introduction). Given that ActivePTW is a generalization of Thompson Sampling, comparing against windowed TS variants would be a more direct ablation — it would separate the benefit of the PTW hierarchical prior from the benefit of Thompson Sampling's posterior sampling. The absence of this baseline makes it difficult to assess whether ActivePTW's gains come from the PTW structure specifically or from Bayesian posterior sampling more generally.

The $\gamma$ ablation is claimed but not quantitatively reported. The statement that $\gamma = |\mathcal{A}|/(|\mathcal{A}|+1)$ "performed substantially better than $\gamma = 1/2$" is important for the paper's theoretical narrative (the modified prior as a principled adaptation to arm count), but without a table or figure quantifying the difference, the reader cannot assess the magnitude of the improvement or whether it varies across regimes. This is a notable omission for a claim that the authors explicitly make.

The failure regime is identified but not analyzed. Table 4 shows ActivePTW losing to UCB at $|\mathcal{A}| = 50, p = 0.01$, and the paper acknowledges this in one sentence ("with the except when the number of actions is large and the change-point rate high, then UCB outperforms all alternatives"). But there is no analysis of why — no investigation of the PTW posterior's behavior in this regime, no diagnostic plots of segment posterior concentration, no comparison of exploration patterns between ActivePTW and UCB. Understanding this failure mode is critical for practitioners deciding whether to adopt ActivePTW, and the paper's silence on the mechanism is a weakness.

The theoretical analysis (Section 5.3) is not empirically validated. The paper provides concentration bounds for the forced-exploration variant (Hoeffding + Lemma 6) but does not empirically verify these rates — no plots of posterior concentration over time, no comparison of empirical exploration counts against the theoretical $\Omega(\sqrt{l}/|\mathcal{A}|)$ lower bound, no measurement of how quickly the active segment posterior identifies change-points. The theory demonstrates plausibility, but the empirical section does not close the loop by confirming that the theoretical mechanisms actually operate as claimed in the experiments.

Single change-point structure considered. The PTW prior is over binary temporal partitions, which can only place change-points at dyadic boundaries (powers of 2). The geometric change-point regime generates change-points at arbitrary times, not necessarily aligned with dyadic boundaries. The paper's theoretical analysis (Theorem 4) accounts for this mismatch via the $(\lceil \log_2 t \rceil + 1)$ factor in the redundancy bound, but the empirical section does not investigate how this approximation cost manifests in practice. For example, does ActivePTW perform worse when change-points occur at times that are not powers of 2? Does the posterior place mass on approximate segment boundaries? These questions are relevant for assessing how the binary tree structure limits real-world performance.

The adversarial regime (c) is a single-trace diagnostic, not a comprehensive evaluation. Figure 4 shows one specific construction (two segments, specific arm parameter values). While this successfully demonstrates the necessity of forced exploration, it does not characterize how the algorithms perform across a distribution of adversarial change-point configurations. The geometric adversarial regime mentioned in the problem setting (regime c: geometrically spaced change-points where the previous best arm retains its value) is not experimentally reported, leaving open the question of how ActivePTW($\pi^\varepsilon$) performs on a more realistic stream of adversarial changes.

The claim that ActivePTW reduces to Thompson Sampling in stationary settings is verified only visually. Figure 3 shows overlapping regret curves for ActivePTW(MEU) and Thompson Sampling, described as "nearly identical." No statistical test for equivalence is reported, and the confidence intervals (shaded regions) appear to overlap substantially but are not quantified. This is a mild weakness — the theoretical argument (constant redundancy overhead of $-\log_2 \gamma$ bits) is strong, but the empirical confirmation is qualitative.

Computational cost is not empirically reported. The paper states that ActivePTW requires $O(D + |\mathcal{A}|)$ time per step, but actual wall-clock times, memory usage, or scalability with $D$ and $|\mathcal{A}|$ are not provided. For $T = 10^6$ and $D \approx 20$, maintaining $O(D \cdot |\mathcal{A}|)$ counters is trivial (hundreds of integers), but the dynamic programming recurrence involves numerical operations in log-space that could accumulate floating-point errors over very long horizons — this is not discussed or empirically evaluated.

The experiments genuinely support the paper's central claims, but with important qualifications:

• "ActivePTW achieves 4–10× lower regret than baselines at moderate change rates" — supported by Tables 1–4, but the exact factor depends strongly on arm count and change rate. The advantage is largest at low change rates and moderate arm counts; it disappears (and reverses) at the combination of high arm count and fast change rate. The 4–10× figure is representative but not uniform.

• "The MEU variant reduces to Thompson Sampling in stationary settings" — supported by Figure 3 visually, with a strong theoretical backing (constant redundancy overhead). The practical implication (ActivePTW does not pay a penalty for being change-point-aware when the environment is stationary) is convincingly demonstrated.

• "Forced exploration is essential on adversarial change-point regimes" — supported by Figure 4 for a specific diagnostic construction. The generalizability to arbitrary deceptive environments (where the diagnostic condition — old-best arm retaining value across change-points — holds) is plausible but not experimentally characterized.

• "The modified PTW prior ($\gamma = |\mathcal{A}|/(|\mathcal{A}|+1)$) substantially improves performance" — claimed but not quantitatively demonstrated, which weakens the paper's argument that this is a principled theoretical contribution rather than a heuristic tuning.

• "ActivePTW compares favorably with the state of the art" — supported for MASTER and (best-case) SWUCB, but the absence of Discounted TS and Sliding Window TS leaves open whether the comparison is against the most relevant non-stationary Thompson Sampling variants, rather than primarily against UCB-based methods.

6. Limitations and Trade-offs

The Difficulty Estimation Cost Is Unaccounted for in the Headline Efficiency Gains

The assumption or constraint. The entire compute-optimal framework rests on the ability to estimate a given question's difficulty before deciding how to allocate the test-time compute budget. The paper's method for doing so requires generating 2048 samples per question and averaging either ground-truth correctness (oracle bins) or the PRM's final-answer score (predicted bins). The authors explicitly acknowledge this in Section 3.2:

"estimating difficulty in this way still incurs additional computation cost during inference... our experiments do not account for this cost largely for simplicity"

Generating 2048 samples per question is extraordinarily expensive — it consumes more compute than the largest test-time budgets studied in the experiments (256–512 generations). For a prompt where the system would ultimately allocate, say, 16 generations under the compute-optimal policy, the difficulty estimation step alone requires 128× more compute than the solution process.

The consequence. The reported 4× efficiency gains over best-of-N (Figures 4 and 8) are computed after difficulty is known, without amortizing the cost of learning it. In a realistic deployment, the total cost would be difficulty estimation + strategy execution, and the former could easily dominate the latter. The 4× figure should therefore be understood as an upper bound on achievable efficiency — a theoretical limit that assumes free difficulty labels — rather than a realized deployment gain. A practitioner evaluating this approach would need to compare the total end-to-end cost (including difficulty assessment) against simply running best-of-N with a larger budget, and the paper provides no evidence that the compute-optimal approach would win under that accounting.

The paper also does not discuss the latency implications. Generating 2048 samples before beginning the actual problem-solving process introduces a massive serial delay that would be unacceptable for interactive applications regardless of total FLOPs.

What evidence exists in the paper. The gap is acknowledged explicitly in Section 3.2 but is not measured or bounded in any experiment. There is no ablation showing how performance degrades when difficulty estimation uses fewer than 2048 samples, no analysis of the minimum sample budget required for reliable difficulty binning, and no end-to-end cost accounting that amortizes the difficulty estimation overhead across multiple queries in a batch setting.

Mitigation status. The paper flags this as "a key avenue for future work" (Section 3.2) and suggests training models to predict difficulty directly from the question text, or deploying adaptive schemes that interleave difficulty estimation with problem-solving. No such model or scheme is developed or evaluated. The authors acknowledge that "exploration-exploitation tradeoffs" are involved — compute spent assessing difficulty versus compute spent solving the problem — but offer no guidance on how to navigate this tradeoff in practice. Until this gap is closed, the compute-optimal framework as described is a laboratory demonstration rather than a deployable system.

---

Performance Is Evaluated on a Single Benchmark with a Single Model Family

The assumption or constraint. All experiments use the MATH benchmark (500 test questions) with PaLM 2-S* as the base model. The authors state they "believe this model is representative of the capabilities of many contemporary LLMs" (Section 4), but this belief is not empirically tested. The choice of MATH is deliberately motivated (Section 4): test-time compute is expected to help most when the model possesses the necessary knowledge and the challenge is drawing complex inferences — mathematical reasoning fits this profile. However, this means the results are confined to a specific domain (competition-level symbolic math), a specific difficulty distribution, and a specific model's output characteristics.

The consequence. Several aspects of the findings could be model-specific or domain-specific in ways that practitioners cannot assess from the paper alone:

• The PRM's quality and over-optimization behavior depend on PaLM 2-S*'s output distribution — how calibrated the model is, what kinds of errors it makes, and how its solution quality varies with difficulty. A model with different calibration properties might exhibit different difficulty-dependent scaling curves for beam search versus best-of-N (Figure 3, right).

• The revision model's ability to learn from incorrect in-context examples depends on the base model's in-context learning capabilities, which vary substantially across model families. The paper's revision training procedure (edit-distance-based pairing of incorrect and correct solutions) may transfer differently to models with different output characteristics.

• The MATH benchmark consists of problems with clear ground-truth answers and well-defined solution steps — properties that enable both the PRM training pipeline (Monte Carlo rollout supervision) and the difficulty estimation procedure (pass@1 rate). Whether the difficulty-dependent patterns (beam search hurting easy problems, revisions helping easy problems, neither method helping hard problems) generalize to other reasoning domains — code generation, logical reasoning, scientific QA — or to tasks requiring factual knowledge rather than inference is unknown.

• The test set of 500 questions, split into five difficulty quintiles of ~100 each, then further split by two-fold cross-validation, means the compute-optimal policy is selected based on ~50 questions per fold per bin. This is a small sample, and the paper does not report confidence intervals on the compute-optimal scaling curves (Figures 4 and 8), making it difficult to assess whether the observed strategy choices are statistically reliable or sensitive to the particular 500-question test set. The selected strategy for, say, medium-difficulty problems at 64 generations could change with a different sample of 50 questions.

What evidence exists in the paper. All results (Figures 1–16, Tables, Appendices) are drawn exclusively from MATH with PaLM 2-S*. The paper does not report results on any other benchmark (e.g., GSM8K, HumanEval, MBPP, ARC), any other model family (GPT, LLaMA, Claude), or any non-math reasoning task.

Mitigation status. The authors acknowledge this constraint implicitly by focusing their claims on the MATH benchmark and PaLM 2-S*, but they do not discuss generalizability as a limitation. The paper states that it "believe[s] this model is representative" (Section 4) — a claim that remains unverified by the evidence presented. No replication or transfer study is suggested as future work, though Section 8 mentions extending "to other domains" as a general direction.

---

The 14× Larger Model Baseline Is Not Compute-Optimally Trained and Uses Only Greedy Decoding

The assumption or constraint. The FLOPs-matched comparison in Section 7 scales model parameters by approximately 14× while holding training data fixed, following the LLaMA paradigm (Touvron et al., 2023). The authors explicitly acknowledge this departs from compute-optimal pretraining:

"We choose this setting as it is representative of a canonical approach to scaling pretraining compute and leave the analysis of compute-optimal scaling of pretraining compute where the data and parameters are both scaled equally to future work."

A Chinchilla-optimal model (Hoffmann et al., 2022) trained with 14× more total FLOPs would scale both parameters and data, and would likely outperform a parameter-only-scaled model at the same total training budget. Additionally, the 14× larger model is evaluated using only greedy decoding — no majority voting, no best-of-N, no search of any kind. This means the baseline does not use any test-time compute augmentation, while the smaller model is allowed to use up to 256–512 generations' worth of inference compute.

The consequence. The headline finding — that "a smaller model augmented with compute-optimal test-time strategies can outperform a ~14× larger model" — is evaluated against a weaker-than-necessary baseline. A properly compute-optimal larger model (scaling both parameters and data per Chinchilla) would be a stronger pretraining competitor. Giving that larger model even a modest test-time compute budget — say, best-of-8 or best-of-16 — would create a much more demanding comparison that the paper never tests.

The reported advantage of test-time compute over pretraining in specific regimes (e.g., +27.8% on easy questions at $R \ll 1$ for revisions, from Figure 1 bar charts) may shrink or reverse against a properly optimized larger model with even a small inference budget. The paper's FLOPs-matched analysis therefore provides evidence that test-time compute can substitute for naive pretraining scaling, but does not establish that it should substitute for best-practice pretraining scaling.

What evidence exists in the paper. Section 7 describes the FLOPs accounting and explicitly notes the departure from compute-optimal pretraining. Figure 9 and the Figure 1 bar charts show results for the three $R$ ratio regimes, but all are computed against the parameter-only-scaled, greedy-decoding baseline. The paper does not include an ablation where the larger model receives any test-time compute augmentation, nor does it compare against a Chinchilla-optimal larger model.

Mitigation status. The paper acknowledges this limitation (Section 7) and defers the compute-optimal pretraining comparison to future work. The choice of LLaMA-style scaling is defended as "representative of a canonical approach to scaling pretraining compute" — which is true for many deployed models (LLaMA, LLaMA-2, LLaMA-3) that scale parameters more aggressively than data. However, the paper does not discuss the implications of the greedy-decoding-only baseline for its central claim about the training-inference tradeoff. A fairer comparison — giving the larger model a token-matched inference budget — is not explored.

---

Hard Problems Remain Essentially Unsolved, Establishing a Hard Capability Boundary

The assumption or constraint. The paper's core finding — that compute-optimal test-time scaling provides 4× efficiency gains — applies only to problems where the base model already has a non-trivial probability of producing correct answers. On the hardest questions (difficulty bin 5, where the base model's pass@1 is near zero), no amount of test-time compute helps.

The consequence. This is not a limitation that can be engineered around with better strategies or more compute — it is a fundamental capability boundary. If the base model's pass@1 is effectively zero on a problem class, there are no correct solutions in the proposal distribution to find (via search) or refine (via revisions). The paper's own experiments demonstrate this starkly:

• In Figure 3 (right), bin 5 accuracy for all search methods hovers at 1–3% regardless of whether the budget is 4, 16, 64, or 256 generations. The scaling curve is essentially flat.
• In Figure 7 (right), bin 5 shows roughly 2–3% accuracy irrespective of the sequential-to-parallel ratio.
• In Figure 9, the bin 5 scaling line (bottommost, blue) is essentially flat near 0–5% for both revisions and search, across all test-time compute budgets.

The paper is candid about this (Section 7 takeaway box), but the practical implication is significant: the approach offers no path forward for problems that exceed the base model's training distribution. For such problems, pretraining on more data, larger models, or better data mixtures remains the only viable path. The training-inference tradeoff is therefore not symmetric — test-time compute can amplify existing capability but cannot create it, while pretraining can do both. A practitioner needs to understand this boundary to decide whether investing in better inference strategies or larger pretraining budgets is the right choice for their specific problem distribution.

What evidence exists in the paper. The bin-5 failure is consistent across every experimental setting: search algorithms (Figure 3, right), revision strategies (Figure 7, right), and the FLOPs-matched comparison (Figure 9). The pattern is unambiguous and replicated with both oracle and predicted difficulty bins.

Mitigation status. The paper explicitly states this limitation in the Section 7 takeaway box, calling it a "clear boundary condition: test-time compute amplifies existing capability but does not create it from nothing." However, the paper does not provide guidance on how a practitioner should distinguish, a priori, whether their problem distribution falls into this regime — i.e., whether the base model has non-zero pass@1 on their problems. The difficulty estimation method (2048 samples) could theoretically answer this in deployment, but at the prohibitive cost discussed in the first limitation. Additionally, the paper does not explore whether combining test-time compute with different base models (e.g., switching to a model stronger on hard math) could address the bin-5 failure, or whether the capability boundary is task-specific or more general.

---

Verifier Over-Optimization Is a Hard Ceiling That the Compute-Optimal Policy Mitigates but Does Not Solve

The assumption or constraint. The paper identifies verifier over-optimization as the primary bottleneck preventing unbounded improvements from additional test-time compute: search algorithms (especially beam search and lookahead search) eventually find solutions that score highly under the PRM but are actually incorrect. The paper provides concrete evidence across multiple experiments:

• Beam search degrades easy-problem performance at high budgets (Figure 3, right) — on bin 1, accuracy decreases from roughly 78% to 77% as budget goes from 4 to 256 generations, while best-of-N weighted correctly improves.
• Lookahead search — the most powerful optimizer — paradoxically performs worst overall (Figure 3, left) because its aggressive optimization exploits the PRM's reward signal most effectively.
• Qualitative examples in Appendix M (Figures 29 and others) show search producing degenerate outputs — repetitive low-information steps at the end of solutions, and overly short 1–2 step solutions — that score highly under the PRM.

The consequence. The compute-optimal policy mitigates over-optimization by routing easy problems away from aggressive search (using best-of-N instead of beam search) and by deploying beam search only on medium-difficulty problems where the PRM's guidance genuinely helps. But this is a workaround, not a solution. The underlying problem — the PRM can be exploited — means that:

• On medium-difficulty problems where beam search is deployed, performance still flattens and eventually declines as the budget increases (Figure 3, right, bins 2–3). The compute-optimal policy just switches strategies before the worst degradation occurs.
• The achievable performance ceiling is fundamentally limited by verifier quality, not by search algorithm sophistication. Improving the search algorithm beyond a certain point is counterproductive — the paper's lookahead search results (Figure 3, left) demonstrate that stronger optimization produces worse results.
• The paper's central finding (4× efficiency gains) is therefore specific to the current verifier quality — it represents the best achievable performance given a PRM trained with the Monte Carlo rollout procedure in Appendix D. If the PRM were better calibrated, the over-optimization threshold would shift, the optimal strategy would change, and the 4× figure would differ.

A practitioner who invests in better PRM training — more on-policy data, adversarial training, ensemble methods — might find that the compute-optimal policy shifts substantially, potentially making beam search viable on easy problems or enabling lookahead search to outperform simpler methods. The paper provides no guidance on how verifier improvements would alter the scaling landscape or the compute-optimal allocation.

What evidence exists in the paper. The over-optimization evidence is extensive: Figure 3 (left and right) for search methods, Appendix M for qualitative examples, and the paper's discussion in Sections 5.3 and 8. The paper explicitly calls this out in Section 8: "improving verifier robustness is the key bottleneck for further scaling test-time compute."

Mitigation status. The paper acknowledges the problem and suggests future work on "robust verifiers resistant to over-optimization" (Section 8), including adversarial training, ensemble verification, and constrained search methods. None of these are explored experimentally. The current compute-optimal policy is presented as a way to route around the problem, not to solve it — which is a reasonable practical strategy but leaves the fundamental scaling ceiling in place. The paper does not quantify how much performance is left on the table due to verifier over-optimization (e.g., what accuracy would be achievable with a perfect verifier, or how close the current PRM is to that ideal).

---

Test-Time Compute Cannot Compensate for Fundamental Capability Gaps at High Inference-to-Pretraining Ratios

The assumption or constraint. The FLOPs-matched comparison in Section 7 introduces the parameter $R = D_{\text{inference}} / D_{\text{pretrain}}$ — the ratio of total inference tokens generated over the model's lifetime to the number of pretraining tokens. The paper tests three values: $R \ll 1$ (0.16), $R \approx 1$ (0.79), and $R \gg 1$ (22). The finding is sharp: test-time compute with the smaller model is preferable when $R$ is small, but becomes increasingly disadvantageous as $R$ grows — especially on harder problems.

The consequence. This means the paper's central recommendation — "sometimes it is more cost-effective to train a smaller model and invest the savings in smarter inference" — is highly regime-dependent in ways that the paper quantifies but does not provide simple heuristics for. A practitioner needs to know their expected $R$ to determine whether the advice applies to their deployment. The failure cases are stark:

• PRM search at $R \gg 1$: The smaller model with compute-optimal search is worse than the 14× larger model on medium questions (−30.8%) and hard questions (−52.9%), with only easy questions showing a marginal advantage (+2.0%). If a deployment involves high inference volume relative to pretraining (e.g., a production chatbot serving millions of queries), the paper's own evidence suggests that scaling pretraining is the better investment.

• Revisions at $R \gg 1$: The pattern is less severe but still shows hard questions at −37.2% relative disadvantage for test-time compute. Only easy and medium questions remain favorable.

The paper's results are also computed assuming the smaller model gets all the FLOPs savings as additional inference budget. In practice, the decision to train a smaller model versus a larger one is made before knowing $R$, and $R$ depends on how heavily the model is used post-deployment. A model used lightly ($R \ll 1$) should be smaller with heavy test-time compute; a model used heavily ($R \gg 1$) should be larger with minimal test-time compute. But this decision must be made at training time, creating a planning-under-uncertainty problem that the paper identifies but does not solve.

What evidence exists in the paper. Figure 9 and the Figure 1 bar charts provide detailed breakdowns by difficulty level and $R$ regime. The numbers quoted above are read from the bar charts (Figure 1, bottom-right for PRM search, top-right for revisions). The $R$ dependence is a central result of Section 7.

Mitigation status. The paper presents the $R$ dependence as a finding rather than a limitation, which is appropriate — it is a genuine empirical contribution to show when test-time compute can and cannot substitute for pretraining. However, the paper does not provide practical guidance on how to estimate $R$ before deployment, how to decide the optimal model size given uncertainty about future inference volume, or how the tradeoff changes for intermediate values of $R$ (only three point estimates are tested). These are natural follow-up questions that the current analysis motivates but does not answer. Section 8 mentions joint optimization of pretraining and inference compute as a future direction but does not develop it.

7. Implications and Future Directions

How This Work Changes the Landscape

This paper shifts the conversation around non-stationary bandit algorithms from hyperparameter engineering toward a principled Bayesian framework for posterior inference over temporal structure. The key move is reframing change-point adaptation not as a question of choosing the right window size or restart probability, but as maintaining a posterior distribution over all possible segmentations of the interaction history and using that posterior to drive action selection through a compression-derived control policy.

The magnitude of this shift is somewhere between a reframing and a new diagnostic capability, rather than a full paradigm shift. Non-stationary bandit algorithms already existed (windowing methods, restarting meta-algorithms), and the Bayesian Control Rule + Thompson Sampling connection was previously established for stationary settings. What changes is the diagnostic precision: the paper shows when different approaches to non-stationarity work and why, by identifying the structural condition that separates regimes where exploitative policies suffice from those where forced exploration becomes necessary.

Specifically, the paper resolves a latent tension in the literature that practitioners may have felt but couldn't articulate. On one hand, windowing methods (Sliding Window UCB, Discounted TS) work well when their hyperparameter matches the change-point rate — but this matching requires advance knowledge that is rarely available. On the other hand, stochastic restarting (MASTER) avoids hand-tuning but commits to a single restart schedule at a time, paying a cost for unnecessary restarts in stationary settings. The implicit question has been: is there a way to get the best of both — adapting to change-points when they occur while avoiding unnecessary overhead when the environment is stable — without knowing the change rate in advance? ActivePTW's answer is that Bayesian model averaging over temporal partitions achieves exactly this, because the posterior automatically concentrates on long segments when the data supports stationarity and shifts toward short segments when change-points are detected, with the transition being evidence-graded rather than hard-coded.

This reframing makes several research directions more attractive and several less so:

Directions that become more attractive. Bayesian nonparametric models for temporal structure in online decision-making now have a clear computational template — the binary partition tree with dynamic programming. The paper demonstrates that exponential partition spaces can be collapsed to linear-time inference without losing decision-relevant uncertainty, using the active segment concept. This template could be applied to other structured decision problems (contextual bandits with non-stationary contexts, semi-Markov decision processes with unknown state durations, change-point detection in hierarchical models). The modified PTW prior ($\gamma = |\mathcal{A}|/(|\mathcal{A}|+1)$) also opens the door to structured universal priors — priors that are universal for a problem class but adapted to known structural properties (like action space size) to improve efficiency. This sits between fully generic universal priors (which work for anything but may adapt slowly) and fully tuned problem-specific priors (which require validation data).

Additionally, the paper's diagnostic — that the necessity of explicit exploration depends on whether the previously-optimal arm's reward changes at a change-point — provides a concrete, testable condition. A practical system could monitor this condition online: if the arm currently being exploited shows stable rewards, the system could gradually increase exploration to guard against the "deceptive" regime, without needing to commit to a fixed forced-exploration schedule. This is a form of meta-learning the exploration rate from the environment's feedback structure, not from cumulative regret alone.

Directions that become less attractive. The paper's results suggest that further refinement of window-size heuristics may be a diminishing-returns path. If the core problem is that windowing methods make a hard binary decision about which data to include — discarding older observations entirely — then no amount of clever window-size tuning will match the soft, evidence-graded adaptation that a Bayesian posterior over segmentations provides. The paper's experiment with SWUCB (where the window was set to the known expected segment length, yet SWUCB still substantially underperformed ActivePTW at low change rates, as seen in Tables 1–4) is particularly telling: even with oracle knowledge of the change rate, the fixed-window approach discards useful data that a posterior-weighted mixture would retain at partial weight.

Similarly, the paper's negative result on the active segment posterior's failure at high arm counts and fast change rates (Table 4, $|\mathcal{A}| = 50$, $p = 0.01$) suggests that throwing more Bayesian computation at fundamentally data-poor regimes does not help. When segments contain only ~2 observations per arm on average, inferring segment structure is hopeless regardless of the inference algorithm. In these regimes, simple uniform exploration (UCB) dominates, and research effort is better spent on (a) designing algorithms that automatically detect when they're in this regime and fall back to uniform exploration, or (b) using structured priors that incorporate prior knowledge about arm similarity to share statistical strength.

---

Follow-Up Research This Work Enables

ActivePTW with arm-conditional change-point models. The current NSSBP model assumes that when a change-point occurs, all arms' parameters are resampled. This is a worst-case assumption that may be too conservative for many real applications. In online advertising, a user's preference for one product category might change while their preference for another remains stable. The PTW-KT framework could be extended to maintain arm-specific segmentations — different temporal partitions for different arms — with a prior that encourages sharing of change-points across arms that tend to change together. A concrete experiment: generate NSSBPs where only a subset of arms change at each change-point (e.g., Poisson-distributed trigger events affecting each arm independently), and compare ActivePTW against a variant where each arm maintains its own active segment posterior, with the hierarchical prior encouraging but not forcing shared change-points. The key metric would be whether the per-arm model adapts faster to local changes while still sharing statistical strength during stationary periods.

Online meta-learning of the $\gamma$ parameter from data. The paper fixes $\gamma = |\mathcal{A}|/(|\mathcal{A}|+1)$ based on a worst-case redundancy argument, but this prior could be adapted online as the agent observes the actual change-point frequency. A natural extension would place a hyperprior over $\gamma$ (e.g., a Beta distribution) and update it based on the posterior probability of splits versus stops in the PTW tree. This would allow the algorithm to start with the minimax-optimal $\gamma$ and gradually sharpen or relax the prior as it learns whether the environment is more or less stationary than the worst case. The concrete experiment: run ActivePTW on environments with varying true change rates, and compare the fixed-$\gamma$ version against a version that maintains a Beta posterior over $\gamma$, updating it at each step using the PTW recurrence. Measure (a) whether the adaptive $\gamma$ converges to the true change rate when one exists, and (b) whether the adaptive version achieves lower regret than the fixed version in environments where the true change rate differs substantially from the minimax assumption.

Combining ActivePTW with structured priors over arm parameters. The current KTE uses independent Jeffreys priors for each arm, which treats arms as completely unrelated. In many applications (dynamic pricing across related products, clinical trials with similar treatments), arms have structured relationships — some arms may have similar reward probabilities, or the ordering of arm qualities may persist across change-points. A hierarchical Bayesian model over arm parameters (e.g., a Dirichlet process mixture or a Gaussian process over the arm index) would allow the agent to generalize observations across arms, accelerating learning within each segment. The concrete experiment: construct NSSBPs where arm parameters are drawn from a latent clustered structure (e.g., 50 arms belonging to 5 latent clusters, with cluster membership fixed across change-points but cluster means changing). Compare ActivePTW with independent per-arm KT estimators against a variant that maintains a Dirichlet process posterior over arm clusters, sharing counts within clusters. The hypothesis: the structured variant should substantially outperform at high arm counts and moderate change rates, because it can learn about 5 clusters from data on 50 arms rather than needing to learn 50 independent parameters.

Stress-test: ActivePTW on changing action spaces. The current formulation assumes a fixed action space $\mathcal{A}$ across all segments. In many real applications, arms become available or unavailable over time (new products are introduced, old ones are discontinued, ad campaigns start and end). Extending ActivePTW to handle transient arms — where each arm has a time window of availability — would test whether the segment inference machinery naturally handles this case. The concrete experiment: generate NSSBPs where arms have random birth and death times, with reward parameters resampled at each birth. A natural baseline would be a version of ActivePTW that maintains a "currently available" mask and only considers arms whose availability window contains the current time, with the PTW-KTE counters only incremented when the arm is available. Whether the active segment posterior correctly identifies birth/death events as distinct from change-points (or conflates them) would reveal a fundamental limitation or capability of the tree-based temporal model.

Negative result: identifying when the binary tree structure imposes a real approximation cost. The PTW prior is over binary temporal partitions, which can only place change-points at dyadic boundaries (positions that are multiples of powers of 2). The redundancy bound (Theorem 4) accounts for this with a $\lceil \log_2 t \rceil$ factor, but the paper does not empirically characterize when this approximation cost actually matters. A stress-test experiment: generate NSSBPs where change-points are deliberately placed at non-dyadic positions (e.g., at times 3, 7, 13, 21 — avoiding powers of 2), and compare ActivePTW's regret against an oracle that knows the exact change-point locations. Also compare against a variant of ActivePTW with a shifted or offset partition tree that can place boundaries at arbitrary positions within some granularity. The result would characterize the practical cost of the dyadic constraint and determine whether more flexible partition classes (e.g., ternary trees, or trees with learned split positions) are worth the additional computational complexity.

Theoretical closure: finite-time regret bound for ActivePTW($\pi^\varepsilon$). The paper provides probabilistic building blocks — forced exploration guarantees ($\Omega(\sqrt{n}/|\mathcal{A}|)$ pulls per arm per segment, with high probability) and posterior concentration (Lemma 6) — but does not assemble them into a formal regret bound. A natural next step is to prove that under the MEUFE policy, ActivePTW achieves $O(|\mathcal{A}| \sqrt{T \log T})$ or similar sublinear regret for a well-defined class of NSSBPs (e.g., those with at most $K$ change-points, or those where the total variation in arm parameters is bounded). The main technical challenge is handling the interaction between the active segment posterior and the policy: the segment posterior determines the effective data window used for Thompson Sampling, but the policy determines which data enters that window, creating a circular dependence. Breaking this circularity — likely by showing that the forced exploration rate dominates the policy's exploitation bias in determining the data distribution — would provide the theoretical guarantee that the paper's empirical results suggest is achievable. Even a negative result (proving that the interaction prevents sublinear regret without further assumptions) would be valuable for delineating when the approach is theoretically sound.

---

Practical Applications and Downstream Use Cases

Automated A/B testing with unknown experiment drift. In continuous A/B testing pipelines (website optimization, email marketing, product feature rollouts), the baseline conversion rate often drifts over time due to seasonality, user population changes, or external events. Standard bandit algorithms (Thompson Sampling, UCB) gradually stop exploring as they converge on apparently-superior variants, making them blind to subsequent drifts. ActivePTW offers a drop-in replacement that automatically detects when the baseline has shifted and re-allocates traffic accordingly, without requiring the experimenter to specify a window size or restart schedule. The paper's results with $|\mathcal{A}| = 5$ arms at moderate change rates (Table 2) show ActivePTW achieving 4–10× lower regret than SWUCB and MASTER — in an A/B testing context where each "regret unit" is a lost conversion or click, this translates directly to revenue preservation during drift periods. The key practical advantage over existing solutions is that the algorithm needs no per-experiment tuning: the same ActivePTW instance (with $D$ set to cover the maximum planned experiment duration) can be deployed across experiments with different drift characteristics.

Dynamic pricing with competitor-induced regime shifts. In e-commerce or ride-sharing, optimal pricing responds to competitor actions — a competitor entering the market, launching a promotion, or adjusting their base price changes the demand curve. ActivePTW can be applied by treating each price point as an arm and each observed purchase (or ride acceptance) as a Bernoulli reward. When a competitor changes strategy, the demand curve shifts — a change-point in the bandit environment. ActivePTW's posterior over segments would detect this shift from the reward data alone (purchase rates at previously-optimal prices change) and begin re-exploring the price space. The forced-exploration variant (ParanoidPTW) would be specifically valuable in markets where competitor actions can be deceptive — e.g., a competitor temporarily matching your price to prevent you from detecting that a different price point has become optimal. The paper's diagnostic condition (whether the previously-optimal arm's reward changes at the change-point) maps directly to whether the competitor's action affects the demand at your current price. A deployable system would use ActivePTW to maintain a posterior over price-segments and could trigger re-optimization only when the segment posterior indicates a regime change, reducing unnecessary price experimentation during stable periods.

Clinical trial adaptive randomization with changing patient populations. In multi-arm clinical trials, the patient population can shift over time as enrollment expands to new sites or demographic groups. A treatment that appeared optimal in early (homogeneous) enrollment may underperform as the population diversifies. ActivePTW provides a principled alternative to fixed-block or response-adaptive randomization: the active segment posterior automatically detects when the reward structure has changed (indicating a population shift) and adjusts the randomization probabilities to re-explore treatments. The key advantage over existing adaptive designs is that ActivePTW's evidence-graded adaptation — rather than an all-or-nothing restart — would smoothly transition from exploiting early findings to re-exploring when the patient population changes, without requiring the trial designers to pre-specify when population shifts might occur. The $\gamma = |\mathcal{A}|/(|\mathcal{A}|+1)$ prior bias toward simpler segmentations is also appropriate here: with small numbers of treatment arms (typically 2–5), the algorithm would maintain moderate sensitivity to change-points rather than requiring extremely strong evidence.

---

When to Prefer This Method

The paper explicitly articulates tradeoffs between ActivePTW variants and against named alternatives, so this section is appropriate.

• Prefer ActivePTW($\pi^*$, MEU) over Sliding Window UCB or MASTER when: (a) the environment's change-points are expected to cause visible degradation in the currently-optimal arm's reward (i.e., exploiting the old-best arm naturally reveals the change, as in the geometric regime with uniform reinitialization — Tables 1–4), (b) the number of arms is moderate relative to the expected segment length ($|\mathcal{A}| \lesssim \sqrt{\mathbb{E}[L]}$, approximately), so that sufficient data exists per segment for the segment posterior to concentrate, and (c) you cannot specify a good window size or restart rate in advance — ActivePTW's Bayesian model averaging removes this hyperparameter entirely, which is its primary practical advantage.

• Prefer ActivePTW($\pi^\varepsilon$, ParanoidPTW) over ActivePTW($\pi^*$) when: the environment may be "deceptive" — specifically, when there is a non-trivial probability that a change-point leaves the currently-exploited arm's expected reward unchanged while making another arm superior (the adversarial regime from Figure 4). The forced exploration guarantees that the agent eventually discovers the new optimum regardless of the environment's deception. The cost is a permanent exploration overhead (~$l^{-1/2}$ per segment of length $l$) that reduces performance in non-deceptive regimes (Tables 1–4 show ParanoidPTW trailing MEU by 8–200% across geometric regimes). A practical heuristic: if you cannot characterize whether your environment is deceptive, prefer ParanoidPTW as the safer default, accepting the exploration overhead as an insurance premium against catastrophic failure.

• Prefer UCB1 over ActivePTW when: the number of arms is large relative to the expected segment length ($|\mathcal{A}|$ is comparable to or larger than $\sqrt{\mathbb{E}[L]}$, approximately). Table 4 ($|\mathcal{A}| = 50$, $p = 0.01$, expected segment length 100) shows UCB1 achieving 15557 ± 81 regret versus ActivePTW at 28429 ± 82 — the Bayesian segment inference provides no benefit and actively hurts because there is simply not enough data per segment to identify segment structure. In this regime, uniform exploration (which UCB provides without attempting to model change-points) dominates. This is the operationalization of the paper's candid admission that "a general solution is of course impossible" when changes are too rapid relative to the action space size.

• Prefer MASTER over ActivePTW when: (a) you require finite-time regret guarantees (MASTER's are proven; ActivePTW's are deferred to future work), (b) the environment's change-point structure is known to match the assumptions of MASTER's theoretical analysis, and (c) the slight empirical disadvantage of MASTER at moderate change rates (Tables 1–3) is acceptable in exchange for the theoretical guarantee. The paper's empirical results show MASTER trailing ActivePTW by 1.2–6× across most regimes but occasionally matching or slightly exceeding it ($|\mathcal{A}| = 10, p = 0.01$, Table 3, where MASTER at 14855.74 edges ActivePTW at 16559.30, though confidence intervals overlap).