Exploration-Exploitation Tradeoff

A Bayesian probability matching strategy. The agent maintains a probability distribution (posterior) over the expected reward of each action. On each round, it samples a reward estimate from each distribution and selects the action with the highest sampled value.

• Pro: Naturally balances exploration; uncertainty is encoded in the distribution's variance.
• Con: Computationally more intensive than epsilon-greedy; requires maintaining and updating posteriors.

Actions are selected probabilistically based on their estimated values, using a softmax function. The probability of choosing action a is proportional to exp(Q(a) / τ), where τ is a temperature parameter.

• High τ: All actions have nearly equal probability (high exploration).
• Low τ: The highest-value action is chosen with probability near 1 (high exploitation).
• Pro: Explores promising actions more than poor ones.
• Con: Sensitive to the scaling of reward estimates and the temperature schedule.

An extension where decisions are informed by contextual features (e.g., user profile, time of day). The agent learns a policy that maps contexts to actions, allowing it to generalize exploration across similar situations.

• Example: A news recommender explores different article categories for a new user but can exploit known preferences for a returning user.
• Key Algorithm: Often uses linear models with UCB or Thompson Sampling (LinUCB, Linear Thompson Sampling).

A meta-strategy applied to parameters like ε in epsilon-greedy or τ in softmax. The exploration rate is systematically reduced over time according to a schedule (e.g., exponential decay, 1/t).

• Rationale: High exploration is crucial early to gather information, but the system should converge to stable exploitation as knowledge becomes certain.
• Implementation: ε_t = ε_0 * decay_rate^t or ε_t = 1 / sqrt(t).
• Challenge: Setting the correct decay rate requires domain knowledge to avoid premature convergence to a sub-optimal policy.

A heuristic search algorithm for optimal decision-making in sequential decision processes, like games, that explicitly manages exploration and exploitation.

• Four-Step Loop: Operates through Selection (traversing the tree using a policy like UCB), Expansion (adding a new child node), Simulation (running a random playout), and Backpropagation (updating node statistics).
• Exploration-Exploitation in UCT: The Upper Confidence Bound for Trees (UCT) formula balances choosing nodes with high average reward (exploitation) against nodes with few visits (exploration).
• Famous Use Case: A key component of AlphaGo and AlphaZero, where it was used to explore possible move sequences and exploit promising lines of play.

A Bayesian probability matching algorithm for solving the multi-armed bandit problem. It provides a principled, often highly efficient, method for balancing exploration and exploitation.

• Mechanism: The algorithm maintains a posterior probability distribution for the reward of each arm. On each trial, it samples a reward estimate from each distribution and selects the arm with the highest sampled value.
• Natural Balance: Arms with uncertain (high-variance) distributions are more likely to be sampled, leading to exploration. As evidence accumulates, the distributions concentrate on the true means, leading to exploitation.
• Advantage: It automatically adjusts the exploration rate based on uncertainty, often outperforming fixed strategies like ε-greedy in cumulative regret.

A deterministic algorithm for the multi-armed bandit problem that selects actions based on an optimistic estimate of their potential reward.

• Core Principle: For each arm, calculate an index: UCB(i) = average_reward(i) + c * sqrt(ln(total_pulls) / pulls(i)). The constant c controls the exploration weight.
• Optimism in the Face of Uncertainty: The added confidence interval term (c * sqrt(...)) is larger for less-tried arms, encouraging their exploration. As an arm is pulled more, this term shrinks, leading to exploitation of its known average.
• Theoretical Guarantee: UCB1 and its variants provide strong bounds on cumulative regret, making it a theoretically well-understood and widely applied algorithm.

In reinforcement learning, internal reward signals designed to encourage an agent to explore its environment beyond extrinsic (goal-oriented) rewards.

• Purpose: To overcome sparse reward problems where extrinsic feedback is rare, preventing the agent from learning useful behaviors.
• Common Forms:
  • Curiosity-Driven: Reward for predicting the outcome of its own actions (prediction error).
  • Novelty-Seeking: Reward for visiting states that are rare or unseen in its experience.
  • Skill/Goal Discovery: Reward for learning diverse skills or achieving self-set goals.
• Role in Tradeoff: Provides a systematic exploration drive, ensuring the agent gathers diverse experience before exploiting a narrow, known policy.