Abstract
Imitation learning has been widely used to speed up learning in novice agents, by allowing them to leverage existing data from experts. Allowing an agent to be influenced by external observations can benefit the learning process, but it also puts the agent at risk of following sub-optimal behaviors. In this paper, we study this problem in the context of bandits. More specifically, we consider that an agent (learner) is interacting with a bandit-style decision task, but can also observe a target policy interacting with the same environment. The learner observes only the target’s actions, not the rewards obtained. We introduce a new bandit optimism modifier that uses conditional optimism contingent on the actions of the target in order to guide the agent’s exploration. We analyze the effect of this modification on the well-known Upper Confidence Bound algorithm by proving that it preserves a regret upper-bound of order O(lnT), even in the presence of a very poor target, and we derive the dependency of the expected regret on the general target policy. We provide empirical results showing both great benefits as well as certain limitations inherent to observational learning in the multi-armed bandit setting. Experiments are conducted using targets satisfying theoretical assumptions with high probability, thus narrowing the gap between theory and application.
Introduction: The Challenge of Observational Learning
In the classic multi-armed bandit problem, an agent must maximize rewards by balancing the exploration of new arms with the exploitation of known ones. Traditionally, agents learn solely from their own experiences. However, real-world scenarios often involve observational learning, where we observe the actions of others without knowing their outcomes—such as seeing which products a competitor prioritizes without knowing their sales figures.
This presents a dual challenge: how to leverage the "popularity" of an action among peers to accelerate learning, while simultaneously managing the risk of being misled by sub-optimal or irrational "targets."
Methodology: The Target-UCB Algorithm
To address this, researchers from McGill University developed Target-UCB, an extension of the standard Upper Confidence Bound (UCB) algorithm. While standard UCB relies on an empirical average and an exploration bonus based on uncertainty, Target-UCB introduces a third component: Target Optimism.
- The Mechanism: The algorithm monitors the discrepancy between the number of times a target has chosen an arm versus the learner's own choices.
- Conditional Optimism: If a target selects an arm frequently, the learner becomes "optimistic" about that arm and is nudged to explore it. As the learner gathers its own reward data, this external influence fades, allowing the agent to rely on its own empirical evidence.
- Theoretical Robustness: The authors mathematically demonstrate that Target-UCB maintains "logarithmic regret" (O(lnT)), ensuring that even if the observed target is highly sub-optimal, the learner will not perform significantly worse than a standard agent in the long run.
Experimental Evaluation
The algorithm was tested across three distinct environments:
- Synthetic Bernoulli Bandits: Controlled settings used to test robustness against varying target qualities (from 90% optimal to 0.1% optimal).
- Graph-Based Social Simulations: Agents arranged in structures like cliques, chains, and "small-world" networks to observe how social topology affects learning.
- Human Subject Data: Utilizing real-world data from psychology experiments, where the algorithm used human actions as its target.
Key Insights and Results
Robustness and Performance Gains
Target-UCB demonstrates a remarkable ability to filter noise. When observing a "good" target, the algorithm reaches optimal actions significantly faster than a lone UCB agent. Crucially, as shown in Figure 2, even when the target is nearly random or poor ($\alpha = 0.001$), Target-UCB does not fail; it eventually reverts to standard learning behavior once its own reward data contradicts the target's actions.
The Power of Social Structures
In multi-agent settings, the algorithm benefits from "clique averaging." By observing multiple neighbors, the learner can filter out the noise of a single unlucky peer. This collective intelligence allows Target-UCB to often outperform the very "teachers" it is observing.
Human-in-the-Loop
When applied to human action data, Target-UCB successfully leveraged human intuition. Despite humans not following mathematically optimal exploration strategies, the algorithm used their choices as a proxy for value to find optimal arms more rapidly than standard methods.
Conclusion and Future Directions
Target-UCB provides a robust framework for observational learning, bridging the gap between blind imitation and isolated learning. While the algorithm is implicitly robust, future work could focus on explicit detection—allowing an agent to identify and ignore a bad target earlier in the process. Additionally, exploring "restless" bandits, where reward probabilities change over time, could yield insights into complex social phenomena like herding and the impact of online influencers.
Summary updated