LFBL Research — MAB Formalism (in progress)

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

Theoretical Framework

We formally define the inverse multi-armed bandit problem under a biased demonstrator. Unlike classical inverse reinforcement learning (IRL) frameworks that assume a perfectly rational or Boltzmann-rational agent, our demonstrator is an online learner whose exploration is skewed by strong intrinsic preferences (prior biases).

Environment and Reward Structure

Consider a stochastic multi-armed bandit (MAB) environment with a finite set of arms denoted by $[K]:=\{1,2,\dots ,K\}$. Each arm $i\in [K]$ is associated with an unknown true reward distribution supported on $[0,1]$ with an expected true reward ${\mu }_i:=\mathbb{E}[Y(i)]$. We denote the vector of true mean rewards as $\mu =({\mu }_1,\dots ,{\mu }_K)\in [0,1{]}^K$. Without loss of generality, we assume a unique optimal arm $i^{\ast }=\arg {\max }_{i\in [K]}{\mu }_i$, and define the sub-optimality gap for arm $i$ as ${\Delta }_i={\mu }_{i^{\ast }}-{\mu }_i$.

The Biased Demonstrator Model

The demonstrator interacts with the environment sequentially over a horizon of $T$ rounds. At each round $t\in [T]$, the demonstrator selects an arm $A_t\in [K]$ and observes a noisy reward $Y_t\sim P_{A_t}$ such that $\mathbb{E}[Y_t\mid A_t]={\mu }_{A_t}$.

To model strong intrinsic preferences, we assume the demonstrator does not maintain purely empirical reward estimates. Instead, they operate under a regularized Bayesian-style prior bias. Let $\nu =({\nu }_1,\dots ,{\nu }_K)\in [0,1{]}^K$ be the demonstrator’s intrinsic anchor (bias) vector, and let $\lambda =({\lambda }_1,\dots ,{\lambda }_K)\in {\mathbb{R}}_{++}^K$ be the coordinates of prior intensity (pseudo-counts), capturing how strongly the demonstrator clings to their bias. Let $N_i(t)={\sum }_{\tau =1}^t\mathbb{I}(A_{\tau }=i)$ be the number of times arm $i$ has been selected up to round $t$. The demonstrator’s biased empirical mean ${\tilde{\mu }}_i(t)$ at the end of round $t$ is:

$${\tilde{\mu }}_i(t)=\frac{{\sum }_{\tau =1}^t\mathbb{I}(A_{\tau }=i)Y_{\tau }+{\lambda }_i{\nu }_i}{N_i(t)+{\lambda }_i}$$

We consider a demonstrator executing a Biased Upper Confidence Bound (B-UCB) policy. At round $t+1$, they select the action maximizing the biased index:

$$A_{t+1}=\arg \underset{i\in [K]}{\max }\left\{{\tilde{\mu }}_i(t)+\alpha \sqrt{\frac{\log t}{N_i(t)+{\lambda }_i}}\right\}$$

where $\alpha >0$ is a standard exploration parameter.

Remark 1 (Interpretation of Bias Intensity). When ${\lambda }_i\to 0$, the policy reduces to standard UCB1. When ${\lambda }_i\gg T$, the prior completely dominates the empirical feedback, yielding a stubbornly biased agent who rarely updates their belief about arm $i$ despite counter-evidence.

The Observer’s Objective and Information Structure

The observer has no access to the true rewards $\mu$, the realized rewards $Y_t$, or the internal indices. The observer records only the action history:

$${\mathcal{H}}_T=\{A_1,A_2,\dots ,A_T\}$$

The observer does not know the bias (the perception shift $b$, or the prior $(\nu ,\lambda )$); only the exploration constant $\alpha$ is treated as known (used to invert the action frequencies back to effective means). This is what makes recovering $\mu$ nontrivial. The objective is an estimator $\hat{\mu }:{\mathcal{H}}_T\to [0,1{]}^K$ minimizing the expected ${\ell }_{\infty }$ or ${\ell }_2$ error w.r.t. $\mu$, evaluated by the minimax risk over an admissible class $\mathcal{M}$:

$${\mathcal{R}}_T(\mathcal{M})=\underset{\hat{\mu }}{\inf }\underset{\mu \in \mathcal{M}}{\sup }{\mathbb{E}}_{\mu }\left[\Vert \hat{\mu }({\mathcal{H}}_T)-\mu {\Vert }_2\right]$$

