Revealing After Overwriting: An Exponential POMDP OPE Lower Bound under History-Dependent Logging

Abstract:Multi-step revealing can make off-policy evaluation tractable under memoryless logging. With history-dependent logging, state decodability and target-relevant evidence can separate. For every horizon $H\ge3$, we construct two exactly realizable POMDPs with four actions, at most four states per layer, a known logger, and a memoryless target. Action overlap, history coverage, and observation-only revealing remain bounded independently of $H$, yet the target values differ by $1/2$ and the KL divergence between the logged laws is $\Theta(4^{-(H-1)})$, forcing exponential sample complexity. Logger memory makes states distinguishable, while reset erases the model-distinguishing evidence preserved by the target. A separate construction retains this barrier with common, known observation-only revealing operators. Under action and history coverage, we give a finite-class OPE guarantee using common observable value representations that remain valid at every history. The sample bound depends polynomially on their second-moment cost. In the common-operator construction, the same value direction has constant marginal decoding cost but exponential history-conditioned cost. Finally, on a fixed four-action continuum, we derive matching passive and budgeted readout rates. With one known channel and unit read cost, early reads are optimal. With unknown sensor bias, early reads alone remain exponentially costly. Combining them with post-reset calibration gives sample complexity independent of $H$ when both read types receive fixed positive expected budgets per trajectory.

Machine Learning (cs.LG)

arXiv:2610.05063 [cs.LG]

