Research map / Reinforcement learning / MDPs and planning
The Number of Trials Matters in Infinite-Horizon General-Utility Markov Decision Processes
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that in infinite-horizon GUMDPs the number of sampled trajectories affects policy evaluation: finite-trial objectives mismatch infinite-trial ones for nonlinear discounted and multichain average objectives, with lower/upper bounds in K, and match for unichain average.
Problem
Prior GUMDP work assumes infinite trials and only analyzed finite-horizon settings; it is unclear how the number of sampled trajectories affects policy evaluation of nonlinear occupancy-based objectives in infinite-horizon discounted and average GUMDPs.
Approach
Defines finite-trials objectives that evaluate a policy's empirical state-action occupancy over K sampled trajectories (versus expected occupancy), proving that for convex nonlinear f the finite and infinite trials objectives differ, with lower bounds scaling as 1/K (strongly convex f) and high-probability upper bounds for Lipschitz f, and that they coincide for unichain average GUMDPs.
Key results
- For the discounted setting, a strictly convex example (M_f3) shows f_K(pi) differs from f_inf(pi) for K=1, and a lower bound (c/2K) times summed variances of discounted returns shows the gap decays linearly in 1/K.
- For unichain average GUMDPs, f_K(pi) = f_inf(pi) for any bounded continuous f, while multichain average GUMDPs admit a mismatch with a 1/K lower bound.
- Empirical results on M_f1, M_f2, M_f3 confirm that the gap shrinks with more trajectories and vanishes in the unichain noisy-transition case as gamma approaches 1.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Evaluate a fixed policy with a finite number K of trajectories instead of the infinite-trials objective | Discounted GUMDPs with convex nonlinear objectives · Discounted setting | finite–infinite objective mismatch: f_K(π) ≥ f_∞(π); for c-strongly convex f, f_K(π) - f_∞(π) ≥ (c/(2K)) Σ_{s,a} Var[ d̂_T(s,a) ] | Mixed |
| Increase the number of sampled trajectories K | Discounted GUMDP policy evaluation · Discounted setting | finite–infinite objective mismatch: 1/K | Helped |
| Increase the number of sampled trajectories K | Truncated discounted GUMDP policy evaluation · Discounted setting | upper bound on absolute objective deviation: L ( √(2|S||A| log(2H / δ) / K) + 2γ^H ) | Helped |
| Increase trajectory length H while keeping K fixed | Truncated discounted GUMDP policy evaluation · Discounted setting | upper bound on absolute objective deviation: lim_{H → ∞} E_Upper(K,H) = ∞ | Hurt |
| Use finite rather than infinite trials | Average GUMDPs with a unichain induced Markov chain and bounded continuous objective · Average setting, unichain | finite–infinite objective mismatch | No clear effect |
| Use finite rather than infinite trials | Average GUMDPs with a multichain induced Markov chain and nonlinear objective · Average setting, multichain | finite–infinite objective mismatch: f_∞(π) < f_{K=1}(π) | Hurt |
| Use a linear objective instead of a nonlinear objective | Discounted and average GUMDPs · Discounted and average settings | finite–infinite objective mismatch: f_∞(π) = f_K(π), for any K ∈ N | Helped |
| Add noisy transitions that make the induced chain unichain | Illustrative GUMDPs under average policy evaluation · Average setting, noisy transitions | finite–infinite objective mismatch | Helped |
| Evaluate with a finite number of trajectories | Illustrative GUMDPs under discounted policy evaluation · Discounted setting, infinite-length trajectories | finite–infinite objective mismatch | Hurt |
| Increase both trajectory count K and trajectory length H | Illustrative GUMDPs under discounted policy evaluation · Discounted setting | finite–infinite objective mismatch | Helped |
Surprising findings
- Contrary to the prior suggestion that the finite/infinite trials gap vanishes in the infinite-horizon setting, the number of trials matters for discounted and multichain average GUMDPs.
- For the discounted setting the mismatch persists even with infinite-length trajectories when K is small.
Limitations
- Analysis restricted to policy evaluation; policy optimization under finite trials is left open
- Lower and upper bounds assume strong convexity or Lipschitz continuity of f and are not tight in general
- Experiments use small illustrative tabular GUMDPs
Experimental setup
Metrics: finite trials objective f(d_hat) gap to infinite trials objective f(d_pi) 95% bootstrapped confidence intervals over 100 seeds
Builds on: general-utility MDPs convex MDPs finite-horizon GUMDP finite-trials formulation (Mutti et al.)
Closest papers by meaning
- Finding good policies in average-reward Markov Decision Processes without prior knowledge (NeurIPS 2024 · similarity 0.87)
- Efficient and Sharp Off-Policy Evaluation in Robust Markov Decision Processes (NeurIPS 2024 · similarity 0.87)
- Regret Analysis of Policy Gradient Algorithm for Infinite Horizon Average Reward Markov Decision Processes (AAAI 2024 · similarity 0.86)
- Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes (ICLR 2025 · similarity 0.86)
- Solving Robust Markov Decision Processes: Generic, Reliable, Efficient (AAAI 2025 · similarity 0.86)
- Sample-efficient Learning of Infinite-horizon Average-reward MDPs with General Function Approximation (ICLR 2024 · similarity 0.86)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.