Lemma 4 — Conversion of estimated reach weights
DisprovedGaoCascadePricing.UCB.lemma_4bandit-algorithmscascade-click-modelp2o-gran-per-chapterp2o-plan-paperp2o-v1regret
Fix a positive finite market, a valid stationary cascade and any resolution of UCB-Cascade. For every initialized history of positive probability at calendar time , and every given price vector , let be the sum of the four printed bonuses and let and be the empirical and true continuation probabilities at . Then the source asserts
There is no good-event premise and need not maximize the objective. The zeta bonus remains uncapped. This is the printed assertion; the recorded source counterexample is not repaired in the target.
Differences from the source:
- encoding: products 1 through J and price labels 1 through K → zero-based finite indices with positive J and K; reason: the finite index sets are in bijection and every feasible vector is retained
- reading: monetary price points → nonnegative real prices in strictly increasing order; reason: the standing economic price convention is made explicit
- encoding: expectation over customer movements and external policy randomization → normalized action PMFs and finite sums of products of conditional path weights; reason: the paper has finite action and observation spaces, so this is the exact finite-horizon law
- reading: keep testing and select a UCBOPT solution, without specifying the choices → every history-dependent randomized testing rule and every maximizing tie rule, fixed before the unknown parameters; reason: the statement must cover the full underspecified algorithm rather than a favorable choice
- encoding: a period with defined empirical estimates → an initialized public history of positive trajectory probability at time n+1; reason: this is the domain of the printed ratios on realizable histories and imposes no confidence condition
- reading: the shorthand true parameter theta_t → the fixed stationary true parameter theta; reason: the model has no time-varying environment
Preamble
import Definitions.Def_GaoCascadePricing_UCB_EstimationEvent
Formal statement
namespace GaoCascadePricing.UCB
theorem lemma_4 {J K : ℕ} (M : Market J K)
(π : Policy J K) (hπ : IsUCBCascade M π)
(θ : Cascade J K) (hθ : θ.Valid) (n : ℕ) (h : History J K n)
(hpossible : 0 < historyWeight θ π h) (hinit : Initialized h) (p : Action J K) :
weightedBonus (estimate h) h p ≤ 4 * (J : ℝ) * weightedBonus θ h p := by sorry
end GaoCascadePricing.UCB
Source
Gao, Jasin, Najafi and Zhang (2022), Joint Learning and Optimization for Multi-Product Pricing (and Ranking) Under a General Cascade Click Model, DOI https://doi.org/10.1287/mnsc.2021.4246; published basis, supplied manuscript-paginated PDF; Lemma 4, PDF = printed p. 17; SHA256 e199fc0dfffccf57ac4a59ae46b7a8342a11c3dd3db189795d3a5028b566b1b6
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.