LFBL Research — MAB Formalism (in progress)

Part of Learning-from-Learner Theory; sibling to the MDP-formalism note. In-progress research note, synced from a notes.inria.fr source to Markdown + KaTeX. The inverse multi-armed-bandit (“learning from a biased learner”) theory side.

Re-synced 2026-08-25 from the updated source — this is a rewrite, not an edit. The note roughly quadrupled (12 KB → 54 KB) and is now organised as passive problems → active interventions → proofs, carrying five numbered theorems with a dedicated proof section. The previous revision’s structure — subjective posterior / internally rational policy, the single dynamic-observational-equivalence theorem, inverse Bayesian inference via NPF, and the probabilistic memory-hint intervention — has been replaced rather than extended. Nothing from the old version was transplanted into the new sections; see the Slack thread for what dropped.

1. Problem Formulation

I am trying to compare a completely biased agent that merely validates its own hypotheses. This is an AI safety project enabling the model to recognize that the human is a biased agent. First let’s try to modelise our biased agent, we will modeliser our observator after.

Framework

We consider a Multi-Armed Bandit (MAB) problem with $K$ arms, indexed by $k\in \{1,\dots ,K\}$. Each arm $k$ is characterized by an unknown reward distribution $P(r\mid {\mu }_k)$ parameterized by the mean of $k$-arm ${\mu }_k\in \Theta$. Let $\mathbf{\mu }=({\mu }_1,\dots ,{\mu }_K)\in {\Theta }^K$ represent the true state of the environment.

At each discrete time step $t\in \{1,\dots ,T\}$, the agent selects an action $a_t\in \{1,\dots ,K\}$ and receives a reward $r_t\sim P(r\mid {\mu }_{a_t})$. We denote the objective history up to time $t-1$ as $h_t:=\{(a_i,r_i){\}}_{i=1}^{t-1}\in {\mathcal{H}}_t$.

Reference Unbiased Agent (${\mathcal{A}}_{\text{learning}}$)

A standard Bayesian learning agent retains the complete objective history $h_t$. Given an initial prior $b_0\in \mathcal{P}({\Theta }^K)$, its objective posterior belief at step $t$ is:

$$b_t(\mathbf{\mu })\propto b_0(\mathbf{\mu })\prod _{i=1}^{t-1}P(r_i\mid a_i,{\mu }_{a_i})$$

We denote its standard objective expected return for arm $k$ as ${\hat{\mu }}_k^{(t)}:={\mathbb{E}}_{b_t}[{\mu }_k]$.

Biased Agent (${\mathcal{A}}_{\text{bias}}$)

Unlike the reference agent, the Biased Agent does not directly retain the true reward $r_t\sim P(r\mid {\mu }_{a_t})$ generated by the environment. Instead, its perception is subjectively corrupted by its current expectation, reflecting cognitive distortions such as confirmation bias.

At time step $t$, upon selecting action $a_t$ and receiving the ground-truth reward $r_t$, the agent observes a subjectively perceived reward ${\tilde{r}}_t$ sampled from a perceptual distortion distribution:

$${\tilde{r}}_t\sim P_{\text{bias}}\left(\tilde{r}|r_t,{\tilde{\mu }}_{a_t}^{(t-1)}\right)$$

where ${\tilde{\mu }}_{a_t}^{(t-1)}:={\mathbb{E}}_{{\tilde{b}}_{t-1}}[{\mu }_{a_t}]$ represents the agent’s prior expected return for arm $a_t$. The agent consequently maintains a subjective history ${\tilde{h}}_t:=\{(a_i,{\tilde{r}}_i){\}}_{i=1}^{t-1}\in {\mathcal{H}}_t$.

Subjective Belief Update

Given a subjective prior ${\tilde{b}}_0\in \mathcal{P}({\Theta }^K)$, the agent updates its posterior belief ${\tilde{b}}_t$ by treating the perceived outcomes in ${\tilde{h}}_t$ as standard objective signals via Bayes’ rule:

$${\tilde{b}}_t(\mathbf{\mu })\propto {\tilde{b}}_0(\mathbf{\mu })\prod _{i=1}^{t-1}P({\tilde{r}}_i\mid a_i,{\mu }_{a_i})$$

where $P({\tilde{r}}_i\mid a_i,{\mu }_{a_i})$ is the standard likelihood function evaluated at the candidate parameter ${\mu }_{a_i}$.

We denote the biased agent’s subjective expected reward for arm $k$ at time $t$ as: ${\tilde{\mu }}_k^{(t)}:={\mathbb{E}}_{{\tilde{b}}_t}[{\mu }_k]$

Observer Agent (${\mathcal{A}}_{\text{obs}}$)

To mitigate sycophancy and evaluate user bias without relying on unobservable ground-truth signals, we model the LLM as an Observer Agent (${\mathcal{A}}_{\text{obs}}$).

Information Structure and Constraints

The observer has no access to ground-truth environment rewards $r_t$ or subjectively perceived rewards ${\tilde{r}}_t$. At step $t$, ${\mathcal{A}}_{\text{obs}}$ observes solely the user’s action history:

$$h_t^a:=\{a_1,\dots ,a_{t-1}\}\in {\mathcal{H}}_t^a$$

Let $z\in \{0,1\}$ denote the latent user type:

• $z=0$ corresponds to the objective learning agent ${\mathcal{A}}_{\text{learning}}$,
• $z=1$ corresponds to the biased agent ${\mathcal{A}}_{\text{bias}}$.

Generative Model of User Actions via Thompson Sampling

We model the user as a Bayesian decision-maker employing Thompson Sampling over their posterior belief. Let ${\bar{b}}_{t-1}(\mathbf{\mu }\mid z)$ denote the user’s belief distribution at step $t-1$ under type $z$, where ${\bar{b}}_{t-1}(\mathbf{\mu }\mid z=0)=b_{t-1}(\mathbf{\mu })$ and ${\bar{b}}_{t-1}(\mathbf{\mu }\mid z=1)={\tilde{b}}_{t-1}(\mathbf{\mu })$.

At step $t$, the user draws a parameter vector $\mathbf{\theta }=({\theta }_1,\dots ,{\theta }_K)$ from their current belief and selects the action that maximizes expected return:

$${\mathbf{\theta }}^{(t)}\sim {\bar{b}}_{t-1}(\mathbf{\mu }\mid z),a_t=\arg \underset{k\in \{1,\dots ,K\}}{\max }{\theta }_k^{(t)}$$

Thus, the marginal likelihood of observing action $a_t=k$ given the user type $z$ corresponds to the probability that arm $k$ yields the highest sample under the user’s posterior distribution:

$$P(a_t=k\mid h_t^a,z)={\mathbb{P}}_{\mathbf{\theta }\sim {\bar{b}}_{t-1}(z)}\left({\theta }_k=\underset{j\in \{1,\dots ,K\}}{\max }{\theta }_j\right)$$

Bayesian Bias Inference

Given a prior $P(z)$ over user types, ${\mathcal{A}}_{\text{obs}}$ updates its posterior belief $P(z\mid h_t^a)$ sequentially via Bayes’ rule:

$$P(z\mid h_t^a)\propto P(z)\prod _{i=1}^{t-1}P(a_i\mid h_i^a,z)$$

Since Thompson Sampling directly draws from the user’s posterior ${\bar{b}}_{t-1}(z)$, this likelihood accounts for both the user’s expected returns and their subjective uncertainty.

2. Passive Problems

Theoretical Analysis: Confirmation Trap in Biased Agents

To formalize how confirmation bias leads to an irreversible belief lock-in, we define a standard condition on the perceptual distortion distribution $P_{\text{bias}}$.

Assumption 1 (Negative prediction-error attenuation). There exists a confirmation factor $\gamma \in (0,1]$ such that for any selected action $a_t$ with true parameter ${\mu }_{a_t}$, if the agent’s prior expectation exceeds the reward of arm $a_t$ (${\tilde{\mu }}_{a_t}^{(t-1)}>r_t$), the subjectively perceived reward satisfies:

$${\mathbb{E}}_{\tilde{r}\sim P_{\text{bias}}}\left[\tilde{r}|r_t,{\tilde{\mu }}_{a_t}^{(t-1)}\right]\ge r_t+\gamma \left({\tilde{\mu }}_{a_t}^{(t-1)}-r_t\right)$$

Assumption 1 captures the core mechanic of confirmation bias: negative deviations from the user’s prior expectation are systematically attenuated or discounted.

Assumption 2 (Persistent confirmation near certainty). There exists $C>0$ and $p>1$ in a Bernoulli setting such that:

