In the realm of Reinforcement Learning (RL), much like in supervised or unsupervised learning paradigms, the way we represent the state is a critical determinant of success. This is akin to the importance of feature representation, selection, and engineering in other machine learning domains. Introductory materials on RL often employ simplified environments where every possible state can be explicitly listed. This approach streamlines the estimation of values into straightforward rolling averages within a lookup table, making the concepts easier to grasp and implement. Tabular learning methods also benefit from robust theoretical guarantees of convergence. Consequently, if your problem can be simplified to contain a manageable number of states – perhaps under a few million – exploring this avenue is a worthwhile initial step in single agent reinforcement learning.
However, the majority of real-world control problems present state spaces that far exceed this manageable size, even with state discretization. This explosion in dimensionality is known as the “curse of dimensionality.” For these more complex scenarios, state representation typically involves using a vector composed of various features. For example, in robotics, these features might include positions, angles, and velocities of different mechanical components. Similar to supervised learning, these features may require preprocessing for effective use with a specific learning algorithm. Numeric representation is generally necessary, and for neural networks, normalization to a standard range, such as -1 to 1, is often beneficial.
Beyond these considerations shared with other machine learning techniques, Reinforcement Learning introduces the crucial concept of the Markov Property. For effective RL, the state must encapsulate sufficient information to accurately predict future rewards and subsequent states, given an action, without needing any historical context. While perfect adherence to the Markov Property isn’t always necessary – minor variations like air density or temperature for a robot navigating on wheels are usually negligible – any consistent, unaccounted factors can pose a significant challenge. Ignoring essentially random factors may reduce overall agent optimality, but the fundamental RL theory remains applicable.
A more serious issue arises when consistent, unknown factors influence outcomes and could logically be inferred from past states or actions but are excluded from the state representation. In such cases, the agent’s ability to learn effectively can be severely compromised. It’s important to differentiate between observation and state in this context. An observation is simply the raw data collected, such as sensor readings from a robot’s joints. A single, raw observation might not fulfill the Markov Property requirements to serve as an adequate state. In such situations, you can use domain expertise to construct a more informative state from the available data. Alternatively, techniques designed for Partially Observable Markov Decision Processes (POMDPs) can be employed. POMDP methods statistically infer the missing state information, often using Recurrent Neural Networks (RNNs) or Hidden Markov Models (HMMs) to create a “belief state.” This process can be seen as using learning or classification algorithms to effectively “learn” the underlying states.
Finally, the choice of approximation model is another critical consideration. Similar to supervised learning, several approaches exist:
- Linear Regression with Feature Engineering: A simple linear regression model combined with carefully engineered features based on domain knowledge can be surprisingly effective. The challenge lies in iteratively refining state representations to suit linear approximation. This simpler approach offers greater robustness against stability issues compared to non-linear approximations.
- Non-linear Function Approximators (e.g., Neural Networks): More complex non-linear function approximators, like multi-layer neural networks, offer the flexibility to process more “raw” state vectors. The hidden layers can potentially learn intricate structures and representations conducive to accurate value estimation. This approach, in a sense, also involves “learning” states, albeit differently than RNNs or HMMs. This can be particularly advantageous when the state is naturally represented as an image, where manual feature engineering is exceedingly difficult.
The groundbreaking Atari DQN work by DeepMind exemplifies a successful combination of feature engineering and deep neural networks. Their feature engineering included downsampling and greyscaling the input images, and crucially, concatenating four consecutive frames to represent a single state. This allowed the network to capture object velocity information, satisfying the Markov Property more effectively. The Deep Neural Network then processed these image states into higher-level features, enabling accurate predictions of state values and demonstrating a powerful approach to handling variable state spaces in single agent reinforcement learning.
