TL;DR
Trajectory Fitted Q-Iteration (TFQI) is a batch-mode reinforcement learning algorithm that improves upon standard Fitted Q-Iteration by utilizing the sequential nature of experience samples. By propagating values backward through observed trajectories, TFQI reduces the impact of function approximation errors, leading to faster convergence and better policies with fewer samples.
What Problem Does This Paper Address?
In Reinforcement Learning (RL), agents often operate in large or continuous state spaces where it is impossible to learn the value of every single state exactly. To handle this, researchers use Approximate Value Iteration (AVI), which employs function approximators (like neural networks or radial basis functions) to generalize values across the state space.
However, these approximators are imperfect. They introduce "generalization errors"—essentially, the model's "guess" about a state's value might be slightly wrong. Because standard RL algorithms (like Fitted Q-Iteration) use these guesses to calculate the values of previous states, these errors propagate and compound, leading to poor policies.
The authors point out a missed opportunity: most RL data is collected as trajectories (sequences of steps), yet standard AVI treats these steps as independent, isolated transitions. They ignore the "ground truth" relationship between a state and its actual observed successor in a sequence.
Methods
The authors introduce Trajectory Fitted Q-Iteration (TFQI). It builds on the well-known Fitted Q-Iteration (FQI) framework but makes two key changes:
-
The Update Rule: In standard FQI, the target value for a state is calculated using the reward plus the discounted maximum value predicted by the current model for the next state. TFQI changes this to: $$Target = reward + \gamma \cdot \max(\text{Model's Predicted Value}, \text{Actual Observed Successor Value})$$ By taking the maximum of the model's guess and the actual value achieved later in that specific trajectory, the algorithm can "correct" the model if it is underestimating the long-term reward.
-
Backward Propagation: TFQI processes trajectories in reverse order (from the end of a sequence to the beginning) during each training iteration. This allows a single reward found at the end of a path to propagate all the way back to the start in a single pass, rather than waiting for multiple iterations of the algorithm.
Crucially, TFQI remains off-policy, meaning it can learn from any trajectory data, regardless of whether the policy that generated that data was "good" or "bad."
Datasets
The authors evaluated TFQI on two classic RL benchmarks:
- Mountain Car (MC): A 2D continuous state-space problem where an underpowered car must swing back and forth to gain enough momentum to reach the top of a hill.
- Acrobot (ACRO): A 4D continuous state-space problem simulating a gymnast on a high bar trying to swing their "feet" above the bar.
To generate diverse training data, they used the NEAT (NeuroEvolution of Augmenting Topologies) algorithm to create a wide variety of trajectories, ranging from highly successful to mediocre.
Key Insights and Ideas
- Trajectories as a Safety Net: The observed trajectory provides a lower bound on the true value of a state. If the function approximator predicts a value lower than what was actually achieved in a real trial, we know the approximator is wrong. TFQI uses the trajectory to "pull up" these underestimates.
- Efficiency through Sequence: Standard FQI propagates value one step per iteration. If a goal is 100 steps away, it takes 100 iterations for that reward to reach the starting state. Because TFQI iterates backward through trajectories, it can propagate that value across the entire sequence in just one iteration.
- Robustness to Hyperparameters: One of the most interesting findings is that TFQI is less sensitive to the choice of function approximation settings (like the number of features). It performs well even when the model is "underpowered," because the trajectory data compensates for the model's inability to represent the value function perfectly.
Key Results
- Superior Performance: In both Mountain Car and Acrobot, TFQI learned better policies than standard FQI using the same amount of data. In the Acrobot domain, TFQI's performance was sometimes more than twice as good as FQI's.
- Faster Convergence: TFQI consistently reached a stable, high-performing policy in roughly 100 fewer iterations than FQI.
- Sample Efficiency: TFQI showed significant advantages when training data was sparse (e.g., only 2–5 trajectories). This makes it highly practical for real-world applications where collecting data is expensive or time-consuming.
Limitations and Future Work
- Trajectory Requirement: TFQI requires data to be organized into trajectories. While this is the norm for most RL data collection, it cannot be applied to "shuffled" datasets where the sequential link between samples has been lost.
- Theoretical Bounds: The paper focuses on empirical results. The authors note that providing theoretical convergence guarantees and error bounds for this specific "max" update rule is a task for future research.
- Action Spaces: The experiments were conducted on domains with discrete actions. Extending this to continuous action spaces (where the "max" over actions is harder to compute) remains an open direction.
Summary updated