$$P_{\mathrm{bias}}(\tilde{r}=0\mid r=0,{\tilde{\mu }}_{a_t}^{(t-1)})\le C(1-{\tilde{\mu }}_{a_t}^{(t-1)}{)}^p$$

and

$$P_{\mathrm{bias}}(\tilde{r}=1\mid r=1,{\tilde{\mu }}_{a_t}^{(t-1)})=1$$

Assumption 2 captures the probability that a negative result will remain subjectively negative therefore decreases superlinearly.

Theorem 1 (Positive-probability confirmation trap). Consider a $K$-armed Bernoulli bandit with true means $\mathbf{\mu }\in [0,1{]}^K$. Suppose that the biased agent uses Thompson Sampling and has independent subjective priors

$${\tilde{b}}_0(\mathbf{\mu })=\prod _{j=1}^K\mathrm{Beta}({\alpha }_j,{\beta }_j),{\alpha }_j>0,{\beta }_j>0$$

Fix an arm $k$ that is strictly suboptimal, so that

$${\Delta }_k:={\mu }^{\star }-{\mu }_k>0,{\mu }^{\star }:=\underset{j\in \{1,\dots ,K\}}{\max }{\mu }_j$$

Suppose that Assumptions 1 and 2 hold and that the upper-tail parameters of every competing arm satisfy

$${\beta }_{\min }^{(-k)}:=\underset{j\ne k}{\min }{\beta }_j>1$$

Then there exists an event ${\mathcal{E}}_k$ with strictly positive probability such that the agent selects arm $k$ and perceives a positive reward at every time step:

$$\mathbb{P}({\mathcal{E}}_k)>0,{\mathcal{E}}_k:=\bigcap _{t=1}^{\infty }\{a_t=k,{\tilde{r}}_t=1\}$$

Consequently,

$$\mathbb{P}(a_t=k\text{ for every }t\ge 1)>0$$

On ${\mathcal{E}}_k$, the subjective posterior mean of arm $k$ converges to one and the conditional Thompson Sampling probability of selecting arm $k$ converges to one:

$${\tilde{\mu }}_k^{(t)}⟶1,P(a_{t+1}=k\mid {\tilde{h}}_{t+1})⟶1$$

Moreover, if $R_T$ denotes the frequentist pseudo-regret, then there exists a constant ${\rho }_k>0$, independent of $T$, such that

$$\mathbb{E}[R_T]\ge {\rho }_k{\Delta }_{k}T$$

Proof in last section $■$

Remark 1 (Role of the assumptions). Assumption 1 ensures that every step of the confirming trajectory has strictly positive probability, including when the objective reward is zero. Assumption 2 provides the stronger summability property required for permanent lock-in. In particular, Assumption 1 alone does not imply a confirmation trap.

Remark 2 (Why the prior-tail condition is needed). The condition ${\beta }_{\min }^{(-k)}>1$ ensures that the Thompson Sampling escape probabilities are summable. If some competing arm satisfies ${\beta }_j\le 1$, the bound obtained above is not summable, and Assumptions 1 and 2 alone do not guarantee permanent lock-in.

Remark 3 (Positive probability versus almost-sure lock-in). The theorem establishes a permanent confirmation trap with strictly positive probability, not with probability one. Almost-sure lock-in would require an additional global condition controlling the switching probability on every possible history, rather than only along the fully confirming trajectory.

Theoretical Analysis: Action-Only Non-Identifiability

We now investigate whether an observer having access only to the user’s actions can determine whether the user is biased. Because the observer observes neither the objective rewards nor the subjectively perceived rewards, perceptual distortion may be observationally confounded with the unknown environment.

For any user model $M$, let

$$P_M^{a,T}:={\mathcal{L}}_M(a_1,\dots ,a_T)$$

denote the probability distribution over action histories of length $T$ induced by that model.

Definition 1 (Action-identifiability). Let ${\mathcal{M}}_0$ and ${\mathcal{M}}_1$ denote the classes of admissible unbiased and biased user models, respectively, and let $P_M^{a,\infty }$ denote the probability law of the infinite action process generated by model $M$. The user type is identifiable from actions if

$$\left\{P_M^{a,\infty }:M\in {\mathcal{M}}_0\right\}\cap \left\{P_M^{a,\infty }:M\in {\mathcal{M}}_1\right\}=\varnothing$$

Equivalently, the type is not action-identifiable if there exist models $M_0\in {\mathcal{M}}_0$ and $M_1\in {\mathcal{M}}_1$ such that

$$P_{M_0}^{a,T}=P_{M_1}^{a,T}$$

for every finite horizon $T\ge 1$.

Assumption 3 (Static bias) Let a perceptually biased agent that transforms each objective reward through a non-trivial, memoryless, arm-independent, and history-independent binary channel, conditionally independently across rounds given the objective rewards, satisfying

$$P_{\mathrm{bias}}(\tilde{r}=1\mid r=1)=u,P_{\mathrm{bias}}(\tilde{r}=1\mid r=0)=v$$

where $u,v\in [0,1]$ and $(u,v)\ne (1,0)$.

Assumption 3 captures the core mechanic of confirmation bias: negative deviations from the user’s prior expectation are systematically attenuated or discounted.

Theorem 2 (Action-only non-identifiability in unknown Bernoulli environments) Consider a $K$-armed Bernoulli bandit with unknown true means

$$\mathbf{\mu }=({\mu }_1,\dots ,{\mu }_K)\in [0,1{]}^K$$

Suppose $M_1$ as assumption 3 and treats each perceived reward ${\tilde{r}}_t$ as an objective Bernoulli observation when updating its posterior.*

Define the effective arm means

$${\nu }_k:=u{\mu }_k+v(1-{\mu }_k),k\in \{1,\dots ,K\}$$

and let

$$\mathbf{\nu }:=({\nu }_1,\dots ,{\nu }_K)$$

Let $M_0$ be an unbiased agent operating in a Bernoulli environment with true means $\mathbf{\nu }$. Suppose that $M_0$ and $M_1$ have the same initial prior and use the same Thompson Sampling rule, including the same tie-breaking rule.

Then the biased model $M_1$ in environment $\mathbf{\mu }$ and the unbiased model $M_0$ in environment $\mathbf{\nu }$ induce exactly the same distribution over action histories:

$$P_{M_1}^{a,T}=P_{M_0}^{a,T}$$

for every horizon $T\ge 1$. Consequently, the user type is not identifiable from actions alone.

Moreover, for every estimator ${\hat{z}}_T={\hat{z}}_T(a_1,\dots ,a_T)$ based only on the action history,

$$\max \left\{P_{M_0}({\hat{z}}_T=1),P_{M_1}({\hat{z}}_T=0)\right\}\ge \frac{1}{2}$$

Hence, no action-only estimator can be uniformly consistent over any model classes containing $M_0$ and $M_1$.

Proof in last section $■$

Corollary 1 (No Bayesian learning between observationally equivalent models) Suppose that the observer’s hypothesis space consists exactly of the two models $M_0$ and $M_1$ constructed in Theorem 2. Let

$${\pi }_0:=P(M_0)>0,{\pi }_1:=P(M_1)>0,{\pi }_0+{\pi }_1=1$$

Then, for every action history $h_{T+1}^a$ having positive probability,

$$P(M_1\mid h_{T+1}^a)={\pi }_1$$

Proof. By Theorem 2, the two models assign the same likelihood to every action history:

$$P(h_{T+1}^a\mid M_0)=P(h_{T+1}^a\mid M_1)=:L(h_{T+1}^a)$$

Bayes’ rule therefore gives

$$P(M_1\mid h_{T+1}^a)=\frac{{\pi }_{1}L(h_{T+1}^a)}{{\pi }_{0}L(h_{T+1}^a)+{\pi }_{1}L(h_{T+1}^a)}=\frac{{\pi }_1}{{\pi }_0+{\pi }_1}={\pi }_1$$

Thus, observing additional actions cannot update the observer’s posterior odds between the two observationally equivalent models. $\square$

Remark 4 (Interpretation). The theorem identifies a structural confounding between perceptual bias and the unknown environment:

$$\text{biased perception in environment }\mathbf{\mu }{\equiv }_{\mathrm{actions}}\text{unbiased perception in environment }\mathbf{\nu }$$

The observer cannot determine whether the user’s behavior is generated by corrupted observations in one environment or objective observations in another environment.

Remark 5 (Scope of the impossibility result). The theorem does not claim that every biased agent is observationally equivalent to every unbiased agent. It establishes that the two model classes overlap in the space of observable action-process distributions. This overlap is sufficient to rule out uniform identification over the complete model classes.

