Research map / Reinforcement learning / MDPs and planning

Sample Efficient Reinforcement Learning with Partial Dynamics Knowledge

AAAI 2024 · Reinforcement learning › MDPs and planning · approach: Function approximation in RL theory · 2 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.

Proposes UCB-f, an optimistic Q-learning method for finite episodic MDPs with additive disturbance dynamics that uses known or approximate dynamics f to propagate Q-updates to all state-action pairs, yielding sqrt(T) regret independent of S and A.

Problem

Sample complexity of online RL when partial knowledge of the system dynamics (an additive disturbance model S_{h+1}=f(S_h,A_h)+W_h) is available, with known or approximate f.

Approach

Use the known (or approximate) dynamics f to simulate Q-learning updates for all state-action pairs from each observed disturbance w_h = s_{h+1} - f(s_h,a_h), combined with a rescaled learning rate alpha_t=(H+1)/(H+t) and optimism bonuses, so regret does not scale with S and A when f is exact.

Key results

• With exact f, the algorithm achieves regret O~(sqrt(H^6 T)) with no dependence on S and A, versus O~(sqrt(H^2 SAT)) for prior Q-learning methods.
• With an approximate f_hat (||f_hat - f||_inf <= zeta/2), the regret adds a linear term O(L zeta H T) and the learned policy is (eps + O(L zeta H^2))-optimal.
• Empirically on random MDPs, UCB-f converges to the optimal policy with zeta=0 at a rate not affected by increasing S and A, while UCB-H and UCBVI slow down as S and A grow.

Measured effects reported in the paper

Limitations

• Linear zeta*T regret term is unavoidable under persistent approximation error f_hat != f.
• Horizon dependence H^6 (or H^7 in the policy bound) is not sharp.
• Analysis restricted to tabular finite episodic MDPs with additive disturbances; value-function approximation and continuous spaces are left to future work.

Experimental setup

Datasets: randomly generated MDPs

Benchmarks: randomly generated MDPs (S=25, A in {2,4,8}, H in {5,10})

Metrics: regret per episode (suboptimality gap)

Baselines: UCB-H UCBVI

Builds on: UCB-H UCBVI Q-learning

Closest papers by meaning

• The Sample Complexity of Online Reinforcement Learning: A Multi-model Perspective (ICLR 2026 · similarity 0.93)
• Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning (ICML 2021 · similarity 0.92)
• Non-Asymptotic Best Policy Identification Guarantees in Online Reinforcement Learning (NeurIPS 2026 · similarity 0.89)
• Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning (NeurIPS 2025 · similarity 0.89)
• On the Complexity of Offline Reinforcement Learning with Q*-Approximation and Partial Coverage (NeurIPS 2026 · similarity 0.88)
• A Nearly Optimal and Low-Switching Algorithm for Reinforcement Learning with General Function Approximation (NeurIPS 2024 · similarity 0.88)