Abstract
We present an approximate policy iteration algorithm that uses rollouts to estimate the value of each action under a given policy in a subset of states and a classifier to generalize and learn the improved policy over the entire state space. Using a multiclass support vector machine as the classifier, we obtained successful results on the inverted pendulum and the bicycle balancing and riding domains.
Introduction
In Reinforcement Learning (RL), the standard objective is to find a policy—a mapping from states to actions—that maximizes cumulative long-term rewards. Traditionally, this is achieved through Approximate Policy Iteration (API), which relies on estimating a value function (the expected return of a state or state-action pair) and deriving a policy from it. However, value function approximation is notoriously difficult, often requiring extensive manual feature engineering and exhibiting high sensitivity to approximation errors. Small inaccuracies in value estimation can lead to significant degradations in policy performance.
This paper proposes a shift in perspective: treating policy improvement as a classification problem. Instead of predicting exact numerical values, the goal is to classify which action is optimal for a given state, leveraging the robustness of large-margin classifiers like Support Vector Machines (SVMs).
Methods
The proposed framework integrates Monte-Carlo rollouts with supervised classification to iteratively improve the policy. The algorithm follows a structured loop as detailed in the pseudocode below:
- Rollouts: For a representative set of states $S_{\rho}$, the algorithm performs "rollouts." Starting from a state $s$ and taking action $a$, it follows the current policy $\hat{\pi}_i$ to observe the total accumulated reward. This provides a noisy but unbiased estimate of the action-value $\tilde{Q}_{\pi_i}(s, a)$.
- Statistical Labeling: To mitigate noise, the authors employ statistical tests (e.g., a two-sample t-test). A state-action pair is only used as a training example if one action is significantly better than the others.
- Multi-class SVMs: A multi-class SVM is trained on these labeled examples to learn the new policy $\hat{\pi}_{i+1}$. By utilizing the "kernel trick" (e.g., polynomial or Gaussian kernels), the SVM can capture complex, non-linear decision boundaries in high-dimensional spaces without manual feature design.
Experimental Results
The algorithm was evaluated on two classic control benchmarks: the Inverted Pendulum and the Bicycle Balancing and Riding task.
Inverted Pendulum
In this 2D control problem, the algorithm consistently achieved a perfect balancing policy within one or two iterations, using a sparse set of approximately 200 states. This demonstrated the efficiency of the classification-based approach in low-dimensional settings.
Bicycle Balancing and Riding
The bicycle task is a significantly more complex 6D problem requiring the agent to balance and navigate toward a target 1 km away. Using a degree-5 polynomial kernel and roughly 5,000 rollout states, the algorithm successfully learned to both balance the bicycle and steer it to the destination.
Discussion and Conclusion
The results indicate that classification is often a more robust learning task for RL than regression-based value estimation. By focusing on the relative ranking of actions rather than their absolute values, the algorithm avoids the pitfalls of brittle value function modeling. Furthermore, the use of kernels allows the algorithm to implicitly explore complex feature spaces, reducing the burden of manual feature engineering.
Despite these successes, the approach requires a generative model (simulator) to perform rollouts from arbitrary states, which may limit its application in physical robotics without a high-fidelity model. Future work will focus on automating hyperparameter selection and exploring more efficient state sampling strategies.
Summary updated