Researchers have built a reinforcement-learning algorithm that learns how to reach a goal state without ever building a map of the environment it's in.
The algorithm, called Quasar, targets "reachability" problems in Markov Decision Processes (MDPs), the mathematical models behind much of sequential decision-making research. Earlier methods that came with a proof of eventually finding the optimal policy had to first estimate the full transition-probability table of the MDP, a model-based approach that eats memory proportional to the square of the number of states. Quasar instead uses classic Q-learning-style updates, a model-free technique, and still carries a convergence guarantee, but only on MDPs free of non-trivial maximal end components (MECs), a baseline case every MDP can be reduced to via the standard MEC quotient. On the Quantitative Verification Benchmark Set, the researchers report convergence in orders of magnitude fewer samples than the previous model-based state-of-the-art, while cutting memory use from O(|S|^2|A|) to O(|S||A|).
This closes a gap that has dogged specification-guided RL: a provably-correct learner that skips the memory bill of building a full model first. Formal verification and safety-critical planning both lean on reachability guarantees, and a lighter-weight learner brings those guarantees closer to running on real hardware instead of staying a paper exercise.
Worth noting: the guarantee holds on the MEC-free fragment of MDPs, not arbitrary ones, so applying the MEC quotient to a general problem is a separate step before Quasar's numbers tell the whole story.