TL;DR
This paper analyzes the computational complexity of reinforcement learning (RL) algorithms for solving multi-stage decision problems. It shows that standard RL methods can struggle with large state spaces, but introduces and analyzes two cooperative learning mechanisms, Learning with an External Critic (LEC) and Learning By Watching (LBW), which significantly reduce search time and improve adaptability by leveraging external feedback and vicarious experience.
What Problem Does This Paper Address?
Reinforcement learning algorithms learn optimal policies by having an agent interact with an environment, taking actions, and receiving rewards. For complex, real-world tasks, the number of possible states an agent can be in can be enormous. This leads to a "curse of dimensionality" where the time required for the agent to explore enough states to find a good policy becomes prohibitively long, especially when rewards are sparse or delayed. This paper specifically addresses the computational complexity of this search process in large state spaces and proposes cooperative mechanisms to mitigate it.
Methods
The paper analyzes the time complexity of three approaches:
- Unbiased Q-learning: This is a standard RL algorithm that learns by incrementally updating action-value estimates based on trial-and-error. The analysis focuses on "zero-initialized" Q-learning, meaning the agent starts with no prior knowledge.
- Learning with an External Critic (LEC): This approach introduces a "critic" that provides immediate feedback (rewards) to the learner. The paper specifically details a "Biasing Binary LEC" (BB-LEC) algorithm where the critic provides binary feedback (positive for optimal actions, negative otherwise) to learn a "biasing function" that influences the agent's policy. This mechanism aims to reduce the delay between an action and its evaluation.
- Learning By Watching (LBW): This method allows agents to gain experience by observing other agents performing similar tasks. The observed state-action-reward sequences are used as if they were the learner's own experience. This approach can learn from both skilled and naive peers.
The analysis is performed on a restricted but analytically tractable class of "homogeneous problem solving tasks" with "polynomial width" state spaces.
Datasets
Not discussed in the paper. The paper focuses on theoretical analysis rather than empirical evaluation on specific datasets.
Key Insights and Ideas
- The "Curse of Dimensionality" in RL: Unbiased Q-learning's search time can be exponential in the depth of the state space, making it impractical for large, complex problems.
- Cooperation as a Solution: Intelligent agents in nature don't learn in isolation; they benefit from social structures. LEC and LBW embody this by leveraging external information to guide learning.
- LEC Reduces Feedback Latency: By providing immediate feedback, LEC algorithms significantly speed up learning compared to waiting for environmental rewards.
- LBW Leverages Vicarious Experience: Observing others provides an additional source of learning data, which can be crucial when direct experience is limited or costly.
- Decoupling Search from State Space Size: The core contribution is demonstrating how LEC and LBW can make learning time dependent on the length of the optimal solution path rather than the size of the state space, under certain conditions.
- Importance of Recoverability: For LEC and LBW to achieve their full potential, the agent needs mechanisms to efficiently return to previously visited states or restart tasks. This is crucial for utilizing feedback effectively.
Key Results
- Unbiased Q-learning: For homogeneous problem solving tasks, the expected search time is at least exponentially bounded by the depth of the state space. For polynomial width state spaces, this translates to a search time that is moderately exponential in the state space size.
- LEC (BB-LEC):
- A weak upper bound shows search time is linear in state space size and depth, but inversely proportional to the critic's feedback probability.
- With mechanisms for "undoing" non-optimal actions or restarting tasks, the expected search time becomes linear in the solution length and independent of state space size.
- LBW:
- A population of naive LBW agents can learn at a rate proportional to the inverse of the population size.
- With a skilled role-model, a naive LBW agent can learn the optimal path in time linear to the solution length, independent of state space size, provided it can restart tasks after a certain number of steps.
Limitations and Future Work
- Restricted State Spaces: The analysis is primarily performed on homogeneous, polynomial-width state spaces, which are idealizations. The authors acknowledge that real-world tasks may not perfectly fit these criteria but expect the results to be indicative.
- Naive Critics: LEC algorithms are sensitive to the quality of the critic's feedback. If the critic is poor, the learner can be biased incorrectly.
- Assumption of Recoverability: Many of the strong results for LEC and LBW rely on the agent's ability to efficiently return to previous states or restart tasks. This is not always feasible in all environments.
- Future Work: The authors suggest that LEC and LBW are steps towards supervised learning but aim to retain the autonomy of reinforcement learning. They believe that LEC algorithms could be even more powerful if explicit inversion mechanisms are not required, for instance, if the decision surface is smooth or if policies can be represented by generalizing function approximators. They also note that their simulation studies support the robustness of LEC and LBW to noisy feedback.
Summary updated