Remark 6 (Role of the unknown environment). The construction relies on the fact that the true arm means are unknown to the observer and may differ under the two hypotheses. If the true environment were known and fixed under both hypotheses, this particular observational equivalence would no longer apply, and action-based identification could become possible.

Remark 7 (Independence from the confirmation-trap assumptions). Theorem 2 is independent of Assumptions 1 and 2. It is an information-theoretic result based on observational equivalence, rather than a result about the specific dynamics of persistent confirmation bias. A perceptual channel depending on the current subjective expectation may induce a history-dependent effective environment and is therefore not necessarily covered by the present construction.

Remark 8 (Positive perceptual distortion as a special case). A particularly relevant special case is

$$u=1,v\in (0,1]$$

under which positive rewards are always retained and negative rewards are transformed into positive perceived rewards with probability $v$. The effective means are then

$${\nu }_k={\mu }_k+v(1-{\mu }_k)$$

Remark 9 (Approximate observational equivalence). More generally, for any biased and unbiased models with action distributions $P_1^{a,T}$ and $P_0^{a,T}$, the minimum testing error under equal prior probabilities satisfies

$$\underset{{\hat{z}}_T}{\inf }\frac{1}{2}\left[P_0^{a,T}({\hat{z}}_T=1)+P_1^{a,T}({\hat{z}}_T=0)\right]=\frac{1}{2}\left(1-{\Vert P_0^{a,T}-P_1^{a,T}\Vert }_{\mathrm{TV}}\right)$$

Thus, action-only identification remains difficult whenever the induced action distributions are close in total variation and becomes impossible when they are identical.

3. Active Interventions and Identification

We now allow the Observer to modify the reward-generating process. The objective is to break the observational equivalence established in Theorem 2 by exposing the two user types to an observation whose treatment differs under objective and biased perception.

Active Identification from one User

Adversarial Zero-Reward Intervention

Definition 2 (Adversarial zero-reward intervention). At round $t$, the user first selects an action $a_t$. After observing $a_t$ but before the reward is delivered, the Observer chooses an intervention variable

$$I_t\in \{0,1\}$$

Let $R_t\sim \mathrm{Bernoulli}({\mu }_{a_t})$ denote the natural reward generated by the environment. The delivered objective reward is

$$r_t=(1-I_t)R_t$$

Equivalently,

$$\mathcal{L}(r_t\mid a_t,I_t,\mathbf{\mu })=(1-I_t)\mathrm{Bernoulli}({\mu }_{a_t})+I_t{\delta }_0$$

When $I_t=1$, the Observer pays a cost $c>0$ and deterministically replaces the natural reward by $r_t=0$. The cumulative intervention cost through time $T$ is

$$C_T=c\sum _{t=1}^T{I}_t$$

Under the unbiased model $M_0$, the delivered reward $r_t$ is observed directly and used in the Bayesian update. Under the biased model $M_1$, it passes through the perceptual distortion channel:

$${\tilde{r}}_t\sim P_{\mathrm{bias}}\left(\cdot \mid r_t,{\tilde{\mu }}_{a_t}^{(t-1)}\right)$$

The Observer continues to observe only the action history and its own intervention decisions. It observes neither the delivered reward as internally represented by the user nor the subjective reward ${\tilde{r}}_t$.

Definition 3 (Controlled intervention block). A controlled zero-reward intervention block of length $m$ on arm $k$, beginning at time $\tau$, is an experimental block satisfying

$$a_{\tau }=\cdots =a_{\tau +m-1}=k$$

and

$$I_{\tau }=\cdots =I_{\tau +m-1}=1$$

Thus, the user receives $m$ consecutive objective failures on arm $k$.

The controlled-pull condition is an additional experimental condition. The intervention variable $I_t$ alone controls the reward but does not force the action. If the Observer cannot request repeated pulls of arm $k$, the operational object of identification is the entire switching trajectory rather than only the action following a fixed block (check the following corollary).

Theorem 3 (Active identification from a controlled zero-reward block). Fix an arm $k$. Suppose that immediately before the intervention block, the two candidate models (biased and uubiased) have the same independent subjective posteriors

$${\mu }_k\mid {\mathcal{F}}_{\tau }\sim \mathrm{Beta}(A,B)$$

and

$${\mu }_j\mid {\mathcal{F}}_{\tau }\sim \mathrm{Beta}(A_j,B_j),j\ne k$$

where all parameters are strictly positive.

Suppose that the experimental protocol supplies a controlled intervention block of length $m$ on arm $k$. Let $Q_z^{(m)}$ denote the distribution of the next Thompson Sampling action $a_{\tau +m}$ under type $z$, conditional on the initial posterior state and the controlled-pull design. Under $M_1$, this distribution marginalizes over the latent perceived rewards generated during the intervention block.

Define

$${\epsilon }_{\infty }(A,B):=C{B}^p\sum _{\ell =0}^{\infty }(A+B+\ell {)}^{-p}$$

Suppose that Assumption 2 holds and that, for a desired error level $\delta \in (0,1)$,

$${\epsilon }_{\infty }(A,B)\le \frac{\delta }{6}$$

Then there exists a finite intervention length $m_{\delta }$ such that, for every $m\ge m_{\delta }$,

$${\Vert Q_1^{(m)}-Q_0^{(m)}\Vert }_{\mathrm{TV}}>1-\delta$$

Consequently, the test

$$\hat{z}=1\{a_{\tau +m}=k\}$$

distinguishes the biased and unbiased models with arbitrarily small error, provided that the pre-intervention posterior state is sufficiently confirming and that the intervention block is sufficiently long. The total intervention cost is

$$c{m}_{\delta }$$

A computable value of $m_{\delta }$ can be obtained as follows. Let $G_j$ denote the cumulative distribution function of the fixed Thompson sample from competitor $j\ne k$, and set

$$\xi :=\frac{\delta }{6}$$

Choose a competitor $j_0\ne k$ and thresholds $x,y\in (0,1)$ satisfying

$$G_{j_0}(x)\le \xi$$

and

$$\sum _{j\ne k}\left[1-G_j(1-y)\right]\le \xi$$

Define

$$D_a(s):=\max \{1,s^{a-1}\}$$

and

$$L_0(m;x):=D_A(x)\frac{\Gamma (A+B+m)}{\Gamma (A)\Gamma (B+m+1)}(1-x{)}^{B+m}$$

as well as

$$L_1(m;y):=D_B(y)\frac{\Gamma (A+B+m)}{\Gamma (B)\Gamma (A+m+1)}(1-y{)}^{A+m}$$

Then one may take

$$m_{\delta }:=\min \left\{m\ge 1:L_0(m;x)\le \xi ,L_1(m;y)\le \xi \right\}$$

Proof in last section $■$

Remark 10 (Meaning of a sufficiently confirming posterior). The relevant condition is stronger than requiring the posterior mean $A/(A+B)$ to be close to one. The required condition is the summability bound

$$C{B}^p\sum _{\ell =0}^{\infty }(A+B+\ell {)}^{-p}\le \frac{\delta }{6}$$

If $B$ remains fixed while $A\to \infty$, then

$${\epsilon }_{\infty }(A,B)\le C{B}^p\left[(A+B{)}^{-p}+\frac{(A+B{)}^{1-p}}{p-1}\right]⟶0$$

The exponent condition $p>1$ is essential because it makes the probability of a perceived failure summable along the fully confirming trajectory.

Remark 11 (Posterior mean versus posterior tail). After $m$ objective failures, the unbiased posterior mean is

$${\mathbb{E}}_{M_0}[{\mu }_k\mid {\mathcal{F}}_{\tau +m}]=\frac{A}{A+B+m}$$

This quantity converges to zero algebraically rather than exponentially. What decreases exponentially, up to a polynomial prefactor, is the posterior probability that ${\mu }_k$ exceeds any fixed positive threshold. This posterior-tail decay produces the separation in Thompson Sampling action probabilities.

Remark 12 (Role of Assumption 1). Assumption 1 is not required for Theorem 3. The active-identification result is driven by the quantitative summability property in Assumption 2.

Remark 13 (Reward control does not imply action control). The binary intervention $I_t$ allows the Observer to replace the reward after an action has been selected. It does not allow the Observer to force $a_t=k$. Therefore, Theorem 3 applies directly when the experimental interface can request repeated evaluations of arm $k$. In a strictly autonomous bandit, switching away from $k$ must itself be treated as observable evidence.

Corollary 2 (Reward-only sequential identification). Suppose that the Observer cannot force actions and uses the policy