(or arXiv:2610.05063v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2610.05063 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

calibration_code/README.md

calibration_code/code/check_package.py

calibration_code/code/full_log_experiment.py

calibration_code/code/plot_fair_comparison.py

calibration_code/code/run_fair_comparison.py

calibration_code/code/verify_calibration_bounds.py

calibration_code/code/verify_unknown_bias.py

calibration_code/experiments/fair_protocol.md

calibration_code/figures/calibration_equal_budget.pdf

calibration_code/figures/calibration_equal_budget.png

calibration_code/figures/calibration_sensitivity.pdf

calibration_code/figures/calibration_sensitivity.png

calibration_code/outputs/calibration_bounds_checks.json

calibration_code/outputs/environment.json

calibration_code/outputs/fair_category_metadata.json

calibration_code/outputs/fair_manifest.json

calibration_code/outputs/fair_replicates.csv

calibration_code/outputs/fair_run_checks.json

calibration_code/outputs/fair_scipy_validation.json

calibration_code/outputs/fair_solver_tests.json

calibration_code/outputs/fair_summary.csv

calibration_code/outputs/figure_checks.json

calibration_code/outputs/full_log_sufficiency_checks.json

calibration_code/outputs/horizon_H10_n20000_early_calibration_center.npy

calibration_code/outputs/horizon_H10_n20000_early_calibration_confounded_minus.npy

calibration_code/outputs/horizon_H10_n20000_early_calibration_confounded_plus.npy

calibration_code/outputs/horizon_H10_n20000_early_calibration_nonconfounded.npy

calibration_code/outputs/horizon_H10_n20000_early_only_center.npy

calibration_code/outputs/horizon_H10_n20000_early_only_confounded_minus.npy

calibration_code/outputs/horizon_H10_n20000_early_only_confounded_plus.npy

calibration_code/outputs/horizon_H10_n20000_early_only_nonconfounded.npy

calibration_code/outputs/horizon_H3_n20000_early_calibration_center.npy

calibration_code/outputs/horizon_H3_n20000_early_calibration_confounded_minus.npy

calibration_code/outputs/horizon_H3_n20000_early_calibration_confounded_plus.npy

calibration_code/outputs/horizon_H3_n20000_early_calibration_nonconfounded.npy

calibration_code/outputs/horizon_H3_n20000_early_only_center.npy

calibration_code/outputs/horizon_H3_n20000_early_only_confounded_minus.npy

calibration_code/outputs/horizon_H3_n20000_early_only_confounded_plus.npy

calibration_code/outputs/horizon_H3_n20000_early_only_nonconfounded.npy

calibration_code/outputs/horizon_H4_n20000_early_calibration_center.npy

calibration_code/outputs/horizon_H4_n20000_early_calibration_confounded_minus.npy

calibration_code/outputs/horizon_H4_n20000_early_calibration_confounded_plus.npy

calibration_code/outputs/horizon_H4_n20000_early_calibration_nonconfounded.npy

calibration_code/outputs/horizon_H4_n20000_early_only_center.npy

calibration_code/outputs/horizon_H4_n20000_early_only_confounded_minus.npy

calibration_code/outputs/horizon_H4_n20000_early_only_confounded_plus.npy

calibration_code/outputs/horizon_H4_n20000_early_only_nonconfounded.npy

calibration_code/outputs/horizon_H5_n20000_early_calibration_center.npy

calibration_code/outputs/horizon_H5_n20000_early_calibration_confounded_minus.npy

calibration_code/outputs/horizon_H5_n20000_early_calibration_confounded_plus.npy

calibration_code/outputs/horizon_H5_n20000_early_calibration_nonconfounded.npy

calibration_code/outputs/horizon_H5_n20000_early_only_center.npy

calibration_code/outputs/horizon_H5_n20000_early_only_confounded_minus.npy

calibration_code/outputs/horizon_H5_n20000_early_only_confounded_plus.npy

calibration_code/outputs/horizon_H5_n20000_early_only_nonconfounded.npy

calibration_code/outputs/horizon_H6_n20000_early_calibration_center.npy

calibration_code/outputs/horizon_H6_n20000_early_calibration_confounded_minus.npy

calibration_code/outputs/horizon_H6_n20000_early_calibration_confounded_plus.npy

calibration_code/outputs/horizon_H6_n20000_early_calibration_nonconfounded.npy

calibration_code/outputs/horizon_H6_n20000_early_only_center.npy

calibration_code/outputs/horizon_H6_n20000_early_only_confounded_minus.npy

calibration_code/outputs/horizon_H6_n20000_early_only_confounded_plus.npy

calibration_code/outputs/horizon_H6_n20000_early_only_nonconfounded.npy

calibration_code/outputs/horizon_H7_n20000_early_calibration_center.npy

calibration_code/outputs/horizon_H7_n20000_early_calibration_confounded_minus.npy

calibration_code/outputs/horizon_H7_n20000_early_calibration_confounded_plus.npy

calibration_code/outputs/horizon_H7_n20000_early_calibration_nonconfounded.npy

calibration_code/outputs/horizon_H7_n20000_early_only_center.npy

calibration_code/outputs/horizon_H7_n20000_early_only_confounded_minus.npy

calibration_code/outputs/horizon_H7_n20000_early_only_confounded_plus.npy

calibration_code/outputs/horizon_H7_n20000_early_only_nonconfounded.npy

calibration_code/outputs/horizon_H8_n20000_early_calibration_center.npy

calibration_code/outputs/horizon_H8_n20000_early_calibration_confounded_minus.npy

calibration_code/outputs/horizon_H8_n20000_early_calibration_confounded_plus.npy

calibration_code/outputs/horizon_H8_n20000_early_calibration_nonconfounded.npy

calibration_code/outputs/horizon_H8_n20000_early_only_center.npy

calibration_code/outputs/horizon_H8_n20000_early_only_confounded_minus.npy

calibration_code/outputs/horizon_H8_n20000_early_only_confounded_plus.npy

calibration_code/outputs/horizon_H8_n20000_early_only_nonconfounded.npy

calibration_code/outputs/horizon_H9_n20000_early_calibration_center.npy

calibration_code/outputs/horizon_H9_n20000_early_calibration_confounded_minus.npy

calibration_code/outputs/horizon_H9_n20000_early_calibration_confounded_plus.npy

calibration_code/outputs/horizon_H9_n20000_early_calibration_nonconfounded.npy

calibration_code/outputs/horizon_H9_n20000_early_only_center.npy

calibration_code/outputs/horizon_H9_n20000_early_only_confounded_minus.npy

calibration_code/outputs/horizon_H9_n20000_early_only_confounded_plus.npy

calibration_code/outputs/horizon_H9_n20000_early_only_nonconfounded.npy

calibration_code/outputs/sample_size_H8_n128000_early_calibration_center.npy

calibration_code/outputs/sample_size_H8_n128000_early_calibration_confounded_minus.npy

calibration_code/outputs/sample_size_H8_n128000_early_calibration_confounded_plus.npy

calibration_code/outputs/sample_size_H8_n128000_early_calibration_nonconfounded.npy

calibration_code/outputs/sample_size_H8_n128000_early_only_center.npy

calibration_code/outputs/sample_size_H8_n128000_early_only_confounded_minus.npy

calibration_code/outputs/sample_size_H8_n128000_early_only_confounded_plus.npy

calibration_code/outputs/sample_size_H8_n128000_early_only_nonconfounded.npy

calibration_code/outputs/sample_size_H8_n2000_early_calibration_center.npy

calibration_code/outputs/sample_size_H8_n2000_early_calibration_confounded_minus.npy

calibration_code/outputs/sample_size_H8_n2000_early_calibration_confounded_plus.npy

calibration_code/outputs/sample_size_H8_n2000_early_calibration_nonconfounded.npy

calibration_code/outputs/sample_size_H8_n2000_early_only_center.npy

calibration_code/outputs/sample_size_H8_n2000_early_only_confounded_minus.npy

calibration_code/outputs/sample_size_H8_n2000_early_only_confounded_plus.npy

calibration_code/outputs/sample_size_H8_n2000_early_only_nonconfounded.npy

calibration_code/outputs/sample_size_H8_n32000_early_calibration_center.npy

calibration_code/outputs/sample_size_H8_n32000_early_calibration_confounded_minus.npy

calibration_code/outputs/sample_size_H8_n32000_early_calibration_confounded_plus.npy

calibration_code/outputs/sample_size_H8_n32000_early_calibration_nonconfounded.npy

calibration_code/outputs/sample_size_H8_n32000_early_only_center.npy

calibration_code/outputs/sample_size_H8_n32000_early_only_confounded_minus.npy

calibration_code/outputs/sample_size_H8_n32000_early_only_confounded_plus.npy

calibration_code/outputs/sample_size_H8_n32000_early_only_nonconfounded.npy

calibration_code/outputs/sample_size_H8_n512000_early_calibration_center.npy

calibration_code/outputs/sample_size_H8_n512000_early_calibration_confounded_minus.npy

calibration_code/outputs/sample_size_H8_n512000_early_calibration_confounded_plus.npy

calibration_code/outputs/sample_size_H8_n512000_early_calibration_nonconfounded.npy

calibration_code/outputs/sample_size_H8_n512000_early_only_center.npy

calibration_code/outputs/sample_size_H8_n512000_early_only_confounded_minus.npy

calibration_code/outputs/sample_size_H8_n512000_early_only_confounded_plus.npy

calibration_code/outputs/sample_size_H8_n512000_early_only_nonconfounded.npy

calibration_code/outputs/sample_size_H8_n8000_early_calibration_center.npy

calibration_code/outputs/sample_size_H8_n8000_early_calibration_confounded_minus.npy

calibration_code/outputs/sample_size_H8_n8000_early_calibration_confounded_plus.npy

calibration_code/outputs/sample_size_H8_n8000_early_calibration_nonconfounded.npy

calibration_code/outputs/sample_size_H8_n8000_early_only_center.npy

calibration_code/outputs/sample_size_H8_n8000_early_only_confounded_minus.npy

calibration_code/outputs/sample_size_H8_n8000_early_only_confounded_plus.npy

calibration_code/outputs/sample_size_H8_n8000_early_only_nonconfounded.npy

calibration_code/outputs/unknown_bias_checks.json

calibration_code/outputs/unknown_bias_checks.txt

calibration_code/requirements.txt

supplement_code/README.md

supplement_code/verify_observation_only_dp.py

supplement_code/verify_observation_only_exhaustive.py

supplement_code/verify_parametric_family.py

supplement_code/verify_product_memory_dp.py

supplement_code/verify_product_memory_exhaustive.py

verification/README.md

verification/code/verify_common_operator_dp.py

verification/code/verify_common_operator_exhaustive.py

verification/code/verify_early_readout_dominance.py

verification/code/verify_readout.py

verification/code/verify_scalar_value_calibration.py

verification/code/verify_short_probe_example.py

verification/outputs/common_operator_dp.txt

verification/outputs/common_operator_dp_report.json

verification/outputs/common_operator_exhaustive.txt

verification/outputs/early_readout_dominance.txt

verification/outputs/readout.txt

verification/outputs/scalar_value_calibration.txt

verification/outputs/short_probe_example.txt

verification/reference/verify_product_memory_dp.py

verification/reference/verify_product_memory_exhaustive.py

(149 additional files not shown) You must enabled JavaScript to view entire file list.

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.