Counterexamples

Counterexample Triviale: Constant Perceived Reward Bias (Exact Path Equivalence)

The cleanest counterexample is an additive perception bias (a cognitive distortion, comfort factor, or brand loyalty).

• The Biased Agent: true environmental mean ${\mu }_i$, but an intrinsic bias $b_i$: every pull of arm $i$ yields a perceived reward ${\tilde{Y}}_t=Y_t+b_i$. They run standard UCB on perceived rewards:

$$U_{i,t}^{\text{biased}}=\frac{{\sum }_{\tau =1}^t\mathbb{I}(A_{\tau }=i)(Y_{\tau }+b_i)}{N_i(t)}+\alpha \sqrt{\frac{\log t}{N_i(t)}}$$

• The Rational Agent with Different Preferences: no cognitive bias ($b_i=0$), but the true reward for arm $i$ is shifted to ${\mu }_i^{\prime }={\mu }_i+b_i$:

$$U_{i,t}^{\text{rational}}=\frac{{\sum }_{\tau =1}^t\mathbb{I}(A_{\tau }=i)Y_{\tau }^{\prime }}{N_i(t)}+\alpha \sqrt{\frac{\log t}{N_i(t)}}$$

The Equivalence. If the noise is symmetric (e.g. Gaussian), $(Y_{\tau }+b_i)$ and $Y_{\tau }^{\prime }$ are identically distributed, so the distribution over action sequences ${\mathcal{H}}_T$ is exactly identical for both agents.

Counterexample: Bayesian Prior Bias (Asymptotic Equivalence)

For the Prior Bias Model $(\nu ,\lambda )$, can a standard unbiased agent match it? Path-by-path at finite $t$, no: the exploration bonus decays at different rates due to ${\lambda }_i$ ($\sqrt{N_i(t)+{\lambda }_i}$ vs $\sqrt{N_i(t)}$). But it matches a different notion of rationality:

• The Biased Agent uses the regularized index

$$U_{i,t}^{\text{biased}}=\frac{N_i(t){\hat{\mu }}_i(t)+{\lambda }_i{\nu }_i}{N_i(t)+{\lambda }_i}+\alpha \sqrt{\frac{\log t}{N_i(t)+{\lambda }_i}}$$

• The Rational Bayesian Agent runs Bayes-UCB but starts with a subjective prior ${\mu }_i\sim \mathcal{N}({\nu }_i,1/{\lambda }_i)$.

The Equivalence. Their action choices are identical. What a psychologist calls a stubborn cognitive bias $(\nu ,\lambda )$, an economist calls rational utility maximization under a subjective prior. Actions cannot tell them apart.

Remark (caveat): this equivalence is only asymptotic. At finite $t$ the exploration bonuses differ ($\sqrt{N_i(t)+{\lambda }_i}$ vs $\sqrt{N_i(t)}$), so the action distributions are not identical and the two agents ARE distinguishable from the exploration pattern. This is an as-if-rational re-description, not an exact observational-equivalence result; the Le Cam lower bound below covers only the additive-bias case.

Interventions

Trivial Counterexample: Constant Perception Bias ($b_i$) vs. High True Reward (${\mu }_i^{\prime }$)

Ambiguity. The demonstrator pulls arm $i$ aggressively. Is the arm terrible with a huge psychological bias (${\mu }_i=0.2,b_i=0.6⟹0.8$), or genuinely excellent (${\mu }_i^{\prime }=0.8,b_i=0$)?

The observer alters the monetary scale while keeping mechanisms identical: “for the next 50 rounds all cash payouts are doubled.”

• Perception Bias ($b_i$): external reward doubles, internal bias constant: $V_{\text{biased}}=2{\mu }_i+b_i=2(0.2)+0.6=1.0$.
• True Reward Preference (${\mu }_i^{\prime }$): preference tied to payout: $V_{\text{rational}}=2{\mu }_i^{\prime }=2(0.8)=1.6$.

Distinguishes them: comparing how choice probability for arm $i$ shifts vs a control arm as stakes rise isolates the linear weight of $b_i$. If the agent becomes relatively less interested as stakes rise, the preference was a fixed internal bias, not the scalable environment.