$$I_s=1\{a_s=k\}$$

during a diagnostic window beginning at time $\tau$. Define the no-switch event

$$S_m:=\bigcap _{\ell =0}^{m-1}\{a_{\tau +\ell }=k\}$$

Let

$$q_{1,\ell }(k):=q_k\left(\mathrm{Beta}(A+\ell ,B),b_{-k}\right)$$

denote the Thompson Sampling probability of choosing arm $k$ after $\ell$ perceived successes, with the competitor posteriors held fixed. If

$${\epsilon }_{\infty }(A,B)+\sum _{\ell =0}^{\infty }\left[1-q_{1,\ell }(k)\right]\le \epsilon$$

then

$$P_{M_1}(S_m)\ge 1-\epsilon$$

Under $M_0$, define

$$q_{0,\ell }(k):=q_k\left(\mathrm{Beta}(A,B+\ell ),b_{-k}\right)$$

Then

$$P_{M_0}(S_m)=\prod _{\ell =0}^{m-1}{q}_{0,\ell }(k)⟶0$$

Consequently,

$${\Vert P_{M_1}^{a,m}-P_{M_0}^{a,m}\Vert }_{\mathrm{TV}}\ge P_{M_1}(S_m)-P_{M_0}(S_m)$$

and the action-path distributions become arbitrarily well separated whenever the confirming-path escape probabilities are summable.

Proof. The result follows from a sequential union bound over perceived failures and Thompson Sampling deviations under $M_1$. Under $M_0$, conditional on the no-switch path, arm $k$ accumulates deterministic failures, giving the displayed product representation. The factors $q_{0,\ell }(k)$ converge to zero, so the product converges to zero. $\square$

Passive Identification from a User Population

We now consider a population of users interacting independently with the same objective environment. Population data impose a common-world restriction that is absent from the single-user equivalence construction of Theorem 2.

Hierarchical Multi-User Model

Definition 4 (Hierarchical multi-user model). Let $N$ users interact independently with the same Bernoulli environment

$$\mathbf{\mu }=({\mu }_1,\dots ,{\mu }_K)\in [0,1{]}^K$$

Each user $i\in \{1,\dots ,N\}$ has a latent type

$$z_i\stackrel{i.i.d.}{\sim }\mathrm{Bernoulli}(1-\eta )$$

where

$$P(z_i=0)=\eta ,P(z_i=1)=1-\eta$$

and $\eta \in (0,1)$. Conditional on $(\mathbf{\mu },z_1,\dots ,z_N)$, users have independent objective rewards, subjective perceptions, and Thompson Sampling randomizations.

All users start from the same known independent Beta prior

$$b_0(\mathbf{\theta })=\prod _{k=1}^K\mathrm{Beta}({\alpha }_k,{\beta }_k)$$

where

$${\alpha }_k>0,{\beta }_k>0$$

Biased users satisfy the known static perceptual channel of Assumption 3. Their effective arm means are therefore

$${\nu }_k=v+(u-v){\mu }_k$$

The Observer observes the batch action history

$$H_T^{\mathrm{batch}}:={\left\{h_{i,T}^a\right\}}_{i=1}^N$$

where

$$h_{i,T}^a=(a_{i,1},\dots ,a_{i,T})$$

For $z\in \{0,1\}$, let $P_{z,\mathbf{\mu }}^{a,T}$ denote the action-history law of a type-$z$ user in the common objective environment $\mathbf{\mu }$. The marginal action law of a randomly sampled user is

$$Q_{\mathbf{\mu }}^{a,T}:=\eta P_{0,\mathbf{\mu }}^{a,T}+(1-\eta )P_{1,\mathbf{\mu }}^{a,T}$$

Theorem 4 (Batch identification of the common environment and conditional identification of user types). Consider the hierarchical multi-user model of Definition 4. Suppose that $\eta$, $u$, $v$, and the common initial prior are known to the Observer. Define

$$\lambda :=\eta +(1-\eta )(u-v)$$

and suppose that

$$\lambda \ne 0$$

Then, for every $T\ge 2$, there exists an estimator

$${\hat{\mathbf{\mu }}}_N={\hat{\mathbf{\mu }}}_N\left(H_T^{\mathrm{batch}}\right)$$

such that

$${\hat{\mathbf{\mu }}}_N⟶\mathbf{\mu }$$

almost surely as $N\to \infty$.

Consequently, the common environment is identifiable from the batch action law. If the Observer places a prior on $[0,1{]}^K$ having positive density in a neighborhood of the true parameter, then for every $\epsilon >0$,

$$\Pi \left(\Vert \mathbf{\theta }-\mathbf{\mu }\Vert >\epsilon \mid H_T^{\mathrm{batch}}\right)⟶0$$

almost surely as $N\to \infty$.

Fix a user $i$. Suppose additionally that, under the true environment, the two type-specific infinite action laws are mutually singular:

$$P_{0,\mathbf{\mu }}^{a,\infty }\perp P_{1,\mathbf{\mu }}^{a,\infty }$$

Then

$$P\left(z_i=z_i^{\mathrm{true}}\mid h_{i,T}^a,\mathbf{\mu }\right)⟶1$$

almost surely as $T\to \infty$. Consequently, under the sequential limit $N\to \infty$ followed by $T\to \infty$,

$$P\left(z_i=z_i^{\mathrm{true}}\mid H_T^{\mathrm{batch}}\right)⟶1$$

almost surely.

Proof in last section $■$

Remark 14 (Two actions per user suffice for world identification). The proof constructs a strongly consistent estimator of each ${\mu }_k$ using only the empirical transition probability

$$P(a_{i,2}=k\mid a_{i,1}=k)$$

Thus, under the stated known-channel assumptions, $N\to \infty$ with $T\ge 2$ already identifies the common environment.

Remark 15 (Why batch data break the single-user confounding). For one biased user, Theorem 2 gives the equivalence

$$M_1\text{ in environment }\mathbf{\mu }{\equiv }_{\mathrm{actions}}{M}_0\text{ in environment }\mathbf{\nu }$$

In the hierarchical model, however, both types must share the same objective environment $\mathbf{\mu }$. The population law is constrained to be

$$Q_{\mathbf{\mu }}^{a,T}=\eta P_{0,\mathbf{\mu }}^{a,T}+(1-\eta )P_{1,\mathbf{\mu }}^{a,T}$$

When $\eta$, $u$, and $v$ are known and $\lambda \ne 0$, this common-world mixture is injective in $\mathbf{\mu }$.

Remark 16 (Convergence to the optimal arm is insufficient). If $u>v$, the transformation

$${\nu }_k=v+(u-v){\mu }_k$$

is strictly increasing. Therefore,

$$\arg \underset{k}{\max }{\nu }_k=\arg \underset{k}{\max }{\mu }_k$$

Under a unique optimum, both user types may satisfy

$$\frac{N_{i,k^{\star }}(T)}{T}⟶1$$

Hence, limiting action frequencies reveal only the common optimal arm and do not necessarily identify the user type. Individual type consistency requires mutual singularity or another explicit path-separation condition.

Remark 17 (A sufficient path-separation statistic). A sufficient condition for mutual singularity is the existence of an action-history statistic $S_T$ and distinct constants $s_0(\mathbf{\mu })$ and $s_1(\mathbf{\mu })$ such that

$$S_T⟶s_z(\mathbf{\mu })$$

almost surely under $P_{z,\mathbf{\mu }}^{a,\infty }$. One possible candidate is the vector of logarithmic exploration rates. If

$$\frac{N_{i,j}(T)}{\log T}⟶c_{z,j}$$

for every suboptimal arm $j$, and if

$$(c_{0,j}{)}_{j\ne k^{\star }}\ne (c_{1,j}{)}_{j\ne k^{\star }}$$

then the two type-specific action laws are mutually singular.

Remark 18 (Failure of automatic type identification). Consider the non-trivial channel

$$u=0.8,v=0.2$$

and the environment

$${\mu }_1=\cdots ={\mu }_K=\frac{1}{2}$$

Then

$${\nu }_k=0.2+0.6\left(\frac{1}{2}\right)=\frac{1}{2}={\mu }_k$$

for every arm. Therefore,

$$P_{0,\mathbf{\mu }}^{a,T}=P_{1,\mathbf{\mu }}^{a,T}$$

for every $T$. Even if the common environment is known exactly, the action history cannot identify an individual user’s type.

Remark 19 (Unknown hierarchical parameters). If $\eta$, $u$, or $v$ are unknown, the affine inversion used in Theorem 4 is no longer directly available. Additional normalization conditions, labeled users, repeated environments, or interventions may then be required.

