Research map / Reinforcement learning / Visual and representation RL

Assume-Guarantee Reinforcement Learning

AAAI 2024 · Reinforcement learning › Visual and representation RL · approach: In-context and adaptive RL · 5 citations (OpenAlex)

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 assume-guarantee reinforcement learning for networks of MDPs, solving local two-player Markov games (minimax-Q) per component whose values lower-bound the global DFA-specification satisfaction probability.

Problem

Synthesizing distributed controllers for networks of parallel MDP components with limited or no communication is computationally hard (undecidable for infinite horizons, NP-hard for fixed horizons), and monolithic RL over the joint system is prohibitively large.

Approach

Each component's controller is learned locally as a Markov game against an adversarial environment that makes worst-case assumptions about neighbors' DFA-labeled behavior; the product of local satisfaction values gives a provable lower bound on global satisfaction, and minimax-Q (deep variant) computes the local policies.

Key results

• In the multi-agent grid world, deep minimax-Q learning learns the optimal policies achieving satisfaction probability one, taking about 10 minutes of training.
• In room temperature control with 16 rooms, the learned policies reach empirical satisfaction probabilities reported with 95% confidence intervals from 1000 Monte-Carlo runs; training takes 10 minutes.
• Traffic light control with nine intersections trains in 100 minutes, with satisfaction probability evaluated via 1000 Monte-Carlo simulations per training checkpoint.

Measured effects reported in the paper

Limitations

• Results are restricted to DFA specifications; extension to full LTL is future work.
• Requires access to labels of neighboring components and coarse Kripke abstractions of them.
• Lower bound may be conservative because it relies on worst-case assumptions and product of local values.

Experimental setup

Benchmarks: multi-agent grid world room temperature control traffic lights control (3x3 grid)

Metrics: probability of satisfaction (Monte-Carlo estimate with 95% c

Baselines: independent Q-learning no-communication policies

Builds on: minimax-Q learning Q-learning deep minimax-Q learning

Closest papers by meaning

• Distillation of RL Policies with Formal Guarantees via Variational Abstraction of Markov Decision Processes (AAAI 2022 · similarity 0.87)
• Reinforcement Learning for Reachability: Guaranteeing Asymptotic Optimality (ICML 2026 · similarity 0.86)
• Composable Modular Reinforcement Learning (AAAI 2019 · similarity 0.86)
• Oracle-Efficient Reinforcement Learning for Max Value Ensembles (NeurIPS 2024 · similarity 0.86)
• Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.85)
• Is Inverse Reinforcement Learning Harder than Standard Reinforcement Learning? A Theoretical Perspective (ICML 2024 · similarity 0.85)