scripts/make_logbook.py

"""Render the Trackio logbook pages from the raw result JSONs in outputs/."""

from __future__ import annotations

import json
import os
import uuid

ROOT = os.path.dirname(os.path.dirname(os.path.abspath(__file__)))
PAGES = os.path.join(ROOT, ".trackio", "logbook", "pages")
OUT = os.path.join(ROOT, "outputs")
NOW = "2026-07-25T13:00:00+00:00"

TITLE = "A Perturbation Approach to Unconstrained Linear Bandits"
ARXIV = "2603.28201"
ORID = "XSpBSHzJAg"

SLUGS = {
    1: "claim-1-pablo-reduces-ublo-to-olo",
    2: "claim-2-thm-3-1-expected-static-regret-kappa-gap",
    3: "claim-3-thm-3-3-sqrt-p-t-dynamic-regret-without-prior-p-t",
    4: "claim-4-thm-4-2-high-probability-static-regret",
    5: "claim-5-thm-5-2-omega-sqrt-dt-lower-bound-on-euclidean-ball",
    6: "claim-6-conjecture-5-3-minimax-rate-open-problem",
}
NAMES = {
    1: "Claim 1: PABLO reduces uBLO to OLO",
    2: "Claim 2: Thm 3.1 expected static regret, kappa gap",
    3: "Claim 3: Thm 3.3 sqrt(P_T) dynamic regret without prior P_T",
    4: "Claim 4: Thm 4.2 high-probability static regret",
    5: "Claim 5: Thm 5.2 Omega(sqrt(dT)) lower bound on Euclidean ball",
    6: "Claim 6: Conjecture 5.3 minimax rate open problem",
}
CLAIMS = {
    1: "The paper's perturbation-based algorithm, PABLO, reduces unconstrained Bandit Linear "
    "Optimization (uBLO) to a standard Online Linear Optimization (OLO) problem "
    "(Section 3).",
    2: "Theorem 3.1 gives an expected static-regret bound of the form E[R_T(u)] = "
    "O~(G*epsilon + d*kappa*E[||u||*sqrt(V_T log(...))]), with kappa=sqrt(d) in the "
    "norm-oblivious setting and kappa=1 in the norm-adaptive setting (Theorem 3.1).",
    3: "Theorem 3.3 shows PABLO attains the optimal sqrt(P_T) dynamic-regret dependence on "
    "the path-length P_T without requiring prior knowledge of P_T (Theorem 3.3).",
    4: "Theorem 4.2 establishes a high-probability static-regret bound R_T(u) <= "
    "O~(dG(epsilon+||u||)log(T/delta) + G||u||sqrt(dT log(T/delta))) (Theorem 4.2).",
    5: "Theorem 5.2 proves the folklore Omega(sqrt(dT)) minimax lower bound for adversarial "
    "linear bandits on the unit Euclidean ball (Theorem 5.2).",
    6: "Conjecture 5.3 posits a minimax rate of R_T(u) = Theta(||u|| sqrt(T(d v log||u||))) "
    "for norm-oblivious comparators, left as an open problem (Conjecture 5.3).",
}


def cell(kind, title, body, pinned=False, extra=None):
    meta = {
        "type": kind,
        "id": "cell_" + uuid.uuid4().hex[:12],
        "created_at": NOW,
        "title": title,
    }
    if pinned:
        meta["pinned"] = True
        meta["pinned_at"] = NOW
    if extra:
        meta.update(extra)
    return "\n---\n<!-- trackio-cell\n" + json.dumps(meta) + "\n-->\n" + body + "\n"


def write(slug, heading, cells):
    d = os.path.join(PAGES, slug) if slug != "index" else PAGES
    os.makedirs(d, exist_ok=True)
    path = os.path.join(d, "page.md" if slug != "index" else "index.md")
    with open(path, "w") as f:
        f.write("# " + heading + "\n\n" + "".join(cells))


def load(name):
    with open(os.path.join(OUT, name)) as f:
        return json.load(f)


c1 = load("claim1_reduction.json")
c2 = load("claim2_static.json")
c3 = load("claim3_dynamic.json")
c4 = load("claim4_highprob.json")
c4s = load("claim4_tail_supplement.json")
c5 = load("claim5_lowerbound.json")
c6 = load("claim6_conjecture.json")
c5s = load("claim5_supplement.json")

# ---------------------------------------------------------------------------- index
rows = "\n".join("| [%s](#/%s) |" % (NAMES[i], SLUGS[i]) for i in range(1, 7))
write(
    "index",
    "Reproduction: " + TITLE,
    [
        "\n## Pages\n\n"
        "| Page |\n| --- |\n| [Executive summary](#/executive-summary) |\n%s\n"
        "| [Conclusion](#/conclusion) |\n" % (rows,)
    ],
)

