Research map / Reinforcement learning / MDPs and planning
Provable Benefits of Multi-task RL under Non-Markovian Decision Making Processes
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 UMT-PSR, an upstream multi-task PSR algorithm with pairwise additive distance planning and bracketing-number-based confidence sets, plus a downstream OMLE-based transfer method, proving multi-task and transfer sample-complexity benefits governed by the eta-bracketing number of the joint model class.
Problem
When and how shared latent structure across multiple non-Markovian decision processes (POMDPs/PSRs) reduces sample complexity relative to single-task learning, in both upstream multi-task and downstream transfer settings.
Approach
Characterize task similarity through the eta-bracketing number of the joint multi-task PSR model class; a pairwise additive TV-distance planning objective and a joint-class confidence set yield sample complexity that improves over single-task learning whenever the joint bracketing log-number is less than N times the single-task one. Downstream, a similarity constraint restricts the target model cl
Key results
- UMT-PSR achieves sample complexity about O(r|A|Q_A^2 H^2 beta^(N)/(N gamma^2 eps^2)), which beats single-task learning whenever beta^(N) < N beta^(1)
- Downstream OMLE with upstream-constrained class achieves sample complexity scaling with beta_0 instead of beta, e.g. beta_0 = O(LH) for linear-combination examples versus beta = O(r^2|O||A|H^2) without transfer
- Non-realizable downstream bound adds an approximation error term sqrt(epsilon_0) via Rényi divergence
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use joint multi-task learning when the joint model class has a smaller bracketing complexity than separate task models | UMT-PSR · Upstream multi-task PSRs | sample complexity: \tilde{O}(\frac{r|\mathcal{A}|Q_A^2 H^2 \beta^{(N)} }{ N\gamma^2\epsilon^2}) vs. O(\frac{r|\mathcal{A}|Q_A^2 H^2 \beta } | Helped |
| Remove shared task structure so that the joint class is the Cartesian product of individual classes | UMT-PSR · Upstream multi-task PSRs with no task similarity | sample complexity: \beta^{(N)} = N\beta^{(1)} | No clear effect |
| Share the same dynamics across all tasks | UMT-PSR · Upstream multi-task PSRs with common dynamics | sample complexity: \beta^{(N)} = \beta^{(1)} | Helped |
| Share transition kernels across tasks while allowing different emission distributions | UMT-PSR · Multi-task POMDPs with common transition kernels | sample complexity: \beta^{(N)} < N\beta^{(1)} | Helped |
| Represent task models as perturbations of a shared latent base task with a finite perturbation space | UMT-PSR · Multi-task PSRs with perturbed models | sample complexity: \beta^{(N)} = \tilde{O}( r^2 |\mathcal{O}| |\mathcal{A}| H^2 + HN\log|\boldsymbol{\Delta}|) | Helped |
| Represent tasks as linear combinations of m core tasks | UMT-PSR · Multi-task PSRs with linear combinations of core tasks | sample complexity: \beta^{(N)}=O( m( r^2 |\mathcal{O}| |\mathcal{A}| H^2+ N) ) | Helped |
| Use upstream knowledge and a similarity constraint to restrict the downstream model class | OMLE · Downstream PSR learning | sample complexity: \tilde{O}(\frac{rQ_A^2|\mathcal{A}|H\beta_0}{\gamma^2\epsilon^2}) vs. \tilde{O}(\frac{rQ_A^2|\mathcal{A}|H\beta}{\gamma^ | Helped |
| Use upstream transition kernels as prior knowledge and estimate only the downstream emissions | OMLE · Downstream POMDPs with common transition kernels | sample complexity: \beta_0 = \tilde{O}(H|\mathcal{S}||\mathcal{O}|); \beta = \tilde{O}(H(|\mathcal{S}|^2|\mathcal{A}|+|\mathcal{S}||\mathca | Helped |
| Constrain the downstream PSR to be a perturbation of an upstream base task | OMLE · Downstream PSRs with perturbed models | sample complexity: \beta_0 = \tilde{O}(H\log|\boldsymbol{\Delta}|) | Helped |
| Constrain the downstream PSR to be a linear combination of L upstream tasks | OMLE · Downstream PSRs with linear combinations of core tasks | sample complexity: \beta_0 = \tilde{O}(LH) | Helped |
Limitations
- Purely theoretical; no empirical experiments
- Assumes all tasks share observation and action spaces and same rank and well-conditioning
- Assumes psi_0 known
Experimental setup
Metrics: sample complexity sub-optimality gap TV distance
Baselines: single-task PSR RL (OMLE) independent single-task learning
Builds on: OMLE predictive state representations Rényi divergence analysis
Closest papers by meaning
- Representation Learning Enables Scalable Multitask Deep Reinforcement Learning (NeurIPS 2026 · similarity 0.87)
- Bridging Risk Approximation Gaps in Model Predictive Task Sampling via In-Context Modeling (NeurIPS 2026 · similarity 0.87)
- Multi-Task Reinforcement Learning with Mixture of Orthogonal Experts (ICLR 2024 · similarity 0.86)
- AMAGO-2: Breaking the Multi-Task Barrier in Meta-Reinforcement Learning with Transformers (NeurIPS 2024 · similarity 0.86)
- Mastering Massive Multi-Task Reinforcement Learning via Mixture-of-Expert Decision Transformer (ICML 2025 · similarity 0.86)
- Offline Multitask Representation Learning for Reinforcement Learning (NeurIPS 2024 · similarity 0.86)
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.