Q-Value، یادگیری اختلاف زمانی و Q-Learning

دانستن Value بهینهٔ Stateها برای ارزیابی یک Policy مفید است، اما به‌تنهایی Action بهینه را مستقیماً مشخص نمی‌کند. برای این منظور از Q-Value استفاده می‌شود. مقدار بهینهٔ Q*(s,a) مجموع Rewardهای تخفیف‌خورده‌ای است که عامل پس از رسیدن به State s و انتخاب Action a انتظار دارد، با این فرض که پس از آن کاملاً بهینه رفتار کند.

الگوریتم Q-Value Iteration همهٔ Q-Valueها را ابتدا صفر می‌کند و سپس رابطهٔ زیر را بارها به‌روزرسانی می‌کند:

Q_(k+1)(s,a) =
  Σ_s' T(s,a,s') [ R(s,a,s') + γ max_a' Q_k(s',a') ]

وقتی Q-Valueها همگرا شدند، Policy بهینه بسیار ساده است: در هر State، Actionای را انتخاب می‌کنیم که بیشترین Q-Value را دارد.

π*(s) = argmax_a Q*(s,a)

برای MDP فصل، با γ=0.90 پس از Iteration کافی Q-Valueها تقریباً به مقادیر زیر می‌رسند:

[[18.9189, 17.0270, 13.6216],
 [ 0.0000,    -inf, -4.8797],
 [   -inf, 50.1337,    -inf]]

Policy حاصل در Stateهای s0، s1 و s2 به‌ترتیب Actionهای a0، a0 و a1 است. با افزایش Discount Factor به 0.95، Action بهینهٔ State دوم تغییر می‌کند؛ چون عامل برای Reward بزرگ‌تر آینده حاضر می‌شود جریمهٔ کوتاه‌مدت را تحمل کند.

Temporal Difference Learning

در عمل، عامل معمولاً Transition Probabilityها و Rewardهای MDP را از قبل نمی‌داند. TD Learning برای همین شرایط طراحی شده است. عامل محیط را با یک Policy اکتشافی تجربه می‌کند و Value هر State را با مشاهدهٔ Transition واقعی به‌صورت تدریجی اصلاح می‌کند:

V_(k+1)(s) = (1-α)V_k(s) + α[r + γV_k(s')]
δ = r + γV_k(s') - V_k(s)

α Learning Rate، عبارت r + γV(s') هدف TD و δ خطای TD است. این روش از نظر رفتار شبیه Stochastic Gradient Descent است: نمونه‌ها یکی‌یکی پردازش می‌شوند و برای همگرایی دقیق، Learning Rate باید به‌تدریج کاهش یابد.

Q-Learning

Q-Learning همان ایده را مستقیماً روی State-Action Pairها اعمال می‌کند. عامل با مشاهدهٔ تجربه‌های واقعی، Q-Valueها را به‌سمت Reward فعلی به‌علاوهٔ بهترین Q-Value تخفیف‌خوردهٔ State بعدی حرکت می‌دهد:

Q(s,a) ← (1-α)Q(s,a) + α[r + γ max_a' Q(s',a')]

در مثال کوچک فصل، یک Policy کاملاً تصادفی برای Exploration کافی است. Agent بارها State و Action را تجربه می‌کند و Q-Valueها را به‌روز می‌کند:

alpha0 = 0.05
decay = 0.005
gamma = 0.90
state = 0

for iteration in range(10_000):
    action = exploration_policy(state)
    next_state, reward = step(state, action)
    next_value = Q_values[next_state].max()
    alpha = alpha0 / (1 + iteration * decay)
    Q_values[state, action] *= 1 - alpha
    Q_values[state, action] += alpha * (reward + gamma * next_value)
    state = next_state

Q-Value Iteration چون مدل کامل محیط را می‌داند در کمتر از چند ده Iteration همگرا می‌شود، اما Q-Learning باید محیط را تجربه کند و در مثال کتاب حدود هزاران Iteration لازم دارد.

Q-Learning یک الگوریتم Off-Policy است: Policy مورد استفاده برای Exploration می‌تواند با Policy هدف متفاوت باشد. در مقابل، Policy Gradient نمونهٔ On-Policy است، چون همان Policyای که در حال Train شدن است محیط را نیز Explore می‌کند.

سیاست‌های Exploration

Exploration کاملاً تصادفی از نظر تئوری همهٔ Stateها را می‌بیند، اما ممکن است بسیار کند باشد. روش متداول‌تر ε-greedy است: با احتمال ε Action تصادفی و با احتمال 1-ε بهترین Action فعلی انتخاب می‌شود. معمولاً ε از مقدار بزرگی مثل 1.0 شروع و به مقدار کوچکی مثل 0.05 کاهش داده می‌شود.

روش دیگر افزودن یک Bonus برای Actionهای کم‌تجربه است:

f(Q,N) = Q + κ / (1 + N)

N(s,a) تعداد دفعاتی است که Action در State مشخص انتخاب شده و κ میزان کنجکاوی عامل را کنترل می‌کند.

Approximate Q-Learning و Deep Q-Learning

نگهداری یک Q-Value جداگانه برای تمام State-Action Pairها در مسئله‌های بزرگ غیرممکن است. در بازی‌هایی مانند Ms. Pac-Man تعداد Stateها نجومی است. راه‌حل این است که یک تابع پارامتری Qθ(s,a) Q-Value را تقریب بزند. اگر این تابع یک شبکهٔ عصبی عمیق باشد، آن را Deep Q-Network یا DQN می‌نامیم.

هدف Train کردن DQN از معادلهٔ Bellman می‌آید:

y(s,a) = r + γ max_a' Qθ(s',a')

مدل باید مقدار Qθ(s,a) را به این Target نزدیک کند؛ معمولاً MSE یا Huber Loss برای این کار استفاده می‌شود.

پیاده‌سازی Deep Q-Learning برای CartPole

به‌جای وارد کردن هم State و هم Action به شبکه، کارآمدتر است که State وارد شود و شبکه برای تمام Actionهای ممکن یک Q-Value خروجی دهد:

input_shape = [4]
n_outputs = 2

model = tf.keras.Sequential([
    tf.keras.layers.Dense(32, activation="elu", input_shape=input_shape),
    tf.keras.layers.Dense(32, activation="elu"),
    tf.keras.layers.Dense(n_outputs)
])

Policy ε-greedy یا Action تصادفی انتخاب می‌کند یا Action دارای بیشترین Q-Value را برمی‌گزیند. برای کاهش همبستگی میان تجربه‌های متوالی، Experienceها در یک Replay Buffer ذخیره می‌شوند و هر مرحلهٔ Train از یک Batch تصادفی نمونه می‌گیرد:

from collections import deque
replay_buffer = deque(maxlen=2000)

def sample_experiences(batch_size):
    indices = np.random.randint(len(replay_buffer), size=batch_size)
    batch = [replay_buffer[index] for index in indices]
    return [
        np.array([experience[field_index] for experience in batch])
        for field_index in range(6)
    ]

هر Experience شامل State، Action، Reward، State بعدی، done و truncated است. در Training Step ابتدا برای Stateهای بعدی Q-Valueها پیش‌بینی می‌شوند، بیشترین Q-Value هر State استخراج می‌شود، Target محاسبه می‌گردد و سپس فقط Q-Value مربوط به Action واقعاً اجراشده در Loss شرکت می‌کند:

batch_size = 32
discount_factor = 0.95
optimizer = tf.keras.optimizers.Nadam(learning_rate=1e-2)

def training_step(batch_size):
    states, actions, rewards, next_states, dones, truncateds =         sample_experiences(batch_size)

    next_Q_values = model.predict(next_states, verbose=0)
    max_next_Q_values = next_Q_values.max(axis=1)
    runs = 1.0 - (dones | truncateds)
    target_Q_values = rewards + runs * discount_factor * max_next_Q_values
    target_Q_values = target_Q_values.reshape(-1, 1)

    mask = tf.one_hot(actions, n_outputs)
    with tf.GradientTape() as tape:
        all_Q_values = model(states)
        Q_values = tf.reduce_sum(all_Q_values * mask, axis=1, keepdims=True)
        loss = tf.reduce_mean(tf.keras.losses.mean_squared_error(
            target_Q_values, Q_values))
    grads = tape.gradient(loss, model.trainable_variables)
    optimizer.apply_gradients(zip(grads, model.trainable_variables))

Training برای ۶۰۰ Episode انجام می‌شود. ε از 1 به 0.01 کاهش می‌یابد و پس از پر شدن اولیهٔ Replay Buffer، در هر Step یک Training Step اجرا می‌شود.

ناپایداری و Catastrophic Forgetting

منحنی Reward نشان می‌دهد Deep Q-Learning ممکن است پس از پیشرفت ناگهان افت شدیدی داشته باشد. یکی از علت‌ها Catastrophic Forgetting است: یادگیری در بخش تازه‌ای از محیط می‌تواند دانشی را که مدل قبلاً دربارهٔ بخش دیگری آموخته خراب کند. Experienceها همبسته‌اند و توزیع داده دائماً با تغییر Policy جابه‌جا می‌شود. بزرگ‌تر کردن Replay Buffer و تنظیم Learning Rate می‌تواند کمک کند، اما RL ذاتاً نسبت به Hyperparameter و Random Seed حساس است.

در RL، Loss همیشه معیار خوبی برای Performance نیست؛ ممکن است Loss پایین بیاید ولی Reward بدتر شود، یا برعکس. بنابراین بهتر است Reward واقعی Episodeها را رسم و Monitor کرد.

گونه‌های پایدارتر Deep Q-Learning

Fixed Q-Value Targets

اگر یک شبکه هم Q-Value را پیش‌بینی کند و هم Target خودش را بسازد، Feedback Loop می‌تواند Training را ناپایدار کند. راه‌حل DeepMind استفاده از دو شبکه است: Online Model که دائماً Train می‌شود و Target Model که فقط برای ساخت Target استفاده می‌شود و با فاصلهٔ زمانی از Online Model کپی می‌گردد.

target = tf.keras.models.clone_model(model)
target.set_weights(model.get_weights())

# periodically
target.set_weights(model.get_weights())

در نسخهٔ Atari، Learning Rate بسیار کوچک، Replay Buffer بسیار بزرگ و Update Target بسیار کم‌دفعات‌تر انجام می‌شد.

Double DQN

Target Network تمایل دارد Q-Valueها را بیش‌برآورد کند، چون همواره بزرگ‌ترین مقدار تخمینی را انتخاب می‌کند. در Double DQN، Online Model بهترین Action برای State بعدی را انتخاب می‌کند، اما Target Model فقط Q-Value همان Action را ارزیابی می‌کند. این جداسازی Bias انتخاب را کاهش می‌دهد.

Prioritized Experience Replay

به‌جای Sampling یکنواخت از Replay Buffer، Experienceهایی که TD Error بزرگ‌تری دارند بیشتر انتخاب می‌شوند، چون احتمالاً اطلاعات بیشتری برای یادگیری دارند. Priority معمولاً با |δ| مرتبط است. چون Sampling دیگر بی‌طرف نیست، وزن Training هر Sample باید برای جبران Bias کاهش داده شود. دو Hyperparameter شدت اولویت‌بندی و میزان جبران Bias را کنترل می‌کنند.

Dueling DQN

در Dueling DQN شبکه به‌جای تخمین مستقیم Q-Value، دو مؤلفه را جدا می‌آموزد: Value مربوط به State و Advantage مربوط به هر Action. سپس آن‌ها ترکیب می‌شوند:

Q(s,a) = V(s) + A(s,a)

مدل کتاب از Functional API استفاده می‌کند و بیشترین Advantage را از همهٔ Advantageها کم می‌کند تا بهترین Action Advantage صفر داشته باشد. این روش را می‌توان با Double DQN و Prioritized Replay ترکیب کرد. DeepMind در عامل Rainbow چندین بهبود را با هم ترکیب کرد و Performance بسیار بالاتری به دست آورد.

مروری بر چند الگوریتم مهم دیگر RL

• AlphaGo / AlphaZero / MuZero: ترکیب Monte Carlo Tree Search با Neural Networkها برای انتخاب Action و ارزیابی State. AlphaZero ایده را به Go، Chess و Shogi تعمیم داد و MuZero حتی بدون دانستن قوانین محیط Model داخلی مناسبی می‌آموزد.
• Actor-Critic: یک Policy Network نقش Actor و یک Value/Q Network نقش Critic را دارد. Critic به Actor بازخورد سریع‌تری دربارهٔ کیفیت Action می‌دهد.
• A3C: چند Agent به‌صورت Asynchronous محیط‌های جداگانه را Explore می‌کنند و Updateهای خود را به شبکهٔ مرکزی می‌فرستند.
• A2C: نسخهٔ Synchronous از A3C است و به‌دلیل Batchهای بزرگ‌تر از GPU بهتر استفاده می‌کند.
• Soft Actor-Critic (SAC): علاوه بر Reward، Entropy Actionها را نیز بیشینه می‌کند تا Exploration حفظ شود و Sample Efficiency بهتر شود.
• PPO: Updateهای Policy را محدود می‌کند تا تغییرات خیلی بزرگ و ناپایدار رخ ندهند. این الگوریتم ساده‌تر از TRPO است و در OpenAI Five نیز استفاده شد.
• Curiosity-Based Exploration: عامل برای تجربه‌هایی که پیش‌بینی نتیجهٔ آن‌ها دشوار است Reward درونی می‌گیرد و از این راه بدون Reward محیط نیز Explore می‌کند.
• Open-Ended Learning: محیط‌ها و چالش‌های تازه به‌طور پیوسته تولید می‌شوند تا Agent دائماً مهارت جدید بیاموزد. POET نمونه‌ای از این خانواده است که Curriculum را به‌صورت خودکار سخت‌تر می‌کند.

فصل با این نکته پایان می‌یابد که RL حوزه‌ای بسیار گسترده و سریع‌التغییر است و موضوعات Policy Gradient، Markov Chain، MDP، Q-Learning، DQN و بهبودهای مختلف آن تنها بخش کوچکی از این فضا هستند.

تمرین‌های فصل ۱۸

1. تعریف RL و تفاوت آن با Supervised و Unsupervised Learning را توضیح دهید.
2. سه کاربرد جدید برای RL پیشنهاد کنید و Environment، Agent، Action و Reward هرکدام را مشخص کنید.
3. Discount Factor چیست و آیا تغییر آن می‌تواند Policy بهینه را عوض کند؟
4. Performance یک Agent چگونه اندازه‌گیری می‌شود؟
5. Credit Assignment چه مشکلی است و چگونه می‌توان آن را کاهش داد؟
6. Replay Buffer چه فایده‌ای دارد؟
7. الگوریتم Off-Policy چیست؟
8. با Policy Gradient محیط LunarLander-v2 را حل کنید.
9. با Double Dueling DQN عامل Breakout بسازید؛ Observationهای تصویری را Gray، Crop و Downsample کنید و چند Frame متوالی را در State قرار دهید.
10. در صورت دسترسی به Raspberry Pi و قطعات رباتیک، یک عامل ساده بسازید و سپس از Deep Learning یا RL برای کنترل رفتار آن استفاده کنید.