# ------------------------------------------------------------------ executive summary
B = c2["B_scalings"]
c5r = c5["T1_T2_rates"]
exec_md = """# Executive summary

Paper: [arXiv {arxiv}](https://arxiv.org/abs/{arxiv}) ·
[OpenReview](https://openreview.net/forum?id=XSpBSHzJAg) ·
logbook: [huggingface.co/spaces/SabaPivot/repro-a-perturbation-approach-to-unconstrained-linear-bandits](https://huggingface.co/spaces/SabaPivot/repro-a-perturbation-approach-to-unconstrained-linear-bandits)

**Five of the six claims of "A Perturbation Approach to Unconstrained Linear Bandits"
(arXiv {arxiv}, ICML 2026) reproduce independently on CPU at $0; the sixth is the paper's own
open problem and is recorded honestly as `toy`.** The paper releases no code (no repository is
linked on arXiv, on OpenReview, or in the PDF), so PABLO (Algorithm 1), the perturbation of
Eq. (4) and the parameter-free OLO subroutines (Algorithms 5 and 6, Appendix E.2) were
re-implemented from the pseudocode alone and then attacked from outside: Proposition 2.1 is
checked **exhaustively** (a PABLO round has exactly `2d` outcomes, so its conditional moments
are computed by enumeration, not Monte Carlo) to a relative error of {p21:.1e}; Corollary 2.2's
two constants are attained exactly (ratio 1.000) and **break as soon as Eq. (4) is violated**
(c = 1.5 already fails); the reduction identity E[R_T^uBLO] = E[R_T^OLO] holds to {rb:.1e}
relative error along real trajectories; and the paper's own Theorem E.6 — which we had to
re-derive to disambiguate a fraction the PDF flattens — holds in 60/60 randomized
full-information instances (the alternative parsing violates it by 10^128).

**Rates.** On the hardest known loss family the measured expected regret has fitted exponents
{eT:.3f} ± {sT:.3f} in T, {ed:.3f} ± {sd:.3f} in d and {eu:.3f} in ||u|| against Theorem 3.1's
predicted 1/2, 1/2 (the kappa = sqrt(d) branch) and 1. Dynamic regret satisfies R_T^2 = a + b P_T
with r^2 = {r2:.3f} — a sqrt(P_T) dependence — with P_T withheld from the algorithm. The
high-probability bound of Theorem 4.3 (the claim's "4.2") is never violated in
{nq} quantile tests over 4,000 seeds and its deviation term grows like sqrt(log(T/delta))
(r^2 = {tail:.3f}). Theorem 5.2's construction forces every algorithm we ran above the stated
floor; the empirical minimax envelope scales as T^{{{e5T:.3f}}} at fixed d and, at a fixed
aspect ratio T = 500d, as d^{{{e5d:.3f}}} (predicted 1); envelope/sqrt(dT) stays in
[0.50, 0.82] across every configuration.

**Two honest negatives.** (i) We could not realise the norm-adaptive (kappa = 1) branch of
Theorem 3.1: a comparator norm chosen *after* the trajectory buys a factor 1.000, not the
sqrt(d) the bound allows — the upper bound is valid but not tight there, which is exactly the
question the paper itself leaves open. (ii) Our oblivious instance battery does not realise
Conjecture 5.3's log||u|| growth; the ratio to the conjectured rate *decreases* with ||u||
(slope -0.069 at d = 2), consistent with the log factor requiring an adaptive adversary.

## Scope & cost

| Item | Value |
| --- | --- |
| Scope | 6 claims, independent re-implementation from the pseudocode; no author code exists |
| Hardware | CPU only (shared x86 box), numpy/scipy, no GPU, no API calls |
| Compute time | ~1.5 h wall-clock for all nine scripts on a heavily shared CPU box (numpy only) |
| Cost | $0 |
| Scale | up to d = 64, T = 16,000; 4,000 seeds for the distributional tests; every seed explicit |
""".format(
    arxiv=ARXIV,
    p21=c1["t1_proposition_2_1_exhaustive"]["max_rel_err_unbiasedness"],
    rb=c1["t5_conditional_identity_exact"]["max_rel_err_estimated_loss"],
    eT=B["T_sweep"]["fitted_exponent"],
    sT=B["T_sweep"]["stderr"],
    ed=B["d_sweep"]["fitted_exponent"],
    sd=B["d_sweep"]["stderr"],
    eu=B["u_sweep"]["fitted_exponent"],
    r2=c3["C_D_path_length_sweep"]["regression_of_squared_regret_on_P_T"]["r_squared"],
    nq=len(c4["T2_T3_T4_quantiles"]["quantiles"]["rows"]) + len(c4s["quantiles"]),
    tail=c4["T2_T3_T4_quantiles"]["quantiles"][
        "tail_regression_on_sqrt_log_T_over_delta"
    ]["r_squared"],
    e5d=c5s["fitted_d_exponent"],
    e5T=c5r["fitted_T_exponent"],
)

poster_path = os.path.join(ROOT, "poster", "poster_embed.html")
poster = (
    open(poster_path).read()
    if os.path.exists(poster_path)
    else "<p>poster_embed.html pending</p>"
)
write(
    "executive-summary",
    "Executive summary",
    [
        cell("markdown", "Executive summary", exec_md, pinned=True),
        cell(
            "figure",
            "Reproduction poster (poster_embed.html)",
            "````html\n" + poster + "\n````",
            pinned=True,
        ),
    ],
)

# ------------------------------------------------------------------------- claim pages
t2 = c1["t2_corollary_2_2_and_boundary"]
audit = t2["boundary_audit"]
p1 = """> **Claim (verbatim).** {claim}

## Verdict: **verified**

PABLO is a *reduction*, and the reduction is an exact identity in conditional expectation, not
an approximation. Four independent tests, all from the pseudocode of Algorithm 1 with the
isotropic H_t of Eq. (4) (H_t = I/(d(||w_t||^2 v eps^2)), eigenvectors = standard basis,
s_t uniform on {{+-e_i}}).

### T1 — Proposition 2.1, checked **exhaustively** (not by sampling)
A PABLO round has exactly `2d` equally likely outcomes, so E[ltilde|F] and E[||ltilde||^2|F]
are computable by enumeration. Over **{n1} random configurations, d = 1..12**, random
||w_t|| spanning 10^-2..10^2 and eps spanning 10^-3..1:

| quantity | paper's closed form | max relative error |
| --- | --- | --- |
| E[ltilde_t \\| F_{{t-1}}] | l_t (unbiased) | {e1:.2e} |
| E[\\|\\|ltilde_t\\|\\|^2 \\| F_{{t-1}}] | d\\|\\|l_t\\|\\|^2 + d<l_t,w_t>^2 Tr(H_t) | {e2:.2e} |

### T2 — Corollary 2.2 and a boundary audit
Over {n2} configurations the two constants are **exactly attained**: max ratio to the a.s.
bound 4d^2||l||^2 is {r1:.4f}, max ratio to the conditional bound 2d||l||^2 is {r2:.4f}.
Scaling H_t by c so that Eq. (4) is violated breaks the a.s. bound immediately:

| c (Eq. (4) needs c <= 1) | max ||ltilde||^2 / (4d^2||l||^2) | holds |
| --- | --- | --- |
{audit}

### T3/T5 — the reduction identity itself (Proposition 2.3)
For an F_0-measurable comparator, E[sum_t <l_t, wtilde_t - u>] = E[sum_t <ltilde_t, w_t - u>]:
the uBLO problem *is* the OLO problem in expectation. Rao-Blackwellised along real
trajectories (all 2d outcomes enumerated at every round, **{rounds} rounds**, two different
OLO subroutines, d = 3, 8, 16), the two conditional expectations agree with <l_t, w_t - u> to
max relative error **{e5a:.1e}** (played point) and **{e5b:.1e}** (estimated loss). The plain
Monte-Carlo version over 3,000-4,000 seeds finds no detectable difference either
(|z| <= {z:.2f}).

### T4 — black-box modularity
Three different OLO subroutines dropped into the same wrapper (the paper's Algorithm 6,
OGD at 1/(L sqrt T), OGD mistuned by 10x): in each case the measured uBLO regret tracks that
learner's OLO regret on the estimated losses, and the *ranking* of the learners is preserved.
That is what "reduces to OLO" means operationally.

## Scale, seeds, limitations
* {n1} + {n2} exhaustive configurations; {rounds} Rao-Blackwellised rounds; 3,000-4,000 Monte-Carlo
  replicates per setting; master seed 20260725, every RNG seed explicit in the script.
* Limitation: the reduction is verified for the isotropic H_t of Eq. (4), the choice the paper
  itself adopts for all of Sections 3-4; general positive-definite H_t is covered by the same
  enumeration code but was not swept.
* Script: `scripts/claim1_reduction.py` · raw: `outputs/claim1_reduction.json` ·
  implementation: `scripts/pablo.py`.
""".format(
    claim=CLAIMS[1],
    n1=c1["t1_proposition_2_1_exhaustive"]["configs"],
    e1=c1["t1_proposition_2_1_exhaustive"]["max_rel_err_unbiasedness"],
    e2=c1["t1_proposition_2_1_exhaustive"]["max_rel_err_second_moment"],
    n2=t2["configs"],
    r1=t2["max_ratio_as_bound"],
    r2=t2["max_ratio_expectation_bound"],
    audit="\n".join(
        "| %g | %.4f | %s |"
        % (a["c"], a["max_ratio_to_Cor22_as_bound"], "yes" if a["holds"] else "**no**")
        for a in audit
    ),
    rounds=c1["t5_conditional_identity_exact"]["rounds_checked"],
    e5a=c1["t5_conditional_identity_exact"]["max_rel_err_played_point"],
    e5b=c1["t5_conditional_identity_exact"]["max_rel_err_estimated_loss"],
    z=max(abs(r["z_score"]) for r in c1["t3_reduction_identity"]),
)
write(SLUGS[1], NAMES[1], [cell("markdown", NAMES[1], p1)])

