How statement and proof provenance work
The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.
- Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
- AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
- AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.
These labels describe origin, not correctness: citations and verification chips remain separate evidence.
The conditional Gaussian mixture is a nonnegative supermartingale
Statement
Assume AC and Countable Choice and the finite-dimensional linear contextual bandit model. Put , , and . Let be the information after round has been observed. Then
is a nonnegative integrable supermartingale with respect to .
Statement references
Facts & Assumptions
Given: AC, Countable Choice, the model's predictable feature vectors and conditional MGF bounds, and the matrix sums in the Statement.
The Axiom of Choice: every family of nonempty sets has a choice function; it supplies the conditional-expectation existence and supermartingale interfaces used here.
The Axiom of Countable Choice (): every countable family of nonempty sets has a choice function; it is the exact choice premise of the Gaussian integral and Lebesgue change-of-variables suppliers.
Finite-dimensional linear contextual bandit model: is -measurable, , and for each real .
Conditional sub-Gaussian bounds allow bounded predictable coefficients: for bounded -measurable , almost surely.
The ridge information matrix is positive definite and invertible: is symmetric positive definite and .
Conditional expectation given a sigma algebra, Conditional expectation as an ae class, Conditional expectation exists by radon nikodym, and Martingale submartingale and supermartingale: conditional-expectation versions are measurable and integrable and have the same integrals as the conditioned variable on every event in the conditioning sigma-algebra; a supermartingale is an integrable adapted process whose next conditional-expectation class is at most its current value. The existence and supermartingale interfaces use AC.
Basic algebra and order properties of conditional expectation: conditional expectation is linear and order preserving, preserves total expectation, and contracts .
Monotone convergence for the integral: increasing nonnegative measurable functions pass to the limit under the integral.
Gaussian integral for a positive-definite quadratic form: for symmetric positive-definite , under Countable Choice.
A C^1 diffeomorphism satisfies the change-of-variables formula for nonnegative Lebesgue measurable functions: a diffeomorphism changes a nonnegative Lebesgue integral by the absolute Jacobian determinant; translations have Jacobian determinant .
Tonelli's theorem for nonnegative measurable functions on a sigma-finite product: for a nonnegative product-measurable function on sigma-finite spaces, the iterated integrals equal the product integral and the section integrals are measurable.
The product sigma-algebra and its finite iterates, A measurable function between measurable spaces, The vector space of by matrices over a field, with entrywise operations, The Borel sigma-algebra of a topological space, A continuous map has Borel preimages of Borel sets, and Closure properties of measurable functions used by the integral: finite-coordinate measurable maps, continuous polynomial/exponential operations, and their compositions are measurable on the relevant finite product spaces.
Proof
For fixed , define , , and where . The model makes -measurable and, by [F3], bounds . Thus [F2] gives and [F6] gives . Also , and is -measurable.
For fixed , each coordinate of and is a finite sum and product of variables observed by time . On , the projections from each factor are measurable, so each coordinate of , , and is measurable. The Borel sigma-algebra of the finite-dimensional Euclidean product is generated by coordinate projections, since rational open boxes form a countable basis; hence is measurable. The maps and are continuous, so is product-measurable by [F11]. Tonelli's section-measurability clause [F10] therefore makes -measurable. The density is nonnegative and integrates to by [F8] with .
By the definitions of and the Gaussian density, Completing the square gives
For fixed and every , step 1.1 and the defining event integrals [F5] give . Hence for any nonnegative finite-valued -measurable , summing these inequalities gives . For a bounded nonnegative -measurable , the finite-valued dyadic approximants increase to . Since , monotone convergence [F7] on both sides gives the same inequality for .
Induct on to prove integrability and the supermartingale inequality. The base is integrable. If is integrable, put , a bounded nonnegative -measurable variable. Step 2.1 gives . Since , [F7] gives . Replacing by for any and applying [F7] again gives . Let be a conditional-expectation version of given , which exists by [A1] and [F5]. For each , . On , the event-integral property in [F5] and the preceding inequality imply whereas the definition of makes the left side at least the right side plus . Thus for every ; since , we have almost surely. This is the supermartingale conditional-expectation inequality.
For any , Tonelli [F10] and step 3.1 give Taking shows is integrable. Let be a conditional-expectation version of given ; it exists by [A1] and [F5]. For each , . The event-integral property [F5] and the displayed event inequality imply while the definition of makes the left side at least the right side plus . Thus every is null and almost surely. Together with adaptedness from step 1.2 and , this is the integrable supermartingale property.
The translation is a diffeomorphism with Jacobian determinant , so [F9] and [F8] evaluate the last integral as . Since by [F12], this gives Thus the process in the Statement is the supermartingale established in step 4.1.
Depends on
- The Axiom of Choice
- Conditional expectation given a sigma algebra
- The Borel sigma-algebra of a topological space
- Conditional expectation as an ae class
- The Axiom of Countable Choice ($\mathrm{AC}_\omega$)
- Finite-dimensional linear contextual bandit model
- Martingale submartingale and supermartingale
- The vector space $M_{m \times n}(F) := F^{\,m \times n}$ of $m$ by $n$ matrices over a field, with entrywise operations
- A measurable function between measurable spaces
- The product sigma-algebra and its finite iterates
- Conditional sub-Gaussian bounds allow bounded predictable coefficients
- The ridge information matrix is positive definite and invertible
- Gaussian integral for a positive-definite quadratic form
- Closure properties of measurable functions used by the integral
- Basic algebra and order properties of conditional expectation
- A C^1 diffeomorphism satisfies the change-of-variables formula for nonnegative Lebesgue measurable functions
- Conditional expectation exists by radon nikodym
- A continuous map has Borel preimages of Borel sets
- Cauchy-Schwarz $\lvert\langle x,y\rangle\rvert \le \lVert x\rVert_2\lVert y\rVert_2$ with its equality case, the triangle inequality for $\lVert\cdot\rVert_2$, the parallelogram law and polarisation
- The determinant of a triangular matrix is the product of its diagonal entries
- Monotone convergence for the integral
- Tonelli's theorem for nonnegative measurable functions on a sigma-finite product
Used by
Dependency tree · two levels
120 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.
Sources
- Tor Lattimore and Csaba Szepesvári, Bandit Algorithms (standard reference, not scraped)
- Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári, Online Least Squares Estimation with Self-Normalized Processes: An Application to Bandit Problems (standard reference, not scraped)