Papers

• Optimal Stabilizer Testing and Learning with Limited Quantum Memory (2026)
  Srinivasan Arunachalam et al.
  5.49
• Testing Distributions Against Bounded Distinguishers (2026)
  Mark Bun et al.
  3.51
• Learning Decision-Sufficient Representations for Linear Optimization (2026)
  Yuhan Ye et al.
  1.78
• VERIFY-RL: Verifiable Recursive Decomposition for Reinforcement Learning in Mathematical Reasoning (2026)
  Kaleem Ullah Qasim et al.
  1.72
• Strongly Polynomial Time Complexity of Policy Iteration for $L_\infty$ Robust MDPs (2026)
  Ali Asadi et al.
  1.67
• Computational Hardness of Reinforcement Learning with Partial $q^{\pi}$-Realizability (2025)
  Shayan Karimi and Xiaoqi Tan
  1.50
• Value Iteration with Guessing for Markov Chains and Markov Decision Processes (2025)
  Krishnendu Chatterjee and Mahdi JafariRaviz and Raimundo Saona and Jakub Svoboda
  1.22
• Necessary and Sufficient Oracles: Toward a Computational Taxonomy For Reinforcement Learning (2025)
  Dhruv Rohatgi et al.
  1.06
• Lower Bound On the Computational Complexity of Discounted Markov Decision Problems (2017)
  Yichen Chen and Mengdi Wang
  —
• Algorithms and Conditional Lower Bounds for Planning Problems (2018)
  Krishnendu Chatterjee et al.
  —
• Transience in Countable MDPs (2020)
  Stefan Kiefer et al.
  —
• A Lower Bound for the Sample Complexity of Inverse Reinforcement Learning (2021)
  Abi Komanduru et al.
  —
• Computational-Statistical Gaps in Reinforcement Learning (2022)
  Daniel Kane et al.
  —
• Pandora Box Problem with Nonobligatory Inspection: Hardness and Approximation Scheme (2022)
  Hu Fu et al.
  —
• Lower Bounds for Learning in Revealing POMDPs (2023)
  Fan Chen et al.
  —
• Exponential Hardness of Reinforcement Learning with Linear Function Approximation (2023)
  Daniel Kane et al.
  —
• Computably Continuous Reinforcement-Learning Objectives are PAC-learnable (2023)
  Cambridge Yang et al.
  —
• Rethinking Model-based, Policy-based, and Value-based Reinforcement Learning via the Lens of Representation Complexity (2023)
  Guhao Feng et al.
  —
• Exploration is Harder than Prediction: Cryptographically Separating Reinforcement Learning from Supervised Learning (2024)
  Noah Golowich et al.
  —
• A Deep Reinforcement Learning Approach for Trading Optimization in the Forex Market with Multi-Agent Asynchronous Distribution (2024)
  Davoud Sarani et al.
  —
• Backward explanations via redefinition of predicates (2024)
  L\'eo Sauli\`eres and Martin C. Cooper and Florence Dupin de Saint Cyr
  —