D = c2["D_kappa_mechanism"]
C = c2["C_bound_check"]
E = c2["E_norm_adaptive_adversary"]
p2 = """> **Claim (verbatim).** {claim}

## Verdict: **verified** (with one reproducible negative, below)

**Reading of the formula.** The paper writes the bound with a factor **d/kappa**, kappa = sqrt(d)
oblivious and kappa = 1 adaptive, i.e. an effective dimension factor **sqrt(d)** in the
norm-oblivious regime and **d** in the norm-adaptive one — the "sqrt(d) separation" of
Section 3.1. The claim text above transcribes it as `d*kappa`; we test the paper's formula and
report both branches explicitly.

**Instantiation.** PABLO + **Algorithm 6 of the paper itself** (Appendix E.2), tuned with
eps/d as Theorem 3.1 prescribes; its static specialisation satisfies exactly the parameter-free
OLO guarantee the theorem requires of Jacobsen & Cutkosky (2022, Algorithm 4), which is not
restated in this paper. Losses: the minimax-hard family (theta in {{+-G/sqrt(T)}}^d, noise
variance G^2/(2d)), plus a coordinate-Rademacher family and an adversarial sign-flipping family.

### Fitted exponents (norm-oblivious comparator, {S} seeds per point)

| swept | values | fitted exponent | Theorem 3.1 predicts |
| --- | --- | --- | --- |
| T (d = 8) | {Tv} | **{eT:.3f} ± {sT:.3f}** | 0.5 |
| d (T = 2000) | {dv} | **{ed:.3f} ± {sd:.3f}** | 0.5 (kappa = sqrt(d)) / 1.0 (kappa = 1) |
| ||u|| (d = 8, T = 2000) | 0.25 … 64 | **{eu:.3f} ± {su:.3f}** | 1 |

The d-exponent {ed:.3f} sits on the **kappa = sqrt(d)** branch and is {nsig:.0f} standard errors
below the kappa = 1 branch.

### Where kappa comes from (measured, not quoted)
Corollary 2.2 gives two bounds on the estimated loss; which one the analysis may use is the
whole content of kappa. Measured along real trajectories:

| d | realised sum_t ||ltilde_t||^2 / V_T | conditional bound 2d | a.s. bound 4d^2 |
| --- | --- | --- | --- |
{kap}

The realised dimension factor has fitted exponent **{ekap:.4f} ± {sekap:.4f}** in d (0.5 = the
kappa = sqrt(d) branch): the a.s. bound that produces kappa = 1 is loose by a factor ~4d on
every trajectory we observed.

### The bound holds, and the risk-control term holds
Across 3 loss families x d in {{2, 8, 32}}, maximising over a comparator-norm grid, the largest
ratio of the measured E[R_T(u)] to the kappa = sqrt(d) bound (all unspecified constants set to 1)
is **{mr:.3f}**; to the kappa = 1 bound, {mr1:.3f}. R_T(0) never exceeded **{r0:.3f}** against a
budget of G*eps = 1 — including on the sign-flipping family where the learner does scale up to
||w_t|| = {mw:.3f} and must unwind.

### Reproducible negative: the norm-adaptive branch is not realised
An adversary that fixes ||u|| **only after** seeing the realised trajectory (per-seed
maximisation over the norm grid) gains a factor **{adv:.3f}** over the best oblivious norm, not
the sqrt(d) in {{1.41 … 5.66}} that the kappa = 1 branch allows; 0 of {S} seeds exceeded the
oblivious bound at any d. The extra sqrt(d) is therefore an artefact of worst-case analysis on
these instances. This is consistent with the paper's own statement that whether the gap is
intrinsic "remains open"; it is **not** a contradiction of the theorem, which is an upper bound.

## Scale, seeds, limitations
* {S} seeds per configuration, d up to 64, T up to 8,000; master seed 20260725.
* Limitation: on the minimax-hard family the risk-controlled learner correctly keeps
  ||w_t|| ~ 1e-4, so the measured regret there is the comparator's advantage and the ||u||
  exponent is 1 by construction; the T- and d-exponents are not (they are set by
  ||sum_t l_t|| ~ sqrt(dT) on that family). The sign-flipping family is where the learner is
  active, and the bound is checked there too.
* Limitation: Jacobsen & Cutkosky (2022, Algorithm 4) itself was not re-implemented;
  Algorithm 6 of this paper is used as the OLO subroutine (same guarantee shape).
* Script: `scripts/claim2_static.py` · raw: `outputs/claim2_static.json`.
""".format(
    claim=CLAIMS[2],
    S=B["d_sweep"]["seeds"],
    Tv=", ".join(str(x) for x in B["T_sweep"]["T"]),
    dv=", ".join(str(x) for x in B["d_sweep"]["d"]),
    eT=B["T_sweep"]["fitted_exponent"],
    sT=B["T_sweep"]["stderr"],
    ed=B["d_sweep"]["fitted_exponent"],
    sd=B["d_sweep"]["stderr"],
    eu=B["u_sweep"]["fitted_exponent"],
    su=B["u_sweep"]["stderr"],
    nsig=(1.0 - B["d_sweep"]["fitted_exponent"]) / B["d_sweep"]["stderr"],
    kap="\n".join(
        "| %d | %.2f | %g | %g |"
        % (
            r["d"],
            r["mean_sum_ltilde_sq_over_V_T"],
            r["Cor22_expectation_bound_2d"],
            r["Cor22_as_bound_4d2"],
        )
        for r in D["rows"]
    ),
    ekap=D["fitted_d_exponent_of_realised_dimension_factor"],
    sekap=D["stderr"],
    mr=max(r["max_ratio_to_kappa_sqrt_d_bound"] for r in C),
    mr1=max(r["max_ratio_to_kappa_1_bound"] for r in C),
    r0=max(r["max_R_T_0"] for r in C),
    mw=max(r["max_iterate_norm"] for r in C),
    adv=max(r["adaptive_over_oblivious"] for r in E),
)
write(SLUGS[2], NAMES[2], [cell("markdown", NAMES[2], p2)])

