The field of reinforcement learning and computational complexity is rapidly evolving, with a focus on developing more efficient and scalable algorithms for complex problems. Recent research has explored the use of novel frameworks, such as pseudo-MDPs, to optimize solutions for specific classes of problems, including those related to blockchain security. Additionally, there has been significant progress in the development of benchmarks, such as BuilderBench and PuzzlePlex, to evaluate the performance of foundation models and generalist agents in complex, dynamic environments. These advancements have the potential to improve the efficiency and effectiveness of reinforcement learning algorithms in a wide range of applications. Noteworthy papers include: To Distill or Decide?, which investigates the algorithmic trade-off between privileged expert distillation and standard RL without privileged information. PuzzlePlex, which introduces a benchmark to assess the reasoning and planning capabilities of foundation models. Pseudo-MDPs, which proposes a novel framework for efficiently optimizing last revealer seed manipulations in blockchains.
Advances in Reinforcement Learning and Computational Complexity
Sources
How Pinball Wizards Simulate a Turing Machine
To Distill or Decide? Understanding the Algorithmic Trade-off in Partially Observable Reinforcement Learning
Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Finite-Horizon Offline RL with Linear $q^\pi$-Realizability and Concentrability
Neural Bayesian Filtering
A Dynamic Programming Approach to Evader Pathfinding in Static Pursuit Scenarios
Offline Reinforcement Learning in Large State Spaces: Algorithms and Guarantees
Strongly Solving 2048 4x3
BuilderBench -- A benchmark for generalist agents
PuzzlePlex: Benchmarking Foundation Models on Reasoning and Planning with Puzzles
Scalable Policy-Based RL Algorithms for POMDPs
Pseudo-MDPs: A Novel Framework for Efficiently Optimizing Last Revealer Seed Manipulations in Blockchains