The Cost of Truth: Hybrid Observation

Population data reduce uncertainty about the common environment, while active interventions provide individual evidence when passive action histories remain ambiguous. We now formalize an adaptive policy combining these two information sources.

Hybrid Observer Policy

For a type-$z$ user, define the action-history likelihood

$$p_{z,\mathbf{\theta }}^T(h):=P_{z,\mathbf{\theta }}^{a,T}(h)$$

The Observer maintains the joint posterior

$${\Pi }_N(d\mathbf{\theta },\mathbf{z}\mid H_T^{\mathrm{batch}})\propto \pi (d\mathbf{\theta })\prod _{i=1}^N\left[{\eta }^{1-z_i}(1-\eta {)}^{z_i}{p}_{z_i,\mathbf{\theta }}^T(h_{i,T}^a)\right]$$

For a user with action history $h$, define the type log-posterior odds at environment parameter $\mathbf{\theta }$ by

$${\Lambda }_T(h;\mathbf{\theta }):=\log \frac{(1-\eta )p_{1,\mathbf{\theta }}^T(h)}{\eta p_{0,\mathbf{\theta }}^T(h)}$$

Definition 5 (Hybrid observer policy). Let $U_N$ be a posterior confidence set for the common environment. The Observer classifies user $i$ passively if the sign of

$${\Lambda }_T(h_{i,T}^a;\mathbf{\theta })$$

is constant over all $\mathbf{\theta }\in U_N$ and its absolute value exceeds the desired confidence threshold uniformly over $U_N$. If either condition fails, the Observer applies the active zero-reward experiment of Theorem 3.

The policy therefore intervenes only when the user’s passive classification is not robust to the remaining uncertainty about the common environment.

Theoretical Analysis: Intervention Cost Decay

Theorem 5 (Hybrid identification and vanishing average intervention cost). Suppose that the Observer manages $N$ users, each observed for $T_N$ passive rounds. Fix a target joint error probability $\delta \in (0,1)$ and define

$${\epsilon }_N:=\frac{\delta }{2N}$$

and

$$a_N:=\log \frac{1-{\epsilon }_N}{{\epsilon }_N}$$

Suppose that the following conditions hold.

First, there exists a random confidence set $U_N$ such that

$$P_{\mathbf{\mu }}(\mathbf{\mu }\notin U_N)\le {\kappa }_N$$

and, on the event $\{\mathbf{\mu }\in U_N\}$,

$$\underset{\mathbf{\theta }\in U_N}{\sup }\Vert \mathbf{\theta }-\mathbf{\mu }\Vert \le r_N$$

where

$${\kappa }_N⟶0,r_N⟶0$$

Second, the type log-likelihood ratio is locally stable in the environment parameter:

$$\left|{\Lambda }_{T_N}(h;\mathbf{\theta })-{\Lambda }_{T_N}(h;\mathbf{\mu })\right|\le L_{T_N}\Vert \mathbf{\theta }-\mathbf{\mu }\Vert$$

Third, define the oracle passive-ambiguity probability

$$q_{T_N}({\epsilon }_N):=P_{\mathbf{\mu }}\left(\left|{\Lambda }_{T_N}(h_{i,T_N}^a;\mathbf{\mu })\right|\le a_N\right)$$

Suppose that

$$q_{T_N}({\epsilon }_N)⟶0$$

Fourth, suppose that there exist constants $A>0$ and $\alpha >0$ such that, for every sufficiently small $x>0$,

$$P_{\mathbf{\mu }}\left(a_N<\left|{\Lambda }_{T_N}(h_{i,T_N}^a;\mathbf{\mu })\right|\le a_N+x\right)\le A{x}^{\alpha }$$

Finally, suppose that every passively ambiguous user satisfying the preconditions of Theorem 3 can be actively classified with error at most ${\epsilon }_N$ using at most

$$m_N:=m({\epsilon }_N)$$

zero-reward interventions.

Let $C_N$ denote the total intervention cost of the hybrid policy. Then

$$P(\hat{\mathbf{z}}\ne \mathbf{z})\le {\kappa }_N+\frac{\delta }{2}$$

and

$$\frac{\mathbb{E}[C_N]}{N}\le c{m}_N\left[q_{T_N}({\epsilon }_N)+A(L_{T_N}{r}_N{)}^{\alpha }+{\kappa }_N\right]$$

Consequently, if

$$m_N{q}_{T_N}({\epsilon }_N)⟶0$$ $$m_N(L_{T_N}{r}_N{)}^{\alpha }⟶0$$

and

$$m_N{\kappa }_N⟶0$$

then

$$\frac{\mathbb{E}[C_N]}{N}⟶0$$

Moreover, the fraction of users requiring at least one active intervention converges to zero in probability.

Proof in last section $■$

Corollary 3 (Representative parametric rate). Suppose that the common-environment posterior satisfies

$$r_N=O\left(\sqrt{\frac{\log N}{N}}\right)$$

and suppose that

$$m_N=O(\log N)$$ $$T_N=O(\log N)$$ $$L_{T_N}=O(T_N)$$

If there exists $b>0$ such that

$$q_{T_N}({\epsilon }_N)+{\kappa }_N=O(N^{-b})$$

then

$$\frac{\mathbb{E}[C_N]}{N}=O\left(c\log N\left[N^{-b}+{\left(\frac{(\log N{)}^{3/2}}{\sqrt{N}}\right)}^{\alpha }\right]\right)$$

and therefore

$$\frac{\mathbb{E}[C_N]}{N}⟶0$$

Proof. Under the stated rates,

$$L_{T_N}{r}_N=O\left(\frac{(\log N{)}^{3/2}}{\sqrt{N}}\right)$$

Substitution into Theorem 5 gives the claimed bound. $\square$

Remark 20 (What population growth removes). The cost bound separates two sources of ambiguity:

$$\text{passive individual ambiguity}+\text{global environment uncertainty}$$

The global term

$$A(L_{T_N}{r}_N{)}^{\alpha }$$

vanishes because the population posterior concentrates around the common environment. The individual term

$$q_{T_N}({\epsilon }_N)$$

vanishes only when each user’s passive history becomes sufficiently informative as $T_N\to \infty$.

Remark 21 (The number of interventions is integer-valued). It is not mathematically meaningful to claim that the intervention count of every user decreases continuously to zero. The rigorous conclusion is that the fraction of users receiving any intervention and the expected intervention cost per user converge to zero.

Remark 22 (Strict monotonicity is not automatic). The actual sequence

$$\frac{\mathbb{E}[C_N]}{N}$$

need not be strictly decreasing for every integer $N$. Intervention counts are discrete, posterior confidence sets can fluctuate, and the joint-confidence requirement makes the individual error threshold ${\epsilon }_N$ smaller as $N$ grows. The theorem establishes a vanishing and eventually decreasing upper envelope under the stated rate conditions.

Remark 23 (Why population growth alone is insufficient). Suppose that

$$u=0.8,v=0.2$$

and

$${\mu }_1=\cdots ={\mu }_K=\frac{1}{2}$$

Then the two type-specific action laws are identical. If $\eta =1/2$, an untreated user’s type remains a fair coin even when $\mathbf{\mu }$ is known exactly. If $M_N$ users receive no additional identifying information, the probability of correctly recovering all their types is at most

$$2^{-M_N}$$

Therefore, fixed joint confidence requires active information for all but a bounded number of users. In this case, the intervention cost per user does not vanish. Passive type separation is therefore necessary for the conclusion of Theorem 5.

4. Proofs

Theorem 1 (Positive-probability confirmation trap).

Proof. Let

$${\mathcal{E}}_{k,n}:=\bigcap _{t=1}^n\{a_t=k,{\tilde{r}}_t=1\},{\mathcal{E}}_{k,0}:=\Omega$$

The events form a decreasing sequence and satisfy

$${\mathcal{E}}_k=\bigcap _{n=0}^{\infty }{\mathcal{E}}_{k,n}$$

Conditional on ${\mathcal{E}}_{k,n}$, arm $k$ has been selected $n$ times and all its subjectively perceived rewards have been equal to one. By Beta—Bernoulli conjugacy, its subjective posterior is therefore

$${\mu }_k\mid {\mathcal{E}}_{k,n}\sim \mathrm{Beta}({\alpha }_k+n,{\beta }_k)$$

Because no competing arm has been selected on ${\mathcal{E}}_{k,n}$, the posterior of every arm $j\ne k$ remains equal to its prior:

