Papers for

robotics algorithm designers

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

History dependent logging makes policy evaluation exponentially hard

Exponential Hardness of Off-Policy Evaluation under History-Dependent Logging

Abstract: Can a logged dataset visit every hidden state frequently and still be exponentially uninformative about a target policy's value? We show that it can when the logger depends on history. For every horizon $H \ge 3$, we construct two POMDPs with at most two latent states per stage, three actions, and a common logger with three memory states. Action coverage, belief coverage, and two behavior-marginal outcome-revealing conditions all have constants independent of $H$. Nevertheless, evaluating a known deterministic target policy to accuracy $1/8$ requires $Θ((3/2)^H \log(1/δ))$ logged episodes at confidence $1-δ$, for $0 < δ\le 1/4$, even when both candidate models are known. The mechanism is simple: a reset erases the unknown transition that determines the target value. We characterize the resulting statistical experiment exactly and obtain a matching optimal estimator. A directed two-lane gridworld realizes the construction, and trajectory simulations agree with its finite-sample prediction. The result establishes intractability for the history-dependent-logging, model-based case posed by Zhang and Jiang (2025, arXiv:2503.01134), under their behavior-marginal definition of revealing.

Wed 16 SeptMachine Learning
The gist
Estimating how well a certain plan (policy) will work using past data can be very difficult if the data collection depends on previous events. The authors show that even when the system seems to have good coverage and the models are known, the number of samples needed to evaluate a policy grows exponentially with the length of the decision process. They build simple examples where a single reset action erases key information, making the problem much harder. Their findings prove that past assumptions about ease of evaluation under these conditions do not hold.
Open 2609.19135v1