Prior-Belief Case: Prior Belief Bias (${\nu }_i,{\lambda }_i$) vs. Intrinsic Utility Bias

Ambiguity. Two hypotheses for stubbornly pulling a bad arm early:

1. Prior Belief Bias: a rational Bayesian who honestly thinks the arm is good (${\nu }_i$ high) but will update with data.
2. Intrinsic Utility Bias: the agent knows it pays poorly but derives permanent, non-fading psychic utility (${\nu }_i$) from it.

Intervention A: Information Shock (Data Flooding)

The observer hands over a verified log of $M=10,000$ trials of arm $i$ proving its true mean is low (${\mu }_i=0.2$).

• Prior Belief Bias: the $M$ samples enter the Bayesian update; since $M\gg {\lambda }_i$, the prior is wiped out,

$${\tilde{\mu }}_i=\frac{N_i{\hat{\mu }}_i+M(0.2)+{\lambda }_i{\nu }_i}{N_i+M+{\lambda }_i}\approx 0.2,$$

and the agent abandons the arm.

• Intrinsic Utility Bias: “I now know it only pays 0.2 in cash, but I still get 0.6 units of pure joy” — total utility stays $0.8$ and they keep pulling.

Distinguishes them: a data shock collapses a belief distortion but leaves an intrinsic preference unchanged.

Intervention B: Horizon Truncation (Endgame Nudge)

At round $t$ the observer announces termination at $T=t+1$, destroying future-exploration incentive and collapsing the bonus $\alpha \sqrt{\log t/N_i}$ to zero; the agent must purely exploit.

• Prior Belief Bias: a rational Bayesian at immediate horizon maximizes current empirical belief; if experience already dragged ${\tilde{\mu }}_i$ down, removing the bonus makes them drop the arm.
• Intrinsic Utility Bias: the structural bonus is decoupled from information gathering; if strong enough it overrides exploration entirely, so the $T=1$ decision matches the $T=100$ behavior.

Minimax Analysis and Proofs

Information-theoretic analysis (inspired by the inverse-bandit paper): passive observation suffers an insurmountable information deficit from observational equivalence, whereas intervention achieves the optimal parametric rate.

Passive Observation and Information-Theoretic Lower Bound

Let $\Theta =[0,1{]}^K\times [-1,1{]}^K$ be the parameter space of $\theta =(\mu ,b)$, with $\mu \in [0,1{]}^K$ the true mean vector and $b\in [-1,1{]}^K$ the constant perception bias. The demonstrator observes ${\tilde{Y}}_t=Y_t+b_{A_t}$ with $Y_t\sim \mathcal{N}({\mu }_{A_t},{\sigma }^2)$, so ${\tilde{Y}}_t\sim \mathcal{N}({\mu }_{A_t}+b_{A_t},{\sigma }^2)$. Let $P_{\theta }$ be the measure induced over ${\mathcal{H}}_T$ under $\theta$.

Theorem (Passive Minimax Lower Bound). In the passive setting where the observer records only ${\mathcal{H}}_T$, the minimax error is lower-bounded by a constant independent of $T$:

$$\underset{\hat{\mu }}{\inf }\underset{\theta \in \Theta }{\sup }{\mathbb{E}}_{\theta }\left[\Vert \hat{\mu }({\mathcal{H}}_T)-\mu {\Vert }_2\right]\ge C>0$$

Proof. By Le Cam’s two-point method, it suffices to exhibit ${\theta }_0=({\mu }^{(0)},b^{(0)})$ and ${\theta }_1=({\mu }^{(1)},b^{(1)})$ mapping to identical perceived-reward distributions while separated in $\mu$. Take $K=2$, an interior baseline $m\in (0,1)$, and $ϵ>0$ with $m+ϵ<1$:

• Instance 0: ${\mu }^{(0)}=(m,m{)}^{\top }$, $b^{(0)}=(ϵ,0{)}^{\top }$.
• Instance 1: ${\mu }^{(1)}=(m+ϵ,m{)}^{\top }$, $b^{(1)}=(0,0{)}^{\top }$.

The reward-vector separation is

$$\Vert {\mu }^{(0)}-{\mu }^{(1)}{\Vert }_2=\sqrt{(m-(m+ϵ){)}^2+(m-m{)}^2}=ϵ.$$