$${\mu }_j\mid {\mathcal{E}}_{k,n}\sim \mathrm{Beta}({\alpha }_j,{\beta }_j),j\ne k$$

In particular, the posterior mean of arm $k$ on this history is

$$m_n:={\tilde{\mu }}_k^{(n)}=\frac{{\alpha }_k+n}{{\alpha }_k+{\beta }_k+n}$$

and hence

$$1-m_n=\frac{{\beta }_k}{{\alpha }_k+{\beta }_k+n}$$

We first bound the probability of a contradictory subjective perception. Define

$$u_n:=P({\tilde{r}}_{n+1}=0\mid {\mathcal{E}}_{k,n},a_{n+1}=k)$$

Conditional on selecting arm $k$, the objective reward is distributed as $\mathrm{Bernoulli}({\mu }_k)$. Therefore,

$$u_n={\mu }_k{P}_{\mathrm{bias}}(\tilde{r}=0\mid r=1,m_n)+(1-{\mu }_k)P_{\mathrm{bias}}(\tilde{r}=0\mid r=0,m_n)$$

By Assumption 2, the first term is zero and the second term is bounded by $C(1-m_n{)}^p$. Thus,

$$u_n\le (1-{\mu }_k)C(1-m_n{)}^p=(1-{\mu }_k)C{\left(\frac{{\beta }_k}{{\alpha }_k+{\beta }_k+n}\right)}^p$$

Consequently, there exists a finite constant $A_k>0$ such that

$$u_n\le A_k(n+1{)}^{-p}$$

Since $p>1$, it follows that

$$\sum _{n=0}^{\infty }{u}_n<\infty$$

Moreover, every factor $1-u_n$ is strictly positive. Indeed, if $r=1$, Assumption 2 implies $\tilde{r}=1$ almost surely. If $r=0$, then $m_n>0$ and Assumption 1 gives

$$P_{\mathrm{bias}}(\tilde{r}=1\mid r=0,m_n)=\mathbb{E}[\tilde{r}\mid r=0,m_n]\ge \gamma m_n>0$$

It follows that

$$1-u_n\ge {\mu }_k+(1-{\mu }_k)\gamma m_n>0$$

We next bound the probability that Thompson Sampling abandons arm $k$. Let

$$X_n\sim \mathrm{Beta}({\alpha }_k+n,{\beta }_k)$$

denote the Thompson sample for arm $k$, and let

$$Y_j\sim \mathrm{Beta}({\alpha }_j,{\beta }_j),j\ne k$$

denote the independent Thompson samples of the competing arms. Define the conditional escape probability

$$q_n:=P(a_{n+1}\ne k\mid {\mathcal{E}}_{k,n})=P\left(\underset{j\ne k}{\max }{Y}_j>X_n\right)$$

For each $j\ne k$, there exists a finite constant $D_j>0$ such that the upper tail of the Beta distribution satisfies

$$P(Y_j>x)\le D_j(1-x{)}^{{\beta }_j},x\in [0,1]$$

To verify this bound, for $x\ge 1/2$ we have

$$P(Y_j>x)=\frac{1}{B({\alpha }_j,{\beta }_j)}{\int }_x^1{y}^{{\alpha }_j-1}(1-y{)}^{{\beta }_j-1}dy\le \frac{M_j}{{\beta }_{j}B({\alpha }_j,{\beta }_j)}(1-x{)}^{{\beta }_j}$$

where $M_j:={\sup }_{y\in [1/2,1]}{y}^{{\alpha }_j-1}<\infty$. For $x<1/2$, the same inequality holds after increasing the constant, since

$$P(Y_j>x)\le 1\le 2^{{\beta }_j}(1-x{)}^{{\beta }_j}$$

Using the union bound and conditioning on $X_n$, we obtain

$$q_n\le \sum _{j\ne k}P(Y_j>X_n)\le \sum _{j\ne k}{D}_j\mathbb{E}[(1-X_n{)}^{{\beta }_j}]$$

The relevant Beta moment is

$$\mathbb{E}[(1-X_n{)}^{{\beta }_j}]=\frac{B({\alpha }_k+n,{\beta }_k+{\beta }_j)}{B({\alpha }_k+n,{\beta }_k)}$$

Using the definition of the Beta function,

$$\mathbb{E}[(1-X_n{)}^{{\beta }_j}]=\frac{\Gamma ({\beta }_k+{\beta }_j)}{\Gamma ({\beta }_k)}\frac{\Gamma ({\alpha }_k+{\beta }_k+n)}{\Gamma ({\alpha }_k+{\beta }_k+{\beta }_j+n)}$$

The standard Gamma-ratio asymptotic gives

$$\frac{\Gamma ({\alpha }_k+{\beta }_k+n)}{\Gamma ({\alpha }_k+{\beta }_k+{\beta }_j+n)}=O(n^{-{\beta }_j})$$

Hence, for each $j\ne k$, there exists a finite constant $G_j>0$ such that

$$\mathbb{E}[(1-X_n{)}^{{\beta }_j}]\le G_j(n+1{)}^{-{\beta }_j}$$

It follows that there exists a finite constant $G>0$ such that

$$q_n\le G(n+1{)}^{-{\beta }_{\min }^{(-k)}}$$

Because ${\beta }_{\min }^{(-k)}>1$, we obtain

$$\sum _{n=0}^{\infty }{q}_n<\infty$$

Furthermore, $q_n<1$ for every finite $n$, because all proper Beta distributions have positive density on $(0,1)$ and hence

$$P\left(X_n>\underset{j\ne k}{\max }{Y}_j\right)>0$$

By the chain rule of conditional probability,

$$P({\mathcal{E}}_{k,n+1}\mid {\mathcal{E}}_{k,n})=(1-q_n)(1-u_n)$$

Therefore, for every $N\ge 1$,

$$P({\mathcal{E}}_{k,N})=\prod _{n=0}^{N-1}(1-q_n)(1-u_n)$$

Since ${\sum }_n{q}_n<\infty$ and ${\sum }_n{u}_n<\infty$, there exists $N_0$ such that $q_n\le 1/2$ and $u_n\le 1/2$ for all $n\ge N_0$. Using $\log (1-x)\ge -2x$ for $x\in [0,1/2]$, we have

$$\sum _{n=N_0}^{\infty }\log ((1-q_n)(1-u_n))\ge -2\sum _{n=N_0}^{\infty }(q_n+u_n)>-\infty$$

The finitely many factors preceding $N_0$ are strictly positive. Consequently,

$$\prod _{n=0}^{\infty }(1-q_n)(1-u_n)>0$$

By continuity of probability for decreasing events,

$${\rho }_k:=P({\mathcal{E}}_k)=\underset{N\to \infty }{\lim }P({\mathcal{E}}_{k,N})=\prod _{n=0}^{\infty }(1-q_n)(1-u_n)>0$$

Since ${\mathcal{E}}_k\subseteq {\bigcap }_{t=1}^{\infty }\{a_t=k\}$, this proves

$$P(a_t=k\text{ for every }t\ge 1)\ge {\rho }_k>0$$

On ${\mathcal{E}}_k$, the posterior mean of arm $k$ satisfies

$${\tilde{\mu }}_k^{(n)}=\frac{{\alpha }_k+n}{{\alpha }_k+{\beta }_k+n}⟶1$$

Moreover,

$$P(a_{n+1}=k\mid {\mathcal{E}}_{k,n})=1-q_n⟶1$$

Thus, the subjective evidence becomes increasingly favorable to arm $k$, while the probability of exploring another arm vanishes.

Finally, define the pseudo-regret by

$$R_T:=\sum _{t=1}^T({\mu }^{\star }-{\mu }_{a_t})$$

On ${\mathcal{E}}_k$, the agent selects arm $k$ at every time step, so

$$R_T={\Delta }_{k}T$$

Since pseudo-regret is nonnegative outside ${\mathcal{E}}_k$,

$$\mathbb{E}[R_T]\ge P({\mathcal{E}}_k){\Delta }_{k}T={\rho }_k{\Delta }_{k}T$$

Therefore, the confirmation trap occurs with strictly positive probability and produces linear expected pseudo-regret. $\square$

Theorem 2 (Finite-Horizon Indistinguishability / Local Non-Identifiability)

Proof. Let

$$G_t^1:=\{(a_s,{\tilde{r}}_s){\}}_{s=1}^{t-1}$$

denote the recorded history of the biased agent, and let

$$G_t^0:=\{(a_s,r_s^0){\}}_{s=1}^{t-1}$$

denote the objective history of the unbiased agent, where $r_s^0$ denotes the reward observed under the effective environment $\mathbf{\nu }$.

