Research map / Reinforcement learning / MDPs and planning
Geometric Active Exploration in Markov Decision Processes: the Benefit of Abstraction
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 MDP homomorphisms to Convex RL to solve Active Exploration via abstraction over geometric symmetries (Geometric Active Exploration), with a sample-complexity analysis showing benefits from geometric compression.
Problem
Active Exploration (experiment design over a Markovian state space) is not scalable when experiment spaces are vast, though they often have known geometric symmetries that are unexploited.
Approach
Define a geometric estimation error that aggregates estimates over f-invariant equivalence classes, smooth it into a convex objective, and solve the Frank-Wolfe sequence of MDPs on a smaller abstract MDP obtained via an MDP homomorphism, lifting policies back to the original MDP.
Key results
- Regret bound of order n^{-1/3} for the Frank-Wolfe-based algorithm with geometric compression factor Phi^{1/2}.
- In the toxicity task with string-permutation invariance (S-bar=55, Phi approx 0.15), even small compression gives a significant statistical advantage over classic AE.
- Runtime reduced versus classic AE at several compression degrees in the pollutant task (normalized runtime comparison).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Exploit geometric symmetries through abstraction | Geometric Active Exploration vs. AE · Pollutant diffusion, deterministic dynamics | sample efficiency | Helped |
| Exploit geometric symmetries through abstraction | Geometric Active Exploration vs. AE · Pollutant diffusion, stochastic dynamics | sample efficiency | Helped |
| Exploit geometric symmetries through abstraction | Geometric Active Exploration vs. AE · Chemical compound toxicity | statistical performance | Helped |
| Exploit geometric symmetries through abstraction | Geometric Active Exploration vs. AE · Pollutant diffusion | computational efficiency | Helped |
| Add weighted averaging across equivalence classes during inference (ablation) | AE · Pollutant diffusion | estimation performance | Helped |
Limitations
- Assumes symmetries are exact and the homomorphism is known.
- Requires homogeneous equivalence classes and ergodicity of the induced Markov chains.
- Experiments limited to simple simulated environments.
Experimental setup
Datasets: simulated pollutant diffusion environment simulated chemical compound toxicity environment
Benchmarks: pollutant diffusion process (S=240) toxicity of chemical compounds (S=363)
Metrics: sample efficiency (estimation error vs samples) normalized runtime
Baselines: Active Exploration (classic, no abstraction)
Builds on: Convex RL MDP homomorphisms Active Exploration
Closest papers by meaning
- Model-Free Active Exploration in Reinforcement Learning (NeurIPS 2023 · similarity 0.89)
- Navigating to the Best Policy in Markov Decision Processes (NeurIPS 2021 · similarity 0.89)
- Provably Efficient Exploration for Reinforcement Learning Using Unsupervised Learning (NeurIPS 2020 · similarity 0.88)
- Task-Optimal Exploration in Linear Dynamical Systems (ICML 2021 · similarity 0.88)
- A Differential and Pointwise Control Approach to Reinforcement Learning (NeurIPS 2025 · similarity 0.87)
- Efficient Preference-Based Reinforcement Learning: Randomized Exploration meets Experimental Design (NeurIPS 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.