CD = c3["C_D_path_length_sweep"]
reg = CD["regression_of_squared_regret_on_P_T"]
p3 = """> **Claim (verbatim).** {claim}

## Verdict: **verified**

**Instantiation.** PABLO + **Algorithm 6** (Appendix E.2), built from the paper's pseudocode:
one Algorithm-5 instance per step size eta_i = min(2^i/(TL), 1/L), playing the **sum** of their
iterates. Its inputs are exactly (eps, L, T) — **no P_T, no M = max_t ||u_t||** — which is the
structural content of "without prior knowledge".

### The base algorithm is correct: Theorem E.6 / E.7 checked as inequalities
* Theorem E.6 (Algorithm 5): **{n6} randomized full-information instances, 0 violations**,
  minimum slack {slack:.1f}; static, drifting and switching comparator sequences.
* Theorem E.7 (Algorithm 6): 4/4 instances hold.
* The PDF flattens a fraction in Algorithm 5's exponential update. The mirror-descent
  optimality condition for psi(w) = (k/eta)∫log(x/alpha+1)dx forces exp((eta/k)(...)); running
  the alternative parsing exp((k/eta)(...)) on a sign-flipping instance gives regret
  **{wrong:.2e}** against a Theorem-E.6 bound of {bnd:.2f} — the check is discriminative, and
  our parsing is the one that satisfies the paper's own theorem.

### sqrt(P_T) with P_T withheld ({S} seeds/point, T = {T}, d = {d}, M = 1)
Comparator sequences are piecewise-constant over K phases, each phase an independent hard
instance calibrated to its own length; P_T is measured from the sequence and never given to the
learner.

| K | P_T | measured E[R_T(u_1:T)] | Theorem E.7 bound (no P_T needed) |
| --- | --- | --- | --- |
{rows}

A sqrt(P_T) dependence means R_T^2 is **affine** in P_T. Regressing the measured R^2 on P_T:
slope {slope:.3g}, intercept {icpt:.3g}, **r^2 = {r2:.4f}**. (The naive log-log slope,
{naive:.3f}, is biased below 1/2 by the large P_T-independent intercept — the static part of the
regret.) In T at fixed K the fitted exponent is {eT:.3f} ± {seT:.3f}, and in d it is
{ed:.3f} ± {sed:.3f} — again the kappa = sqrt(d) branch.

### The price of *not* knowing P_T
A single-step-size learner has to pick eta. Minimising Theorem E.6's bound separately for each
P_T (the oracle) and comparing with the eta that is optimal at P_T = 0:

| P_T | E6 bound, oracle eta | E6 bound, eta tuned for P_T = 0 | ratio |
| --- | --- | --- | --- |
{tune}

so a static tuning already costs **{deg:.2f}x** at P_T = {maxP:.1f} and the gap keeps growing,
while Algorithm 6 needs no tuning at all.

## Scale, seeds, limitations
* {S} seeds per point, T from 500 to 16,000, d from 2 to 32, P_T from 0 to {maxP:.1f}; master
  seed 20260725.
* **Limitation (stated plainly).** We could not exhibit an instance where the *realised* regret
  separates a P_T-aware from a P_T-agnostic tuning: on families where the comparator is
  competitive PABLO correctly plays ||w_t|| ~ 1e-3, so the realised regret is the
  information-theoretic floor and every step size gives the same number; on families where it
  scales up it beats the norm-M comparator outright (negative dynamic regret). The
  no-prior-knowledge property is therefore verified structurally and at the level of the
  guarantees, not by a realised-regret separation.
* **Limitation.** Theorem E.7's constant is dominated by its own lower-order additive term
  4L|S|(eps + M + Phi_T + P^Phi_T) at every feasible horizon: at T = {T} its bound is
  {ratio6:.1f}x the oracle single-eta bound, and the sqrt(P_T) main term only overtakes the
  additive term for T of order 10^7.
* Script: `scripts/claim3_dynamic.py` · base algorithm: `scripts/alg5.py`, `scripts/pablo.py`.
""".format(
    claim=CLAIMS[3],
    n6=c3["A_theorem_E6_check"]["trials"],
    slack=c3["A_theorem_E6_check"]["min_slack"],
    wrong=c3["A2_update_parse_identifiability"]["regret_with_k_over_eta"],
    bnd=c3["A2_update_parse_identifiability"]["thm_E6_bound"],
    S=CD["seeds"],
    T=CD["T"],
    d=CD["d"],
    rows="\n".join(
        "| %d | %.2f | %.1f | %.3g |"
        % (
            r["K"],
            r["P_T"],
            r["measured_alg6_no_prior_knowledge"],
            r["bound_E7_alg6_no_prior_knowledge"],
        )
        for r in CD["rows"]
    ),
    slope=reg["slope"],
    icpt=reg["intercept"],
    r2=reg["r_squared"],
    naive=CD["fitted_P_T_exponent_of_measured_regret"],
    eT=c3["T_sweep"]["fitted_T_exponent"],
    seT=c3["T_sweep"]["stderr"],
    ed=c3["E_dimension_sweep"]["fitted_d_exponent"],
    sed=c3["E_dimension_sweep"]["stderr"],
    tune="\n".join(
        "| %.2f | %.3g | %.3g | %.2f |"
        % (
            r["P_T"],
            r["bound_E6_oracle_eta"],
            r["bound_E6_with_eta_tuned_for_P_T_zero"],
            r["static_tuning_bound_over_oracle_bound"],
        )
        for r in CD["rows"]
    ),
    deg=CD["max_static_tuning_bound_over_oracle_bound"],
    maxP=max(r["P_T"] for r in CD["rows"]),
    ratio6=CD["max_alg6_bound_over_oracle_bound"],
)
write(SLUGS[3], NAMES[3], [cell("markdown", NAMES[3], p3)])

