TL;DR
Reinforcement Learning via Sequence Modeling (RvS) assumes that fitting more expressive generative models to offline trajectories directly translates to better policies. This paper shows that expressiveness alone is insufficient: models often learn accurate return dynamics during training but fail to sample high-reward actions at test time. To solve this, the authors introduce Trifle, which incorporates Tractable Probabilistic Models (TPMs) to enable exact marginalization and efficient, value-guided action generation during inference.
What Problem Does This Paper Address?
RvS methods (like Decision Transformers and Trajectory Transformers) treat offline RL as a conditional sequence generation problem. During inference, these models must generate actions conditioned on achieving high expected future returns: $p(a_t \mid s_t, \mathbb{E}[V_t] \ge v)$.
The authors demonstrate that existing approaches suffer from severe inference-time suboptimality. Even when models learn faithful representations of environment dynamics and values, standard autoregressive sampling or naive rejection sampling rarely yields top-tier actions from high-dimensional continuous action spaces. Furthermore, in stochastic environments, estimating expected multi-step values requires unrolling intermediate states; autoregressive rollouts accumulate compounding variance, degrading policy evaluation.
Methods
The paper introduces Trifle (Tractable Inference for Offline RL), bridging expressive deep generative models and tractable probabilistic computation:
- Tractable Probabilistic Models (TPMs) via Probabilistic Circuits (PCs): The authors employ Hidden Chow-Liu Trees (HCLTs) trained via Latent Variable Distillation (LVD). PCs guarantee exact and linear-time computation of arbitrary marginal and conditional queries.
- TPM-Guided Action Proposal: To sidestep the NP-hardness of directly sampling from the expected-value-conditioned policy (formalized in Theorem 1), Trifle combines an expressive autoregressive prior (such as a Trajectory Transformer or Decision Transformer) with a TPM correction factor across action dimensions: $$\tilde{p}(a_t^i \mid s_t, a_t^{<i}; v) \propto p_{\text{GPT}}(a_t^i \mid s_t, a_t^{<i}) \cdot p_{\text{TPM}}(V_t \ge v \mid s_t, a_t^{\le i})$$
- Closed-Form Multi-Step Value Estimation: For environments with stochastic dynamics or noisy offline returns-to-go (RTG), Trifle computes multi-step return expectations ($\mathbb{E}[V_t^m]$) by leveraging the linearity of expectation and exact marginalization of intermediate future states, avoiding noisy Monte Carlo rollouts.
- Beam Search with Adaptive Thresholds: Candidate action sequences are generated and evaluated via beam search, using an adaptive quantile-based threshold $v$ derived directly from the state-conditioned value distribution $p(V_t \mid s_t)$.
Datasets
- D4RL Gym-MuJoCo: 9 standard locomotion benchmarks across three environments (
HalfCheetah,Hopper,Walker2d) and three dataset regimes (Medium-Expert,Medium, andMedium-Replay). - Modified Gym-Taxi (Stochastic): A discrete grid-world navigation task modified with 30% transition noise (slipping to unintended directions) and heavy penalties for illegal drop-offs/collisions. Trajectories were gathered from a Q-learning agent.
- Action-Space-Constrained Gym-MuJoCo: Safe-RL variants of HalfCheetah, Hopper, and Walker2d where torque applied to rotor joints is constrained ($\le 0.5$).
Key Insights and Ideas
- Expressivity $\neq$ Tractability: Sequence models can distinguish good actions from bad ones in offline data, yet their inference-time optimality scores remain surprisingly low ($\approx 0.7$ out of $1.0$). Failures stem from an inability to query the model effectively, not a failure to learn.
- Theoretical Hardness: The authors prove in Theorem 1 that computing $p(a_t \mid s_t, \mathbb{E}[V_t] \ge v)$ is NP-hard even for a simple Naive Bayes distribution (via reduction from the number partition problem).
- Exact Marginalization Beats Rollouts: In stochastic environments, sampling intermediate states causes variance to blow up over long horizons. By analytically integrating out intermediate states with a PC, Trifle drastically improves multi-step value prediction correlation ($R = 0.67$ vs. $R = 0.52$ for Trajectory Transformers).
Key Results
- Gym-MuJoCo Baselines: Trifle achieves state-of-the-art results across 9 benchmarks against RvS, imitation learning, and offline TD methods (IQL, CQL, BEAR). It particularly shines on noisy
Medium-Replaydatasets (e.g., 88.3 on Walker2d-Replay vs. 82.6 for TT and 66.6 for DT). - Stochastic Taxi: Multi-step Trifle (
m-Trifle) reaches an average episode return of -57 with a failure rate of only 2%, outperforming Trajectory Transformer (-182, 34% failure) and Decision Transformer (-388, 66% failure). - Safe RL (Constrained Actions): Trifle enforces torque limits by conditioning on valid intervals directly inside the PC, outperforming Trajectory Transformers across all tasks (e.g., 109.6 vs. 100.0 on Hopper, 81.9 vs. 77.8 on HalfCheetah).
Limitations and Future Work
- Independent Value Approximation: When approximating the multi-step return CDF $p(V_t^m \ge v \mid s_t, a_{\le \tau})$, intermediate rewards and terminal RTGs are assumed independent, which holds strictly in deterministic settings but is an approximation in stochastic ones.
- Discretization Overhead: The PC requires continuous variables to be discretized into quantile bins (100 bins per dimension), potentially limiting fine-grained continuous control.
- Inference Latency: Combining autoregressive generation, Probabilistic Circuit queries, and beam search incurs substantial computational cost during test-time rollouts.
Summary updated