Research map / Reinforcement learning / MDPs and planning
On the Role of Information Structure in Reinforcement Learning for Partially-Observable Sequential Teams and Games
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 partially-observable sequential teams/games (POST/POSG) with explicit information structure, proves the observable dynamics rank is bounded by the information-structural state size, and gives a UCB-style PSR-based learning algorithm with sample complexity governed by that size.
Problem
Reinforcement learning models (MDPs, POMDPs, Dec-POMDPs, POMGs, PSRs) either assume a fixed, regular information structure or do not represent it explicitly, so the statistical hardness of general sequential decision-making problems is not characterized in terms of their information structure.
Approach
Model sequential decision problems as POSTs/POSGs with an explicit DAG information structure, define an information-structural state as the minimal d-separating set of past (observed or latent) variables, use it to bound the rank of observable dynamics, and generalize PSRs so that arbitrary variable orders are representable; a UCB/MLE-type algorithm then learns with sample complexity governed by t
Key results
- The rank of the observable system dynamics of a POST/POSG is bounded by the maximum cardinality of the information-structural state space, max_h |I_h^dagger|.
- Examples: POMDP and Dec-POMDP rank bounded by |S|; limited-memory-m structures bounded by |O|^m |A|^m; real-time communication with feedback bounded by |X||Z|.
Limitations
- Results are theoretical; no empirical experiments reported in the provided text.
- Bounds depend on the size of the information-structural state, which may still be exponential in general.
- Generalized PSR well-conditioning assumption is needed for learnability.
Experimental setup
Metrics: sample complexity rank of dynamics
Builds on: predictive state representations Witsenhausen intrinsic model UCB-type PSR learning (Huang et al. 2023) optimistic MLE (Liu et al. 2022)
Closest papers by meaning
- Effective Exploration Based on the Structural Information Principles (NeurIPS 2024 · similarity 0.88)
- Structural Information-based Hierarchical Diffusion for Offline Reinforcement Learning (NeurIPS 2025 · similarity 0.87)
- Provable Partially Observable Reinforcement Learning with Privileged Information (NeurIPS 2024 · similarity 0.86)
- Provable Representation with Efficient Planning for Partially Observable Reinforcement Learning (ICML 2024 · similarity 0.86)
- Mitigating Partial Observability in Sequential Decision Processes via the Lambda Discrepancy (NeurIPS 2024 · similarity 0.85)
- The Sample Complexity of Online Strategic Decision Making with Information Asymmetry and Knowledge Transportability (ICML 2025 · similarity 0.85)
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.