Q = c4["T2_T3_T4_quantiles"]
EX = Q["exponents_of_the_1_minus_3delta_quantile"]
p4 = """> **Claim (verbatim).** {claim}

## Verdict: **verified**

**Numbering.** In **arXiv:{arxiv}v2** the statement carrying exactly this formula is
**Theorem 4.3** (Section 4); "4.2" in that version is a remark. We test the formula, and record
the discrepancy rather than silently renumbering.

### T1 — Proposition 4.1, the reduction the theorem is built on
With all unspecified constants set to 1 and the paper's varepsilon^2 ∝ 1/T setting of Eq. (4),
     R_T(u) <= R~^A_T(u) + G sqrt(d sum_t||w_t||^2 log(1/delta))
                         + G sqrt(d sum_t||u_t||^2 log(1/delta)) + dG P_T
was checked as an *event probability* over **{S1} seeds** for d in {{4, 8, 16}}, T in
{{2000, 4000}}, ||u|| in {{1, 8}} and six values of delta: **{nrows} configurations, 0 violations**,
empirical failure probability 0.0000 against the allowed 3*delta.

### T2 — the regret distribution against the theorem's bound
{S2} seeds, d = 8, T = 2000, comparator norms 1, 4, 16, six values of delta ({nq2} tests):
**no violation**; the largest ratio of the (1-3delta) quantile to the bound is {mrat:.3f}.

| delta | (1-3delta) quantile, ||u||=4 | Theorem bound | ratio |
| --- | --- | --- | --- |
{qrows}

### T3 — the shape of the tail
Regressing the quantile on sqrt(log(T/delta)) gives slope {slope:.2f} with **r^2 = {r2:.4f}**.
On this family the regret is extremely concentrated (std/mean = {cv:.1e}), so the deviation term
is not stressed; the supplement below repeats the test where it is.

### T4 — exponents of the (1-3delta) quantile, delta = 0.01

| swept | fitted | predicted |
| --- | --- | --- |
| T | {eT:.3f} ± {sT:.3f} | 0.5 |
| d | {ed:.3f} ± {sd:.3f} | 0.5 |
| ||u|| | {eu:.3f} ± {su:.3f} | 1 |

### Supplement — the same test where the learner is ACTIVE
On the sign-flipping family PABLO does scale up (max_t ||w_t|| up to {mw:.2f}) and the regret
has a genuine distribution (coefficient of variation up to {cv2:.2f}). Over {S3} seeds and 4
instances: **{v1} violations of the theorem's bound, {v2} violations of Proposition 4.1**, and
the quantile grows in sqrt(log(T/delta)) with r^2 in [{r2lo:.3f}, {r2hi:.3f}].

### T5 — boundary audit of varepsilon^2 ∝ 1/T
Replacing Eq. (4)'s varepsilon by 0.1, by 1 and by 1e-6 leaves the bound satisfied (99th
percentile {q1:.0f}, {q2:.0f}, {q3:.0f} against a bound of {bd:.0f}); on these instances the
condition is not binding, which we report as a negative rather than as support.

## Scale, seeds, limitations
* {S2} seeds for the distributional tests, {S1} for Proposition 4.1, six delta values down to
  0.002 (so the 0.994 quantile is estimated from 4,000 replicates); master seed 20260725.
* **Limitation (material).** Theorem 4.3 is stated for PABLO instantiated with
  *Zhang & Cutkosky (2022, Algorithm 1)*, which is not restated in this paper and was **not**
  re-implemented; we instantiate PABLO with Algorithm 6 of this paper. That base learner exists
  solely to control sum_t ||w_t||^2 in Proposition 4.1, so we measure that quantity directly:
  it stays at {sw:.2g} on the hard family and {sw2:.1f} on the active family. Our test therefore
  confirms the bound's validity and its delta-, T-, d- and ||u||-dependence for a valid PABLO
  instantiation; it cannot rule out instances where the iterates are unstable, which is
  precisely what the substituted algorithm addresses.
* Scripts: `scripts/claim4_highprob.py`, `scripts/claim4_tail_supplement.py`.
""".format(
    claim=CLAIMS[4],
    arxiv=ARXIV,
    S1=c4["T1_proposition_4_1"][0]["seeds"],
    nrows=len(c4["T1_proposition_4_1"]),
    S2=Q["quantiles"]["seeds"],
    nq2=len(Q["quantiles"]["rows"]),
    mrat=max(r["ratio"] for r in Q["quantiles"]["rows"]),
    qrows="\n".join(
        "| %.3f | %.1f | %.1f | %.4f |"
        % (r["delta"], r["quantile_1_minus_3delta"], r["theorem_bound"], r["ratio"])
        for r in Q["quantiles"]["rows"]
        if r["u_norm"] == 4.0
    ),
    slope=Q["quantiles"]["tail_regression_on_sqrt_log_T_over_delta"]["slope"],
    r2=Q["quantiles"]["tail_regression_on_sqrt_log_T_over_delta"]["r_squared"],
    cv=Q["distribution_summary"]["std"] / abs(Q["distribution_summary"]["mean"]),
    eT=EX["T"]["fitted"],
    sT=EX["T"]["stderr"],
    ed=EX["d"]["fitted"],
    sd=EX["d"]["stderr"],
    eu=EX["u_norm"]["fitted"],
    su=EX["u_norm"]["stderr"],
    mw=max(r["max_iterate_norm"] for r in c4s["distribution_rows"]),
    cv2=max(r["coefficient_of_variation"] for r in c4s["distribution_rows"][:2]),
    S3=c4s["distribution_rows"][0]["seeds"],
    v1=c4s["violations_of_theorem_bound"],
    v2=c4s["violations_of_proposition_4_1"],
    r2lo=min(r["tail_fit_r_squared"] for r in c4s["distribution_rows"]),
    r2hi=max(r["tail_fit_r_squared"] for r in c4s["distribution_rows"]),
    q1=c4["T5_varepsilon_boundary_audit"][1]["q_99"],
    q2=c4["T5_varepsilon_boundary_audit"][2]["q_99"],
    q3=c4["T5_varepsilon_boundary_audit"][3]["q_99"],
    bd=c4["T5_varepsilon_boundary_audit"][0]["theorem_bound_delta_0p0033"],
    sw=c4["T1_proposition_4_1"][0]["mean_sum_w_sq"],
    sw2=max(r["mean_sum_w_sq"] for r in c4s["distribution_rows"]),
)
write(SLUGS[4], NAMES[4], [cell("markdown", NAMES[4], p4)])

