Apprentissage par renforcement — Easy21Reinforcement Learning — Easy21
TechnologiesTechnologies (6)
TP de cours RL — implémentation de Sarsa(λ) avec approximation linéaire et Q-Learning sur le jeu de cartes Easy21. Comparaison des algorithmes de la famille TD.RL course lab — implementation of Sarsa(λ) with linear approximation and Q-Learning on the Easy21 card game. Comparison of TD-family algorithms.
Lire la présentation complèteRead the full introduction
TP de cours RL — implémentation de Sarsa(λ) avec approximation linéaire et Q-Learning sur le jeu de cartes Easy21. Comparaison des algorithmes de la famille TD.RL course lab — implementation of Sarsa(λ) with linear approximation and Q-Learning on the Easy21 card game. Comparison of TD-family algorithms.
TP de cours d'apprentissage par renforcement à Polytech Sorbonne, réalisé en binôme.
Le jeu Easy21
Easy21 est une variante simplifiée du Blackjack avec un jeu de cartes infini. Les cartes peuvent être rouges (soustraites, prob. 1/3) ou noires (ajoutées, prob. 2/3). Le joueur peut tirer (hit) ou rester (stick), et est éliminé si sa somme sort de [1, 21].
Ce que j'ai implémenté
- Approximation linéaire de la fonction de valeur : plutôt que stocker une valeur par paire (état, action), on représente Q(s,a) comme un produit scalaire entre un vecteur de caractéristiques binaires ϕ(s,a) ∈ {0,1}^36 et un vecteur de paramètres θ ∈ R^36. Le vecteur de caractéristiques est construit par codage grossier (coarse coding) avec des intervalles qui se chevauchent sur la carte du croupier, la somme du joueur et l'action.
- Sarsa(λ) avec approximation linéaire : traces d'éligibilité accumulées (e_t ← γλe_{t-1} + ϕ), mise à jour des paramètres θ ← θ + α · δ_t · e_t. Testé pour λ ∈ {0, 0.1, ..., 1} sur 1 000 épisodes, avec comparaison de la MSE par rapport aux valeurs vraies Q* obtenues par Monte-Carlo.
- Q-Learning : algorithme hors-politique (off-policy). Contrairement à Sarsa qui suit la politique courante, Q-Learning cible directement la politique greedy : Q(s,a) ← Q(s,a) + α[r + max_a' Q(s',a') - Q(s,a)]. Taux d'exploration ε-greedy variable avec N0 = 100.
Ce que j'ai appris
La différence fondamentale entre algorithmes on-policy (Sarsa, qui apprend la politique qu'il suit) et off-policy (Q-Learning, qui apprend la politique optimale indépendamment de son comportement). Le codage grossier permet une généralisation entre les états voisins, mais au prix d'une précision réduite par rapport à la représentation tabulaire sur un espace d'états aussi petit qu'Easy21.
Reinforcement learning course lab at Polytech Sorbonne, done in pairs.
The Easy21 game
Easy21 is a simplified Blackjack variant with an infinite deck. Cards can be red (subtracted, prob. 1/3) or black (added, prob. 2/3). The player can hit or stick, and busts if their sum leaves [1, 21].
What I implemented
- Linear value function approximation: instead of storing one value per (state, action) pair, Q(s,a) is represented as a dot product between a binary feature vector ϕ(s,a) ∈ {0,1}^36 and a parameter vector θ ∈ R^36. The feature vector is built using coarse coding with overlapping intervals over the dealer card, player sum and action.
- Sarsa(λ) with linear approximation: accumulated eligibility traces (e_t ← γλe_{t-1} + ϕ), parameter update θ ← θ + α · δ_t · e_t. Tested for λ ∈ {0, 0.1, ..., 1} over 1,000 episodes, with MSE compared to the true Q* values from Monte-Carlo.
- Q-Learning: off-policy algorithm. Unlike Sarsa which follows the current policy, Q-Learning targets the greedy policy directly: Q(s,a) ← Q(s,a) + α[r + max_a' Q(s',a') - Q(s,a)]. Variable ε-greedy exploration with N0 = 100.
What I learned
The fundamental difference between on-policy (Sarsa, which learns the policy it follows) and off-policy (Q-Learning, which learns the optimal policy regardless of behavior). Coarse coding enables generalization between neighboring states, but at the cost of reduced precision compared to tabular representation on a state space as small as Easy21.