The effective means $\tilde{\mu }=\mu +b$ driving the policy are identical:

$${\tilde{\mu }}^{(0)}=\left(\begin{array}{c}m+ϵ\\ m\end{array}\right),{\tilde{\mu }}^{(1)}=\left(\begin{array}{c}m+ϵ\\ m\end{array}\right).$$

Since ${\tilde{\mu }}^{(0)}={\tilde{\mu }}^{(1)}$ and ${\sigma }^2$ is shared, ${\tilde{Y}}_t\mid A_t$ is identically distributed under both, so the history-dependent policy induces indistinguishable path measures $P_{{\theta }_0}({\mathcal{H}}_T)=P_{{\theta }_1}({\mathcal{H}}_T)$, hence

$$D_{\mathrm{KL}}(P_{{\theta }_0}\parallel P_{{\theta }_1})=0.$$

Le Cam’s inequality gives, for any $\hat{\mu }$,

$$\underset{\theta \in \Theta }{\sup }{\mathbb{E}}_{\theta }[\Vert \hat{\mu }-\mu {\Vert }_2]\ge \frac{1}{2}\Vert {\mu }^{(0)}-{\mu }^{(1)}{\Vert }_2\left(1-\sqrt{\frac{1}{2}{D}_{\mathrm{KL}}}\right)=\frac{ϵ}{2}.$$

Setting $C=ϵ/2$ completes the proof; since $ϵ$ is independent of $T$, the floor does not decay with data. $■$

Interventional Design and Parametric Convergence Rate

An active observer deploys a macro-phase Stakes Manipulation policy $\mathcal{I}$: partition the horizon into two epochs of size $T/2$. Phase 1 leaves rewards unmodified (${\gamma }_t=1$); Phase 2 multiplies all payoffs by ${\gamma }_t=\gamma >1$. Assume minimum exploratory coverage $\mathbb{E}[N_i(T/2)]\ge cT$ for all $i$ and some $c>0$. (Assumption flagged — to revisit: this uniform-coverage bound conflicts with the strong-bias regime $\lambda \gg T$, where biased arms are chronically under-pulled, so coverage can fail precisely on the arms that are hardest to identify. Not addressed for now.)

Theorem (Interventional Upper Bound). Under $\mathcal{I}$, there is a joint estimator with

$$\underset{\theta \in \Theta }{\sup }{\mathbb{E}}_{\theta }\left[\Vert \hat{\mu }({\mathcal{H}}_T\mid \mathcal{I})-\mu {\Vert }_2\right]\le \mathcal{O}\left(\frac{1}{\sqrt{T}}\right).$$

Proof. In Phase 1 the demonstrator acts under ${\xi }^{(1)}=\mu +b$. By structural inversion on the empirical allocations, with coverage $\mathbb{E}[N_i(T/2)]\ge cT$, concentration gives

$$\mathbb{E}\left[\Vert {\hat{\xi }}^{(1)}-(\mu +b){\Vert }_2\right]\le \frac{C_1}{\sqrt{T}}.$$

In Phase 2 the demonstrator responds to ${\xi }^{(2)}=\gamma \mu +b$, giving $\mathbb{E}[\Vert {\hat{\xi }}^{(2)}-(\gamma \mu +b){\Vert }_2]\le C_2/\sqrt{T}$. Isolate $\mu$ by the linear combination

$$\hat{\mu }({\mathcal{H}}_T\mid \mathcal{I})=\frac{{\hat{\xi }}^{(2)}-{\hat{\xi }}^{(1)}}{\gamma -1}.$$

By the triangle inequality,

$$\mathbb{E}\left[\Vert \hat{\mu }-\mu {\Vert }_2\right]\le \frac{1}{\gamma -1}\left(\frac{C_2}{\sqrt{T}}+\frac{C_1}{\sqrt{T}}\right)=\frac{C_1+C_2}{(\gamma -1)\sqrt{T}}.$$

With $C_{\text{upper}}=(C_1+C_2)/(\gamma -1)$ this is $\mathbb{E}[\Vert \hat{\mu }-\mu {\Vert }_2]\le C_{\text{upper}}/\sqrt{T}$, the optimal parametric rate $\mathcal{O}(1/\sqrt{T})$. $■$