Consider the biased model $M_1$. Conditional on any recorded history $G_t^1=g_t$ and on selecting arm $k$, the objective reward remains distributed according to the stationary Bernoulli environment:

$$P_{M_1}(r_t=1\mid G_t^1=g_t,a_t=k)={\mu }_k$$

Using the memoryless property of the perceptual channel and the law of total probability, we obtain

$$P_{M_1}({\tilde{r}}_t=1\mid G_t^1=g_t,a_t=k)=u{\mu }_k+v(1-{\mu }_k)={\nu }_k$$

Therefore,

$${\tilde{r}}_t\mid (G_t^1=g_t,a_t=k)\sim \mathrm{Bernoulli}({\nu }_k)$$

Under the unbiased model $M_0$, arm $k$ has objective mean ${\nu }_k$. Hence,

$$r_t^0\mid (G_t^0=g_t,a_t=k)\sim \mathrm{Bernoulli}({\nu }_k)$$

Thus, conditional on the same recorded history and selected action, the next recorded observation has the same distribution under both models:

$$P_{M_1}({\tilde{r}}_t=y\mid G_t^1=g_t,a_t=k)=P_{M_0}(r_t^0=y\mid G_t^0=g_t,a_t=k)$$

for every $y\in \{0,1\}$.

We now prove by induction that the recorded-history processes $(G_t^1{)}_{t\ge 1}$ and $(G_t^0{)}_{t\ge 1}$ have the same distribution. At $t=1$, both histories are empty. Since the two agents have the same initial prior and use the same Thompson Sampling and tie-breaking rules, their first actions have the same distribution:

$$P_{M_1}(a_1=k)=P_{M_0}(a_1=k)$$

for every arm $k$.

Suppose that $G_t^1$ and $G_t^0$ have the same distribution for some $t\ge 1$. Conditional on any common realization

$$g_t=\{(k_s,y_s){\}}_{s=1}^{t-1}$$

both agents have updated the same initial prior using the same sequence of recorded action—reward pairs and the same Bernoulli likelihood. Their posterior distributions are therefore identical.

Because both agents apply the same Thompson Sampling rule to these identical posteriors, their conditional action probabilities coincide:

$$P_{M_1}(a_t=k\mid G_t^1=g_t)=P_{M_0}(a_t=k\mid G_t^0=g_t)$$

for every arm $k$.

Conditional on the selected action, the distributions of their next recorded observations also coincide:

$$P_{M_1}({\tilde{r}}_t=y\mid G_t^1=g_t,a_t=k)=P_{M_0}(r_t^0=y\mid G_t^0=g_t,a_t=k)$$

Consequently, for every possible extension $(k,y)$ of $g_t$,

$$P_{M_1}(G_{t+1}^1=g_t\cup \{(k,y)\})=P_{M_0}(G_{t+1}^0=g_t\cup \{(k,y)\})$$

It follows that $G_{t+1}^1$ and $G_{t+1}^0$ have the same distribution. By induction, the joint distributions of the recorded histories coincide at every horizon.

Marginalizing out the recorded rewards yields

$$P_{M_1}^{a,T}=P_{M_0}^{a,T}$$

for every $T\ge 1$. Hence, the biased agent in environment $\mathbf{\mu }$ and the unbiased agent in environment $\mathbf{\nu }$ are observationally equivalent from the perspective of an action-only observer.

It remains to establish the statistical lower bound. Let

$$Q_T:=P_{M_0}^{a,T}=P_{M_1}^{a,T}$$

denote their common action-history distribution, and define

$$q_T:=Q_T({\hat{z}}_T=1)$$

Under the unbiased model, the estimator’s probability of error is

$$P_{M_0}({\hat{z}}_T=1)=q_T$$

Under the biased model, its probability of error is

$$P_{M_1}({\hat{z}}_T=0)=1-q_T$$

Therefore,

$$P_{M_0}({\hat{z}}_T=1)+P_{M_1}({\hat{z}}_T=0)=1$$

Consequently,

$$\max \left\{P_{M_0}({\hat{z}}_T=1),P_{M_1}({\hat{z}}_T=0)\right\}\ge \frac{1}{2}$$

This bound holds for every estimator and every horizon $T$. Therefore, no sequence of action-only estimators can consistently distinguish the two models, and no action-only estimator can be uniformly consistent over model classes containing both models. $\square$

Theorem 3 (Active identification from a controlled zero-reward block)

Let

$$E_m:=\bigcap _{\ell =0}^{m-1}\{{\tilde{r}}_{\tau +\ell }=1\}$$

denote the event that the biased user transforms every injected objective failure into a perceived success.

Conditional on $E_{\ell }$, the biased posterior of arm $k$ after $\ell$ interventions is

$$\mathrm{Beta}(A+\ell ,B)$$

Its posterior mean is

$${\tilde{\mu }}_{k,\ell }=\frac{A+\ell }{A+B+\ell }$$

and hence

$$1-{\tilde{\mu }}_{k,\ell }=\frac{B}{A+B+\ell }$$

By Assumption 2,

$$P_{M_1}\left({\tilde{r}}_{\tau +\ell }=0\mid E_{\ell }\right)\le C{\left(\frac{B}{A+B+\ell }\right)}^p$$

Decomposing according to the first perceived failure and applying a union bound yields

$$P_{M_1}(E_m^c)\le C{B}^p\sum _{\ell =0}^{m-1}(A+B+\ell {)}^{-p}$$

Therefore,

$$P_{M_1}(E_m^c)\le {\epsilon }_{\infty }(A,B)$$

On $E_m$, the biased posterior of arm $k$ is

$$\mathrm{Beta}(A+m,B)$$

and its posterior mean is

$$\frac{A+m}{A+B+m}⟶1$$

Under $M_0$, every injected reward is observed as an objective failure. The posterior of arm $k$ is therefore

$$\mathrm{Beta}(A,B+m)$$

and its posterior mean is

$$\frac{A}{A+B+m}⟶0$$

Let

$$X_m\sim \mathrm{Beta}(A,B+m)$$

For a fixed threshold $x\in (0,1)$,

$$P(X_m>x)=\frac{1}{B(A,B+m)}{\int }_x^1{s}^{A-1}(1-s{)}^{B+m-1}ds$$

Since

$$s^{A-1}\le D_A(x)$$

on $[x,1]$, it follows that

$$P(X_m>x)\le D_A(x)\frac{\Gamma (A+B+m)}{\Gamma (A)\Gamma (B+m+1)}(1-x{)}^{B+m}$$

Thus,

$$P(X_m>x)\le L_0(m;x)$$

The Gamma-function ratio grows only polynomially in $m$, whereas $(1-x{)}^m$ decreases exponentially. Hence,

$$L_0(m;x)⟶0$$

Now let

$$X_m^{\prime }\sim \mathrm{Beta}(A+m,B)$$

Since $1-X_m^{\prime }$ has distribution $\mathrm{Beta}(B,A+m)$, the same calculation gives

$$P(X_m^{\prime }\le 1-y)\le L_1(m;y)$$

and

$$L_1(m;y)⟶0$$

Under $M_0$, if arm $k$ is selected at the diagnostic round, then either $X_m>x$ or the Thompson draw of competitor $j_0$ is at most $x$. Therefore,

$$Q_0^{(m)}(k)\le L_0(m;x)+G_{j_0}(x)$$

Conditional on $E_m$, arm $k$ is selected under $M_1$ whenever $X_m^{\prime }>1-y$ and every competitor draw is below $1-y$. Consequently,

$$Q_1^{(m)}(k\mid E_m)\ge 1-L_1(m;y)-\sum _{j\ne k}\left[1-G_j(1-y)\right]$$

After marginalizing over the latent perceived rewards,

$$Q_1^{(m)}(k)\ge 1-{\epsilon }_{\infty }(A,B)-L_1(m;y)-\sum _{j\ne k}\left[1-G_j(1-y)\right]$$

By construction,

$${\epsilon }_{\infty }(A,B)\le \xi$$ $$G_{j_0}(x)\le \xi$$ $$\sum _{j\ne k}\left[1-G_j(1-y)\right]\le \xi$$

For every $m\ge m_{\delta }$,

$$L_0(m;x)\le \xi$$

and

$$L_1(m;y)\le \xi$$

Therefore,

$$Q_1^{(m)}(k)-Q_0^{(m)}(k)\ge 1-5\xi$$

Since $\xi =\delta /6$,

$$1-5\xi =1-\frac{5\delta }{6}>1-\delta$$

Finally, total variation dominates the probability difference of every measurable event. In particular,

