Research map / Reinforcement learning / Policy gradient and actor-critic

Reinforcement Learning with Random Time Horizons

ICML 2025 · Reinforcement learning › Policy gradient and actor-critic · approach: Policy gradients for special settings · 0 citations (OpenAlex)

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.

Extends RL to random (trajectory-dependent) time horizons and derives policy gradient formulas for stochastic and deterministic policies, with trajectory- and state-space-based versions, showing faster convergence than classical formulas that ignore the expected stopping time.

Problem

Standard policy gradient theorems assume deterministic or infinite horizons, but in many applications the stopping time is random and policy-dependent, so classical gradient formulas are incorrect for such settings.

Approach

Formulates MDPs with random first-hitting-time horizons and derives corrected policy gradients (trajectory-based, state-space-based with an E[N+1] scaling factor, and model-based deterministic policy gradient), showing that omitting the expected runtime factor yields a biased gradient equivalent to a changing effective learning rate.

Key results

• On the modified mountain car, the PG formulas incorporating expected hitting time perform significantly better than the biased state-space PG, which becomes unstable due to increasing trajectory lengths and memory issues.
• On the reacher task, the corrected PG formulas converge faster than the classical biased formula, whose effective learning rate is small early on.
• In molecular dynamics hitting-time importance sampling (d=20), the stopping-time-aware formulas converge roughly twice as fast as the scaled-out state-space gradient.

Measured effects reported in the paper

Surprising findings

• Omitting the expected stopping time factor E[N+1] from the state-space policy gradient yields an incorrect gradient that acts as a policy-dependent effective learning rate, which can slow or destabilize optimization.
• The trajectory-based policy gradient for random horizons has the same form as for deterministic horizons, with no extra term from the policy dependence of N.

Limitations

• Experiments are small-scale classical control and molecular dynamics benchmarks with simple policies (3-layer MLPs) and plain stochastic gradient ascent.
• Equivalence of the discounted infinite-horizon formulation holds only in expectation; numerical implications are not fully studied.
• The state-space gradient still requires simulating trajectories for sampling, so the computational advantage is not fully established.

Experimental setup

Benchmarks: modified continuous mountain car two-joint robot arm (reacher) importance sampling of hitting times in molecular dynamics

Metrics: negative expected return effective learning rate convergence per gradient step convergence per computational time

Baselines: trajectory PG state-space PG (biased)

Builds on: policy gradient theorem deterministic policy gradient discounted infinite horizon as random horizon lemma

Closest papers by meaning

• Pausing Policy Learning in Non-stationary Reinforcement Learning (ICML 2024 · similarity 0.87)
• Towards Global Optimality for Practical Average Reward Reinforcement Learning without Mixing Time Oracles (ICML 2024 · similarity 0.87)
• Convergence Analysis of Policy Gradient Methods with Dynamic Stochasticity (ICML 2025 · similarity 0.87)
• Learning Optimal Deterministic Policies with Stochastic Policy Gradients (ICML 2024 · similarity 0.87)
• Randomized Exploration for Reinforcement Learning with Multinomial Logistic Function Approximation (NeurIPS 2024 · similarity 0.87)
• The Horizon Threshold in Cooperative Multi-Agent Reward-Free Exploration (NeurIPS 2026 · similarity 0.87)