R5 = c5["T1_T2_rates"]
M5 = c5["T3_noise_variance_mechanism"]
I5 = c5["T4_information_argument"]
p5 = """> **Claim (verbatim).** {claim}

## Verdict: **verified**

A lower bound cannot be *proved* by simulation, so what is reproduced here is the theorem's
construction and its information-theoretic engine, end to end, plus the rate it predicts.

**Construction (part 1 of Theorem 5.2, implemented verbatim).** theta in {{+-Delta}}^d with
Delta = c/sqrt(T); losses l_t = theta + xi_t, xi_t ~ N(0, (2d)^{{-1}} I_d); the learner plays
z_t in the unit Euclidean ball and observes only <l_t, z_t>. Measured quantity: the direction
regret of Eq. (7), R^Z_T = sum_t <z_t, theta> + T||theta|| (comparator u = -theta/||theta||).

### T1 — every algorithm we ran is above the stated floor
Three strong baselines, each *given advantages* (grid-optimised exploration budget / step size,
and the adversary's best Delta selected per algorithm): linear Thompson sampling on the ball,
explore-then-commit with coordinate exploration, and an OSMD-style bandit-gradient learner.

| d | T | empirical minimax envelope | sqrt(dT) | envelope / sqrt(dT) | >= floor sqrt(dT)/64 ^ T/(12d) |
| --- | --- | --- | --- | --- | --- |
{rows5}

### T2 — the rate
Fitted exponents of the empirical minimax envelope: **T^{{{eT:.3f} ± {seT:.3f}}}** (predicted
1/2) and, at fixed T = 4000, **d^{{{ed:.3f} ± {sed:.3f}}}**. The d-exponent overshoots 1/2
because at fixed T the aspect ratio T/d falls from 1000 to 125 and the envelope/sqrt(dT) ratio
drifts from 0.54 to 0.82; sqrt(dT) is the rate in the regime T >> d that the theorem's
T >= 4d assumption points at. Sweeping d at a **fixed aspect ratio T = 500d** (where sqrt(dT)
= sqrt(500) d, so the predicted d-exponent is 1) gives **{eds:.3f} ± {seds:.3f}** with
envelope/sqrt(dT) in [{lo5:.2f}, {hi5:.2f}]:

| d | T = 500d | envelope | sqrt(dT) | ratio |
| --- | --- | --- | --- | --- |
{rows5s}

### T3 — the mechanism the proof sketch names
The sketch attributes the sqrt(dT) rate (rather than d sqrt(T)) to the 1/d noise-variance
constraint. Sweeping sigma^2 with Delta rescaled to the noise level:

| sigma^2 | envelope regret | sigma d sqrt(T) | ratio |
| --- | --- | --- | --- |
{rows5b}

fitted exponent in sigma^2 = **{es:.3f} ± {ses:.3f}** (predicted 1/2, i.e. regret ~ sigma d
sqrt(T)); at sigma^2 = 1/(2d) this is exactly sqrt(dT/2).

### T4 — the KL / Pinsker step, re-derived numerically
For neighbours differing in one coordinate sign, sum_i KL = 2 Delta^2 T / sigma^2 exactly (the
algorithm plays ||z_t|| = 1). Measured along real trajectories:

| Delta * sqrt(T) | mean total KL | closed form | fraction of coordinate signs recovered | regret / sqrt(dT) |
| --- | --- | --- | --- | --- |
{rows5c}

When the total KL is O(d) the signs are recovered at chance level (0.5) and the regret sits at
the sqrt(dT) scale — exactly the trade-off the randomisation-hammer argument exploits.

### T5 — part 2 (bounded losses)
Truncating the losses to ||l_t|| <= 1 preserves the behaviour: envelope / sqrt(dT) =
{trunc} for d = 8, 16, 32, all above the floor.

## Scale, seeds, limitations
* {seeds} seeds per (algorithm, Delta) cell; d in {{4, 8, 16, 32}}, T in {{500 … 8000}} with
  T >= 4d as the theorem assumes; master seed 20260725.
* **Limitation.** "Minimax" is over *all* algorithms; we can only run finitely many, so T1/T2
  establish the floor for the three (advantaged) algorithms tested, not for every algorithm.
  The parts that are genuinely verified rather than sampled are the construction and the
  information argument (T4), which is where the proof's force lies.
* Scripts: `scripts/claim5_lowerbound.py`, `scripts/claim5_supplement.py` · raw:
  `outputs/claim5_lowerbound.json`, `outputs/claim5_supplement.json`.
""".format(
    claim=CLAIMS[5],
    rows5="\n".join(
        "| %d | %d | %.1f | %.1f | %.3f | %s |"
        % (
            r["d"],
            r["T"],
            r["empirical_minimax_envelope"],
            r["sqrt_dT"],
            r["envelope_over_sqrt_dT"],
            "yes" if r["above_theorem_floor"] else "**no**",
        )
        for r in R5["rows"]
    ),
    ed=R5["fitted_d_exponent"],
    sed=R5["stderr_d"],
    eT=R5["fitted_T_exponent"],
    seT=R5["stderr_T"],
    eds=c5s["fitted_d_exponent"],
    seds=c5s["stderr"],
    lo5=min(r["envelope_over_sqrt_dT"] for r in c5s["rows"]),
    hi5=max(r["envelope_over_sqrt_dT"] for r in c5s["rows"]),
    rows5s="\n".join(
        "| %d | %d | %.1f | %.1f | %.3f |"
        % (r["d"], r["T"], r["empirical_minimax_envelope"], r["sqrt_dT"],
           r["envelope_over_sqrt_dT"])
        for r in c5s["rows"]
    ),
    rows5b="\n".join(
        "| %.4g | %.1f | %.1f | %.3f |"
        % (r["sigma_sq"], r["envelope_regret"], r["sigma_d_sqrtT"], r["ratio"])
        for r in M5["rows"]
    ),
    es=M5["fitted_sigma_sq_exponent"],
    ses=M5["stderr"],
    rows5c="\n".join(
        "| %.2f | %.1f | %.1f | %.3f | %.3f |"
        % (
            r["Delta_coefficient"],
            r["mean_total_KL"],
            r["closed_form_2Delta2T_over_sigma2"],
            r["mean_fraction_of_signs_recovered"],
            r["regret_over_sqrt_dT"],
        )
        for r in I5["rows"]
    ),
    trunc=", ".join(
        "%.3f" % r["over_sqrt_dT"] for r in c5["T5_truncated_bounded_losses"]
    ),
    seeds=R5["seeds"],
)
write(SLUGS[5], NAMES[5], [cell("markdown", NAMES[5], p5)])

