Regret without Optimal-Arm Feedback under Reward-Dependent Delays
Organizations: Department of Biomedical Engineering, College of Design and Engineering, National University of Singapore
Abstract
We study stochastic bandits with reward-dependent delays, possibly infinite, whose reports omit the originating round. For each , Balanced Historical Optimism (BHO) has a delay term controlled by the largest suboptimal-arm quantile at level , without requiring optimal-arm reports. Lower bounds give an inverse-square slack cost in the logarithmic statistical regime and linear minimax regret at . A family with growing forces worst-case regret for every learner, where is the largest gap-weighted suboptimal cutoff. Pending-triggered balance preserves BHO's weighted-cutoff bound for and attains the historical-greedy exploration coefficient with deterministic rewards, a unique optimum and fixed bounded delays. Gap-weighted comparisons and experiments show when shared waiting helps and what balanced exploration costs.
Figures & tables
| Result | Statistical term | Delay term | Optimal arm; assumptions/proof |
|---|---|---|---|
| OPSE (L21, Thm. 5) | Finite ; proved there | ||
| PSE (L21, Thm. 3) | No optimal-arm cutoff; reward-independent delays | ||
| Optimistic-UCB (L21, Eq. 8) | Unrestricted; stated without expanded proof | ||
| BHO (Theorems 1–2) | or | Unrestricted; Apps. A–B, M | |
| RATE (Proposition 1) | Unrestricted; App. Q | ||
| NC-lean (Theorem 3) | Two full bounds in (10) | Unrestricted; same-run proof, App. R |
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
| World and arm | Mass at | Mass at | Infinite-delay mass and its latent reward |
|---|---|---|---|
| , arm 1 | , reward 1 | ||
| , arm | , reward 0 | ||
| , arm 1 | , reward 0 | ||
| , arm | , reward 1 | ||
| , arm | , reward 0 |
| Table O.1. Environment key, grouped by identical coordinates. A0/A2048: all optimal rewards after 0/2048. N: none. Z/R: immediate zeros/successes only. Bad laws F/I/S hide failures/independent outcomes/successes. Ranges denote consecutive cells; varying entries follow ascending cell order. Each Z01–Z59 appears once: 25 RI (reward independent), 32 stress (reward dependent), 2 NC (outside positive slack). | |||||||
|---|---|---|---|---|---|---|---|
| Cell | K | Optimum | Bad d | Bad p | Missing law | Slow bad q | Scope |
| Z01–Z03 | 8 | A0 | 0, 512, 2048 | 0 | – | 7 | RI |
| Z04 | 8 | A0 | 2048 | 1/8 | F | 7 | stress |
| Z05 | 8 | A0 | 2048 | 1/8 | I | 7 | RI |
| Z06 | 8 | A0 | 2048 | 1/8 | S | 7 | stress |
| Z07–Z09 | 8 | A0 | 8192, 32768, 65536 | 0 | – | 7 | RI |
| Table O.2. Selected endpoint means (seed SE). The uniform reference is 57344 for and 64512 for . † marks a mean at least 90% of the reference. In Z06=Z03 only BHO, BHO-half, G and OUCB-current share the Z03 trajectory (O.5). | |||||||
|---|---|---|---|---|---|---|---|
| Cell | BHO | BHO-half | G | OUCB-current | OPSE | PSE | SE |
| Z04 | 8114.33 (58.33) | 5062.64 (47.92) | 10411.75 (123.73) | 7451.98 (47.65) | 15748.90 (150.81) | 15264.75 (994.52) | 6169.62 (104.84) |
| Z05 | 4215.47 (40.17) | 2823.82 (28.02) | 4111.38 (255.94) | 7603.00 (116.72) | 8411.53 (88.93) | 6956.94 (4.51) | 3372.07 (44.85) |
| Z06=Z03 | 2824.43 (25.95) | 2101.40 (24.39) | 1442.77 (35.31) | 4602.12 (207.44) | 5571.27 (60.03) | 6662.96 (84.33) | 2157.53 (24.64) |
| Z37 | 36378.52 (57.30) | 29778.04 (37.93) | 27083.14 (59.79) | 26962.15 (48.17) | 43873.83 (405.66) | 64759.04 (0.03)† | 26530.48 (337.80) |
| Z40 | 64220.10 (16.18)† | 63864.50 (27.04)† | 58227.19 (103.82)† | 46789.69 (173.70) | 64511.99 (0.01)† | 64768.00 (0.00)† | 37173.82 (355.16) |
| Table O.3. Selected primary intervals with favorable and unfavorable results. All intervals use the same nominal Bonferroni-t calibration with p=118; the complete family is supplied in the data archive. | |||
|---|---|---|---|
| Cell | Contrast | Mean difference | Primary 95% interval |
| Z19 | BHO-minus-PSE | -56626.02 | [-56856.66, -56395.39] |
| Z19 | BHO-minus-SE | -57234.80 | [-57464.69, -57004.90] |
| Z53 | BHO-minus-PSE | -224.42 | [-243.69, -205.16] |
| Z53 | BHO-minus-SE | -895.49 | [-903.80, -887.19] |
| Z58 | BHO-minus-PSE | -225.05 | [-243.53, -206.56] |
| Table O.4. Descriptive total-regret comparisons with G, OUCB and OPSE. Counts of cells with lower/equal unrounded BHO mean over 32 seeds; the remainder have higher BHO means. Optimum-reporting groups cover all 59 environments. The fixed-optimum group differs from the 25-cell reward-independent subset because some bad-arm laws depend on reward. | ||||
|---|---|---|---|---|
| Optimum reporting law | Cells | Versus G | Versus OUCB | Versus OPSE |
| All outcomes, fixed delay | 25 | 8 / 0 | 11 / 0 | 25 / 0 |
| Never reports | 8 | 0 / 0 | 4 / 0 | 8 / 0 |
| Only zeros report | 24 | 9 / 0 | 14 / 0 | 23 / 1 |
| Only successes report | 2 | 0 / 2 | 0 / 2 | 0 / 2 |
| Family and calibration | Negative | Positive | Includes zero | Zero sample variance |
|---|---|---|---|---|
| Total regret, Bonferroni-t primary | 96 | 18 | 4 | 2 |
| Total regret, fixed-SE max-z sensitivity | 96 | 19 | 3 | 2 |
| Delay excess, Bonferroni-t primary | 8 | 96 | 36 | 20 |
| Delay excess, fixed-SE max-z sensitivity | 9 | 97 | 34 | 20 |
| Table O.5. Selected returned-UCB endpoints and paired contrasts. Mean pseudo-regret (seed SE) and percentage of uniform regret. The final columns give BHO minus returned-UCB, mean (paired seed SE), and the nominal 95% interval in the full 59-contrast family. Positive differences favor returned-UCB. The rows cover three all-report cells, never-report cells at both arm counts, and zeros-only cells including Z53 and Z58. The data archive provides all 59 rows. | ||||
|---|---|---|---|---|
| Cell | Returned-UCB | Percent of uniform | BHO − returned-UCB | Primary interval |
| Z01 | 646.47 (9.60) | 1.13 | 1461.89 (16.68) | [1400.26, 1523.53] |
| Z09 | 65535.20 (0.03) | 114.28 | -20914.85 (281.26) | [-21953.93, -19875.77] |
| Z12 | 464.91 (26.76) | 0.81 | 940.62 (27.12) | [840.42, 1040.82] |
| Z19 | 65467.12 (1.21) | 114.17 | -57352.79 (57.96) | [-57566.92, -57138.66] |
| Z31 | 32260.34 (17.65) | 50.01 | -12588.10 (61.71) | [-12816.09, -12360.11] |
| Table T.1. Fixed models. The last column is exact empirical accuracy on the 1,797-record test table, displayed to six decimals. Full constructor parameters and preprocessing are supplied in the data archive. | ||||
|---|---|---|---|---|
| Arm | Classifier and main fixed parameters | Calibration errors/769 | Test correct/1797 | |
| M0 | Multinomial logistic regression: L2, C=1, lbfgs, tol=1e-4, max_iter=1000 , intercept | 19 | 1694 | 0.942682 |
| M1 | Five Euclidean neighbors, uniform weights; deterministic distance/vote ties | 8 | 1752 | 0.974958 |
| M2 | CART: gini, best splitter, depth 6, min_samples_leaf=5 , seed 20261029 | 154 | 1348 | 0.750139 |
| M3 | Gaussian naive Bayes: training-set class priors, var_smoothing=1e-9 | 139 | 1412 | 0.785754 |
| Table T.2. Normalized cumulative pseudo-regret, mean±seed SE across 32 paired seeds. Both quantities are divided by ; smaller values are better. Values are rounded, with small nonzero SEs shown in scientific notation. | |||||||
|---|---|---|---|---|---|---|---|
| Channel/T | NC-lean | BHO | BRB | OPSE | SE | returned-UCB | Uniform |
| E0/4,096 | 0.998±0.003 | 0.951±0.006 | 0.998±5e-05 | 1.000±0 | 1.000±0 | 0.269±0.004 | 0.998±0.003 |
| E0/16,384 | 0.754±0.008 | 0.391±0.003 | 1.000±1e-05 | 0.525±0.005 | 0.525±0.005 | 0.137±0.002 | 0.998±0.001 |
| E1/4,096 | 0.998±0.003 | 0.953±0.006 | 0.998±5e-05 | 1.000±0 | 1.000±0 | 0.275±0.004 | 0.998±0.003 |
| E1/16,384 | 0.754±0.008 | 0.395±0.003 | 1.000±1e-05 | 0.530±0.005 | 0.525±0.005 | 0.138±0.002 | 0.998±0.001 |
| E2/4,096 | 0.998±0.003 | 0.969±0.005 | 0.998±5e-05 | 1.000±0 | 1.000±0 | 0.342±0.007 | 0.998±0.003 |
| Table T.3. Channels E4 and E4b: normalized cumulative pseudo-regret, mean±seed SE across 32 paired seeds, rounded as in Table T.2. Rows give channel, (.05 for 0.05) and . Descriptive; no simultaneous family is formed. | |||||||
|---|---|---|---|---|---|---|---|
| Channel/ /T | NC-lean | BHO | BRB | OPSE | SE | returned-UCB | Uniform |
| E4/0/4,096 | 0.998±0.003 | 0.969±0.005 | 0.998±5e-05 | 1.000±0 | 1.019±0.006 | 0.521±0.008 | 0.998±0.003 |
| E4/0/16,384 | 0.774±0.012 | 0.407±0.003 | 1.000±1e-05 | 0.704±0.010 | 0.783±0.009 | 0.385±0.003 | 0.998±0.001 |
| E4/0/65,536 | 0.316±0.005 | 0.189±0.001 | 1.000±0 | 0.302±0.002 | 0.429±0.002 | 0.320±0.001 | 1.000±0.001 |
| E4/.05/4,096 | 0.998±0.003 | 0.969±0.005 | 0.998±5e-05 | 1.000±0 | 1.000±0 | 0.414±0.008 | 0.998±0.003 |
| E4/.05/16,384 | 0.774±0.012 | 0.407±0.003 | 1.000±1e-05 | 0.704±0.010 | 0.714±0.009 | 0.347±0.003 | 0.998±0.001 |
Multi-Armed Bandits
Multi-Armed Bandits study how to choose among uncertain actions over time while balancing immediate rewards with learning.
See all 377 papers