Study Notes on Learning in Reinforcement Learning

Overview of Learning in Reinforcement Learning

• Introduction to Learning

  • Focus on reinforcement learning and Markov decision processes (MDPs).
  • Connection between search, planning problems, and mathematical frameworks.
  • Outline of course structure: search problems, learning, uncertainty management, and machine learning.

• Upcoming Units

  • Transition to a deep dive into learning, particularly neural network approximators.
  • Upcoming topics include Bayes nets, Markov models, and machine learning frameworks.

Reinforcement Learning Fundamentals

• Core Concepts of Reinforcement Learning

  • MDPs consist of a set of states, actions, and a model that describes transitions between states.
  • Reinforcement learning involves learning from experience to improve decision-making.
  • Key terms include state (s), action (a), and resulting state (s').

• Transition Notation

  • Notation for transitions: (s, a, s') represents state, action, and resulting state.
  • Reward is defined as the outcome of the transition, noted as r for (s, a, s').
  • Learning process involves updating values based on observed transitions.

Objectives in Reinforcement Learning

• Policy and Value Functions

  • Policy (π) is a mapping from states to actions.
  • Value function (V) represents expected rewards from a given state, while Q-value (Q) represents expected rewards for action taken in that state.
  • Optimal policies yield maximum expected rewards.

• Learning Transition Models

  • Importance of learning the transition function (T) and reward function (R) based on experiences.
  • Learning typically involves averaging rewards and future state values to derive Q-values.

Learning Techniques in Reinforcement Learning

• Model-Free vs Model-Based Learning

  • Model-Based Learning: Building an approximate MDP based on collected counts of transitions and rewards.
  • Model-Free Learning: Directly learning about value functions without constructing a model of the environment.

• Temporal Difference Learning

  • Definition: Learning from the difference between estimated values at successive time steps.
  • Directly relates current estimates of value to future estimates based on observed experiences.

• Temporal Difference Update Mechanics

  • Use of empirical running averages for updates instead of model-based probabilities.
  • Q-learning update rule incorporates immediate rewards and expected future rewards:
    $Q(s, a) := Q(s, a) + \alpha \left[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \right]$
    where ( \alpha ) is the learning rate and ( \gamma ) is the discount factor.

Q-Learning and Its Mechanism

• Understanding Q-Learning

  • Q-values are updated based on received rewards and discounting future expected rewards.
  • The update process must incorporate the exploration of states through various actions.

• Exploration Techniques

  • Random exploration leads to learning but can lead to high regret due to many suboptimal actions.
  • Epsilon-greedy methods balance exploration and exploitation, randomly selecting actions to discover new states.

Exploration vs Exploitation Trade-off

• Exploration Strategies

  • Epsilon-greedy strategy involves mostly choosing the best-known action but occasionally exploring other options.
  • Alternative strategies prioritize exploring states with uncertain outcomes, maintaining a balanced learning process.

• Deferred Learning Rate Adjustment

  • Slow down epsilon over time to encourage more exploitation as learning progresses.
  • Strategies to maximize learning efficiency while minimizing regret are key.

Approximate Q-Learning and Feature Representations

• Challenges with Exact Q-Learning

  • Difficulty in storing and retrieving large state-action pairs in systems with vast state spaces (e.g., Pac-Man).
  • Approximation becomes essential for practical implementation of Q-learning in real-world scenarios.

• Feature-Based Learning

  • Utilize feature functions to represent states more abstractly.
  • Example features might include distance to nearest ghost or distance to nearest food dot.
  • Update Q-values based not only on individual states but also feature representation:
    $Q(s, a) = w<em>1 * feature</em>1(s) + w<em>2 * feature</em>2(s) + … + w<em>n * feature</em>n(s)$
    where ( w_i ) are the weights to be learned.

• Weight Adjustment Algorithm

  • Adjustment of weights based on received transitions through proportional adjustment based on errors:
    $w<em>i := w</em>i + \alpha * error * feature_i(s)$
    where the error is the difference between expected and actual outcomes.

• Implications of Approximate Q-Learning

  • Generalization allows for faster learning across similar states without needing to explore every individual state-action pair.
  • Balancing feature extraction and learning weights allows for efficient reinforcement learning in complex environments.