A6 = c6["T1_achievability_shape"]
p6 = """> **Claim (verbatim).** {claim}

## Verdict: **toy** — deliberately, and this is the honest label

Conjecture 5.3 is an **open problem**: the paper states it and explicitly declines to prove it.
No simulation can establish the Omega direction, and none is claimed here. What follows is
numerical evidence about the conjectured *functional form*, on synthetic instances, plus an
executable version of the obstruction the paper describes.

### 1. Does the conjectured shape describe the worst case we can build?
For each ||u|| we take the maximum measured E[R_T(u)] over a battery of 10 loss families
(minimax-hard hypercube, coordinate-Rademacher, nine sign-flipping variants, a 1-D
Streeter-McMahan geometry), T = 4000, {S} seeds, and divide by ||u|| sqrt(T (d v log||u||)):

| d | ||u|| range | min ratio | max ratio | spread | slope of ratio vs ||u|| (log-log) |
| --- | --- | --- | --- | --- | --- |
{rows6}

The ratio stays in **[{lo:.2f}, {hi:.2f}]** across seven orders of magnitude of ||u|| and
d in {{2, 4, 8}} — the conjectured form is the right envelope to within a constant — **but it
decreases**: our oblivious battery realises ||u|| sqrt(dT) and does **not** realise the
log||u|| growth. That is the expected signature of the log factor requiring an *adaptive*
adversary (the paper's Theorem 5.1 is a Streeter-McMahan-type bound whose hard sequence is built
against the learner), and it is reported here as a negative result, not as support.

### 2. The obstruction, made executable
The paper argues the two partial lower bounds do not combine, because on a direction-hard
sequence "nothing prevents the scale regret R^V_T from being large and negative". We compute
the Eq. (7) decomposition R_T(u) = R^V_T(||u||) + ||u|| R^Z_T(u/||u||) along real trajectories
(identity residual <= {res:.1e}):

| instance | d | R^Z_T / sqrt(dT) | R^V_T at ||u||=10^4 |
| --- | --- | --- | --- |
{rows6b}

On the Theorem-5.2 direction-hard instance at d = 16 the direction regret is
{rz:.2f} sqrt(dT) while the scale regret is **negative** ({rv:.1f}) — precisely the
cancellation that blocks the naive combination of the two bounds. On the scale-hard 1-D
sequence the direction regret collapses to {rz2:.2f} sqrt(dT). The two hard instances are
genuinely different instances.

### 3. Falsification probe
{np} (instance, d, ||u||) cells were probed for a ratio growing above the conjectured rate; the
largest ratio observed is **{mx:.3f}** (d = {mxd}, {mxi}), i.e. a constant, with no growing
trend. Nothing in our battery falsifies the conjecture, and nothing in it can prove it.

## Scale, seeds, limitations
* {S} seeds per instance, T = 4000, d in {{2, 4, 8, 16}}, ||u|| from 1 to 10^7; master seed
  20260725.
* **Blocker for a higher verdict:** the claim is an open conjecture. The Omega direction
  requires a proof; the O direction for the specific coin-bettor + OSMD combination is
  Eq. (5) of the paper, which is a corollary of results we do verify elsewhere, but the
  minimax statement is not decidable numerically.
* Script: `scripts/claim6_conjecture.py` · raw: `outputs/claim6_conjecture.json`.
""".format(
    claim=CLAIMS[6],
    S=A6["seeds"],
    rows6="\n".join(
        "| %s | 1 … 10^7 | %.3f | %.3f | %.2f | %+.3f |"
        % (
            k,
            v["min_ratio"],
            v["max_ratio"],
            v["spread"],
            v["fitted_slope_of_ratio_vs_u_norm"],
        )
        for k, v in A6["flatness_summary"].items()
    ),
    lo=min(v["min_ratio"] for v in A6["flatness_summary"].values()),
    hi=max(v["max_ratio"] for v in A6["flatness_summary"].values()),
    res=max(r["identity_residual"] for r in c6["T2_scale_direction_decomposition"]),
    rows6b="\n".join(
        "| %s | %d | %.3f | %.1f |"
        % (r["instance"], r["d"], r["R_Z_over_sqrt_dT"], r["scale_regret_R_V"])
        for r in c6["T2_scale_direction_decomposition"]
        if r["u_norm"] == 1e4
    ),
    rz=[
        r
        for r in c6["T2_scale_direction_decomposition"]
        if r["d"] == 16 and r["instance"].startswith("theorem")
    ][0]["R_Z_over_sqrt_dT"],
    rv=[
        r
        for r in c6["T2_scale_direction_decomposition"]
        if r["d"] == 16 and r["instance"].startswith("theorem") and r["u_norm"] == 1e4
    ][0]["scale_regret_R_V"],
    rz2=[
        r
        for r in c6["T2_scale_direction_decomposition"]
        if r["d"] == 16 and r["instance"].startswith("scale")
    ][0]["R_Z_over_sqrt_dT"],
    np=c6["T3_falsification_probe"]["instances_probed"],
    mx=c6["T3_falsification_probe"]["max_ratio"],
    mxd=c6["T3_falsification_probe"]["worst_case"]["d"],
    mxi=c6["T3_falsification_probe"]["worst_case"]["instance"],
)
write(SLUGS[6], NAMES[6], [cell("markdown", NAMES[6], p6)])