$${\Vert Q_1^{(m)}-Q_0^{(m)}\Vert }_{\mathrm{TV}}\ge \left|Q_1^{(m)}(k)-Q_0^{(m)}(k)\right|>1-\delta$$

This proves the theorem. $\square$

Theorem 4 (Batch identification of the common environment and conditional identification of user types).

Let

$$s_k:=P(a_{i,1}=k)$$

Because all users have the same initial prior and no reward has yet been observed, the first action is independent of the user type and the true environment. The Beta priors have full support, so

$$s_k>0$$

for every arm $k$.

Let $b_{k,1}$ denote the posterior obtained after one perceived success on arm $k$, and let $b_{k,0}$ denote the posterior obtained after one perceived failure. Define

$$q_{k,y}(\ell ):=P_{\mathbf{\theta }\sim b_{k,y}}\left(\ell =\arg \underset{j}{\max }{\theta }_j\right)$$

for $y\in \{0,1\}$. Set

$$d_k:=q_{k,1}(k)-q_{k,0}(k)$$

After a success, the marginal posterior of arm $k$ is

$$\mathrm{Beta}({\alpha }_k+1,{\beta }_k)$$

After a failure, it is

$$\mathrm{Beta}({\alpha }_k,{\beta }_k+1)$$

The success posterior strictly first-order stochastically dominates the failure posterior. Since the probability that arm $k$ wins the Thompson draw is strictly increasing in its sampled parameter,

$$d_k>0$$

For an unbiased user who selected arm $k$ at the first round, the first recorded signal is Bernoulli with mean ${\mu }_k$. For a biased user, the first perceived signal is Bernoulli with mean

$${\nu }_k=v+(u-v){\mu }_k$$

Since the first action is independent of the user type,

$$P(a_{i,2}=k\mid a_{i,1}=k)=q_{k,0}(k)+d_k{w}_k$$

where

$$w_k:=\eta {\mu }_k+(1-\eta ){\nu }_k$$

Substituting the expression for ${\nu }_k$ gives

$$w_k=\left[\eta +(1-\eta )(u-v)\right]{\mu }_k+(1-\eta )v$$

Therefore,

$$w_k=\lambda {\mu }_k+(1-\eta )v$$

Since $d_k>0$ and $\lambda \ne 0$,

$${\mu }_k=\frac{\frac{P(a_{i,2}=k\mid a_{i,1}=k)-q_{k,0}(k)}{d_k}-(1-\eta )v}{\lambda }$$

Define the empirical repeat probability

$${\hat{p}}_{k,N}:=\frac{{\sum }_{i=1}^{N}1\{a_{i,1}=k,a_{i,2}=k\}}{{\sum }_{i=1}^{N}1\{a_{i,1}=k\}}$$

By the strong law of large numbers,

$$\frac{1}{N}\sum _{i=1}^{N}1\{a_{i,1}=k\}⟶s_k$$

and

$$\frac{1}{N}\sum _{i=1}^{N}1\{a_{i,1}=k,a_{i,2}=k\}⟶s_{k}P(a_{i,2}=k\mid a_{i,1}=k)$$

almost surely. Hence,

$${\hat{p}}_{k,N}⟶P(a_{i,2}=k\mid a_{i,1}=k)$$

almost surely.

Define

$${\hat{\mu }}_{k,N}:=\frac{\frac{{\hat{p}}_{k,N}-q_{k,0}(k)}{d_k}-(1-\eta )v}{\lambda }$$

Then,

$${\hat{\mu }}_{k,N}⟶{\mu }_k$$

almost surely for every $k$. Therefore,

$${\hat{\mathbf{\mu }}}_N⟶\mathbf{\mu }$$

almost surely.

The two-action sample space is finite, and the mapping

$$\mathbf{\mu }\mapsto Q_{\mathbf{\mu }}^{a,2}$$

is continuous and injective. Compactness of $[0,1{]}^K$ implies positive Kullback—Leibler separation between the true parameter and every closed set not containing it. The strong law applied to the population likelihood therefore gives

$$\Pi \left(\Vert \mathbf{\theta }-\mathbf{\mu }\Vert >\epsilon \mid H_T^{\mathrm{batch}}\right)⟶0$$

almost surely for every $\epsilon >0$.

It remains to prove the individual type-identification statement. For a fixed user, define the likelihood ratio

$$L_T:=\frac{P_{1,\mathbf{\mu }}^{a,T}(h_{i,T}^a)}{P_{0,\mathbf{\mu }}^{a,T}(h_{i,T}^a)}$$

Bayes’ rule gives

$$P(z_i=1\mid h_{i,T}^a,\mathbf{\mu })=\frac{(1-\eta )L_T}{\eta +(1-\eta )L_T}$$

Under mutual singularity,

$$L_T⟶0$$

almost surely under $P_{0,\mathbf{\mu }}^{a,\infty }$, whereas

$$L_T⟶\infty$$

almost surely under $P_{1,\mathbf{\mu }}^{a,\infty }$. It follows that

$$P(z_i=z_i^{\mathrm{true}}\mid h_{i,T}^a,\mathbf{\mu })⟶1$$

almost surely.

The population posterior consistently identifies $\mathbf{\mu }$, after which the same likelihood-ratio argument applies to each user. This proves the sequential-limit statement and completes the proof. $\square$

Theorem 5 (Hybrid identification and vanishing average intervention cost).

Let $A_{i,N}$ denote the event that user $i$ is sent to active testing.

On the event $\{\mathbf{\mu }\in U_N\}$, the likelihood-stability condition gives

$$\underset{\mathbf{\theta }\in U_N}{\sup }\left|{\Lambda }_{T_N}(h_{i,T_N}^a;\mathbf{\theta })-{\Lambda }_{T_N}(h_{i,T_N}^a;\mathbf{\mu })\right|\le L_{T_N}{r}_N$$

Therefore, if

$$\left|{\Lambda }_{T_N}(h_{i,T_N}^a;\mathbf{\mu })\right|>a_N+L_{T_N}{r}_N$$

then the sign of the log-posterior odds is constant throughout $U_N$, and its absolute value exceeds $a_N$ uniformly over $U_N$. In that case, the hybrid policy classifies the user passively.

Consequently,

$$A_{i,N}\subseteq \{\mathbf{\mu }\notin U_N\}\cup \left\{\left|{\Lambda }_{T_N}\right|\le a_N\right\}\cup \left\{a_N<\left|{\Lambda }_{T_N}\right|\le a_N+L_{T_N}{r}_N\right\}$$

Using the world-confidence bound, the oracle-ambiguity probability, and the margin condition,

$$P(A_{i,N})\le {\kappa }_N+q_{T_N}({\epsilon }_N)+A(L_{T_N}{r}_N{)}^{\alpha }$$

Every actively tested user incurs cost at most $c{m}_N$. Therefore,

$$C_N\le c{m}_N\sum _{i=1}^N{1}_{A_{i,N}}$$

Taking expectations and using exchangeability gives

$$\frac{\mathbb{E}[C_N]}{N}\le c{m}_{N}P(A_{i,N})$$

Hence,

$$\frac{\mathbb{E}[C_N]}{N}\le c{m}_N\left[q_{T_N}({\epsilon }_N)+A(L_{T_N}{r}_N{)}^{\alpha }+{\kappa }_N\right]$$

Conditional on the event $\{\mathbf{\mu }\in U_N\}$, every passive or active classification has posterior error at most ${\epsilon }_N$. A union bound over the $N$ users gives

$$P(\hat{\mathbf{z}}\ne \mathbf{z}\mid \mathbf{\mu }\in U_N)\le N{\epsilon }_N$$

Since

$$N{\epsilon }_N=\frac{\delta }{2}$$

we obtain

$$P(\hat{\mathbf{z}}\ne \mathbf{z})\le {\kappa }_N+\frac{\delta }{2}$$

Finally, if

$$m_N{q}_{T_N}({\epsilon }_N)⟶0$$ $$m_N(L_{T_N}{r}_N{)}^{\alpha }⟶0$$

and

$$m_N{\kappa }_N⟶0$$

then the intervention-cost bound implies

$$\frac{\mathbb{E}[C_N]}{N}⟶0$$

Let

$$F_N:=\frac{1}{N}\sum _{i=1}^N{1}_{A_{i,N}}$$

denote the fraction of actively tested users. Its expectation satisfies

$$\mathbb{E}[F_N]=P(A_{i,N})⟶0$$

Markov’s inequality therefore gives

$$F_N⟶0$$

in probability. This completes the proof. $\square$