# ---------------------------------------------------------------------------- conclusion
concl_md = """## Outcome

| # | Claim | Verdict | Key number |
| --- | --- | --- | --- |
| 1 | PABLO reduces uBLO to OLO (Sec. 3) | **verified** | exhaustive check of Prop. 2.1 over 2,400 configs, max rel. error {e1:.1e} |
| 2 | Thm 3.1 expected static regret, kappa gap | **verified** | fitted d-exponent {ed:.3f} ± {sd:.3f} (kappa = sqrt(d) branch) |
| 3 | Thm 3.3 sqrt(P_T) without prior knowledge | **verified** | R_T^2 affine in P_T, r^2 = {r2:.4f} |
| 4 | Thm 4.2 (= Thm 4.3 in v2) high-probability | **verified** | 0 violations in {nq} quantile tests, 4,000 seeds |
| 5 | Thm 5.2 Omega(sqrt(dT)) on the unit ball | **verified** | envelope/sqrt(dT) in [0.50, 0.82], T-exponent {e5T:.3f}, all above the floor |
| 6 | Conjecture 5.3 (open problem) | **toy** | ratio to conjectured rate in [{lo:.2f}, {hi:.2f}], slope {sl:+.3f} |

Two findings we would not have predicted from the paper: the norm-adaptive (kappa = 1) branch of
Theorem 3.1 is **not tight** on any instance we could build (an adversary choosing ||u|| after
the trajectory gains a factor 1.000, not sqrt(d)); and Theorem E.7's constant is dominated by
its own lower-order additive term until T ~ 10^7, so the sqrt(P_T) main term is not the binding
part of the guarantee at any horizon one can simulate.

## Download the reproduction bundle & rerun

**Bucket:** `hf://buckets/SabaPivot/repro-pablo-bandits-artifacts` —
[browse](https://huggingface.co/buckets/SabaPivot/repro-pablo-bandits-artifacts)
(`scripts/`, `outputs/` raw JSON, `figs/`).

```bash
hf buckets sync hf://buckets/SabaPivot/repro-pablo-bandits-artifacts ./pablo-repro
pip install numpy scipy matplotlib
python scripts/claim1_reduction.py        # Prop 2.1 (exhaustive), Cor 2.2 + boundary audit, reduction identity
python scripts/claim2_static.py           # Theorem 3.1: exponents in T, d, ||u||; kappa mechanism; norm-adaptive adversary
python scripts/claim3_dynamic.py          # Theorems E.6/E.7 + Theorem 3.3: sqrt(P_T) with P_T withheld
python scripts/claim4_highprob.py         # Proposition 4.1 + Theorem 4.3 quantiles
python scripts/claim4_tail_supplement.py  # the same, on instances where the iterate is active
python scripts/claim5_lowerbound.py       # Theorem 5.2 construction, rate, noise mechanism, KL argument
python scripts/claim5_supplement.py       # the d-exponent at a fixed aspect ratio T = 500 d
python scripts/claim6_conjecture.py       # Conjecture 5.3 probes (open problem)
python scripts/make_figures.py            # the four poster figures
```
Everything is CPU-only (numpy, no GPU, no network) and took about 1.5 h wall-clock in total on a
heavily loaded shared machine; every RNG seed is derived from the master seed 20260725 and is
recorded in the JSON outputs.

Paper: [arXiv {arxiv}](https://arxiv.org/abs/{arxiv}) ·
[OpenReview](https://openreview.net/forum?id={orid}).
**No official code exists** — no repository is linked in the PDF, on the arXiv abstract page, or
on the OpenReview forum; `scripts/pablo.py`, `scripts/alg5.py` and `scripts/batch.py` are an
independent re-implementation from the pseudocode of Algorithm 1, Eq. (4), Algorithm 5 and
Algorithm 6.
""".format(
    e1=c1["t1_proposition_2_1_exhaustive"]["max_rel_err_unbiasedness"],
    ed=B["d_sweep"]["fitted_exponent"],
    sd=B["d_sweep"]["stderr"],
    r2=reg["r_squared"],
    nq=len(Q["quantiles"]["rows"]) + len(c4s["quantiles"]),
    e5d=R5["fitted_d_exponent"],
    e5T=R5["fitted_T_exponent"],
    lo=min(v["min_ratio"] for v in A6["flatness_summary"].values()),
    hi=max(v["max_ratio"] for v in A6["flatness_summary"].values()),
    sl=A6["flatness_summary"]["d=2"]["fitted_slope_of_ratio_vs_u_norm"],
    arxiv=ARXIV,
    orid=ORID,
)

write(
    "conclusion",
    "Conclusion",
    [
        cell(
            "artifact",
            "Reproduction bundle",
            "**\U0001F4E6 Artifact** `pablo-bandits-repro/repro-bundle:v0` \u00b7 dataset "
            "\u00b7 scripts + raw JSON + figures\n\n"
            "https://huggingface.co/buckets/SabaPivot/repro-pablo-bandits-artifacts",
            extra={"artifact_type": "dataset"},
        ),
        cell("markdown", "Download & rerun", concl_md),
    ],
)

print("logbook written")