Reinforcement learning प्लेग्राउंडमध्यमपाठ 2906 मिनट का पाठ

Multi-armed bandits

सबसे आसान RL गेम: कई सारे विकल्प, और हर एक में रिवॉर्ड मिलने का एक छिपा हुआ मौका। सीखिए epsilon-greedy, जो आज़माने और इस्तेमाल करने के बीच संतुलन बनाने का क्लासिक तरीका है।

✦ ट्यूटर से पूछें 🧪 लैब · 25 min 📝 पाठ का टेस्ट

स्पीड

पाठ वीडियो में

60 सेकंड में

Multi-armed bandits

1/4

आसान शब्दों में

एक नए रेलवे स्टेशन पर चाय के पाँच स्टॉल हैं। कुछ बढ़िया चाय बनाते हैं, कुछ फीकी, लेकिन सिर्फ देखकर यह पता नहीं लगाया जा सकता। अगर आप हमेशा उसी पहले स्टॉल पर जाते रहेंगे जो आपको पसंद आया था, तो हो सकता है कि आप उससे भी बेहतर स्टॉल से चूक जाएँ। अगर आप हर रोज़ किसी भी रैंडम स्टॉल पर जाएँगे, तो आपको कई बार खराब चाय पीनी पड़ेगी। तो फिर आप कैसे चुनेंगे?

एक multi-armed bandit कई विकल्पों वाला एक गेम है, जिन्हें arms कहा जाता है। यह नाम कसीनो की स्लॉट मशीनों से आया है, जिन्हें कभी "one-armed bandits" कहा जाता था। हर arm एक छिपे हुए औसत के साथ रिवॉर्ड देता है। इसमें केवल एक ही स्टेट होती है: हर राउंड में, आपके सामने वही विकल्प दोबारा होते हैं। तो बस एक ही सवाल है: इस बार कौन-सा arm?

स्कोर याद रखना: रनिंग एवरेज

हर arm के लिए, एजेंट उसके औसत रिवॉर्ड का एक अनुमान Q[arm], और उसे कितनी बार आज़माया गया इसकी गिनती N[arm] रखता है। हर बार खींचने (pull) के बाद, वह अपने अनुमान को नए रिवॉर्ड की तरफ थोड़ा खिसकाता है:

The running-average updatepython

Q, N = [0.0, 0.0, 0.0], [0, 0, 0]    # estimates and counts for three stalls
arm = 2
for reward in [1, 0, 1, 1]:           # four visits to stall 2
    N[arm] += 1
    Q[arm] += (reward - Q[arm]) / N[arm]    # move a bit toward the new reward
    print(f"after reward {reward}: Q[2] = {Q[arm]:.3f}")

इससे पूरी लिस्ट सेव किए बिना, उस arm से मिले सभी रिवॉर्ड्स का बिल्कुल सही औसत मिल जाता है। यही "पुराना अनुमान और नई जानकारी की तरफ एक कदम" वाला पैटर्न आगे चलकर Q-learning में भी देखने को मिलेगा।

Explore करें या exploit?

हमेशा exploit करें (greedy)

हमेशा वही arm चुनता है जो अब तक सबसे अच्छा लगा हो
ऐसे arm पर अटक सकता है जो शुरुआत में किस्मत से अच्छा निकल गया था
यह कभी जान ही नहीं पाता कि कोई दूसरा arm इससे बेहतर है

हमेशा explore करें (रैंडम)

बराबरी के मौके के साथ किसी भी arm को चुन लेता है
हर arm के बारे में सीखता है
हमेशा खराब arms पर अपनी बारी बेकार करता रहता है

Epsilon-greedy इन दोनों को मिला देता है। epsilon नाम का एक छोटा नंबर चुनें, जैसे कि 0.1। हर राउंड में, epsilon संभावना के साथ कोई रैंडम arm चुनें (explore)। बाकी समय सबसे ज़्यादा Q वाला arm चुनें (exploit)। अगर दो arms के बीच टाई हो जाए, तो उनमें से किसी एक को रैंडमली चुन लें, ताकि गलती से भी किसी एक arm का पक्ष न लिया जाए।

Python: a greedy agent can get stuckpython

import random

probs = [0.4, 0.8]           # arm 1 is clearly better, but the agent does not know
def run(epsilon, seed):
    rng = random.Random(seed)
    Q, N = [0.0, 0.0], [0, 0]
    for t in range(500):
        if rng.random() < epsilon:
            arm = rng.randrange(2)
        else:
            arm = 0 if Q[0] >= Q[1] else 1       # greedy; ties go to arm 0
        r = 1 if rng.random() < probs[arm] else 0
        N[arm] += 1
        Q[arm] += (r - Q[arm]) / N[arm]
    return N

for eps in (0.0, 0.1):
    print(f"epsilon={eps}: pulls per arm = {run(eps, seed=3)}")

epsilon=0 होने पर, एजेंट सबसे पहले arm 0 को आज़माता है, कुछ रिवॉर्ड पाता है, और फिर उसके पास arm 1 को आज़माने की कोई वजह नहीं होती। थोड़े से exploration के साथ, उसे जल्द ही पता चल जाता है कि arm 1 बेहतर है और वह ज़्यादातर समय उसी का इस्तेमाल करता है।

Bandits कहाँ काम आते हैं

डिज़ाइन की टेस्टिंग: कुछ वेबसाइटें और ऐप्स किसी बटन या हेडलाइन के कई वर्शन आज़माने के लिए bandit के तरीकों का इस्तेमाल करते हैं, और धीरे-धीरे ज़्यादा लोगों को उस वर्शन पर भेजते हैं जो सबसे अच्छा काम करता है।
रेकमेंडेशन: यह चुनना कि कौन-सा आइटम दिखाया जाए, और साथ ही नए आइटम्स को भी आज़माते रहना ताकि उन्हें भी सही मौका मिले।
रोज़मर्रा की ज़िंदगी: कोई रेस्टोरेंट चुनना, कॉलेज जाने का रास्ता चुनना, या ट्यूशन टीचर चुनना भी एक bandit समस्या ही है।

सावधान रहें

जब असली लोग "arms" या दर्शक होते हैं, तो exploration मुफ़्त नहीं होता। किसी को खराब विकल्प दिखाने का सचमुच नुकसान होता है। गंभीर मामलों में सावधानी, सीमाओं और सेहत या लोन जैसी चीज़ों के लिए इंसानी समीक्षा (human review) व उस क्षेत्र के नियमों की ज़रूरत होती है।

नोट

Bandit के दूसरे तरीके epsilon-greedy से ज़्यादा समझदारी से explore करते हैं। इनमें से दो मशहूर तरीके हैं upper confidence bound (UCB), जो सिर्फ कुछ ही बार आज़माए गए arms को बोनस देता है, और Thompson sampling, जो arms को इस आधार पर चुनता है कि उनके सबसे अच्छे होने की कितनी संभावना है। शुरुआत करने के लिए Epsilon-greedy सबसे आसान तरीका है।

इसे आज़माएँ। ऊपर दिए गए कोड में, probs को बदलकर [0.75, 0.8] कर दें। अब दोनों arms बहुत करीब हैं। क्या epsilon = 0.1 अब भी 500 राउंड में बेहतर arm को खोज पाता है? यह ज़्यादा मुश्किल क्यों है?

और देखें और पढ़ें

लैब

एक epsilon-greedy चाय-स्टॉल एजेंट जो सबसे अच्छा स्टॉल ढूँढता है और ज़्यादातर समय उसी का इस्तेमाल करता है।

~25 min

समस्या

पाँच चाय स्टॉल हैं और हर एक से एक छिपी हुई संभावना के साथ बढ़िया चाय (रिवॉर्ड 1) मिलती है। शुरुआती कोड का choose सीखी हुई हर बात को नज़रअंदाज़ करता है और हमेशा रैंडम तरीके से चुनता है।

Run दबाएँ। हर epsilon एक जैसा खराब परिणाम देता है, क्योंकि choose कभी भी epsilon या Q का इस्तेमाल नहीं करता।
choose में epsilon-greedy लिखें: epsilon संभावना के साथ एक रैंडम स्टॉल लौटाएँ; बाकी समय सबसे ज़्यादा Q वाला स्टॉल लौटाएँ। अगर कई स्टॉल सबसे ज़्यादा मान पर टाई होते हैं, तो rng का इस्तेमाल करके उनमें से किसी एक को रैंडमली चुनें।
फिर से रन करें और epsilon = 0, 0.1, 0.3 और 1.0 की तुलना करें। किसका औसत रिवॉर्ड सबसे अच्छा है? कौन-सा सबसे ज़्यादा बार सबसे अच्छा स्टॉल ढूँढ पाता है?
Check दबाएँ। यह छह नए स्टेशन लेआउट्स पर आपके एजेंट की जाँच करता है।
दो वाक्य लिखें कि epsilon = 0 कभी अच्छा और कभी खराब प्रदर्शन क्यों करता है।

प्रैक्टिस लैब

कोड में बदलाव करें और इसे रन करें। Python आपके ब्राउज़र में चलता है — हमारे सर्वर पर कुछ नहीं भेजा जाता।

रन करने के लिए Ctrl + Enter दबाएं

import random

# Five chai stalls. PROBS holds each stall's hidden chance of a great cup.
PROBS = [0.3, 0.55, 0.2, 0.75, 0.45]

def choose(Q, epsilon, rng):
    """Epsilon-greedy: with chance epsilon pick a random stall, else the best-looking one."""
    # TODO: this version always picks at random. Use epsilon and Q.
    return rng.randrange(len(Q))

def update(Q, N, arm, reward):
    """Running average of the rewards seen from each stall."""
    N[arm] += 1
    Q[arm] += (reward - Q[arm]) / N[arm]

def run(probs, steps=2000, epsilon=0.1, seed=0):
    rng = random.Random(seed)
    Q, N = [0.0] * len(probs), [0] * len(probs)
    picks, total = [], 0
    for _ in range(steps):
        arm = choose(Q, epsilon, rng)
        reward = 1 if rng.random() < probs[arm] else 0
        update(Q, N, arm, reward)
        picks.append(arm)
        total += reward
    return picks, total / steps, Q

best = PROBS.index(max(PROBS))
for eps in (0.0, 0.1, 0.3, 1.0):
    avgs, shares = [], []
    for seed in range(5):                       # five runs, each with its own luck
        picks, avg, Q = run(PROBS, epsilon=eps, seed=seed)
        avgs.append(avg)
        shares.append(picks[-1000:].count(best) / 1000)
    per_seed = " ".join(f"{x:.0%}" for x in shares)
    print(f"epsilon={eps:<4} average reward={sum(avgs) / 5:.3f}   best stall share in last 1000, per seed: {per_seed}")

आउटपुट

कोई आउटपुट नहीं। वैल्यूज़ देखने के लिए print(...) जोड़ें।

आपका काम तब पूरा होगा जब

choose, epsilon संभावना के साथ एक रैंडम स्टॉल और बाकी समय सबसे ज़्यादा Q वाला स्टॉल लौटाता है
टाई होने पर रैंडम तरीके से फैसला होता है, हमेशा पहले स्टॉल की तरफ नहीं
तुलना से पता चलता है कि epsilon = 1.0 का औसत रिवॉर्ड सबसे कम है, और एक छोटा epsilon कुल मिलाकर सबसे अच्छा प्रदर्शन करता है
लिखित उत्तर में यह समझाया गया है कि epsilon = 0 शुरुआती किस्मत पर निर्भर करता है

कठिन सवाल

उत्तर देखने से पहले ख़ुद जवाब देने की कोशिश करें। अगर आप इनके जवाब दे सकते हैं, तो आप पाठ समझ गए हैं।

Q1epsilon = 0.1 और पाँच स्टॉल होने पर, लंबे समय में सबसे अच्छे स्टॉल को विज़िट का अधिकतम कितना हिस्सा मिल सकता है?दिखाएं

लगभग 92%। एजेंट 90% समय exploit करता है और तब सबसे अच्छा स्टॉल चुनता है। जब वह explore करता है (10%), तो वह रैंडम तरीके से चुनता है, और पाँच में से एक बार वह रैंडम चुनाव भी सबसे अच्छा स्टॉल ही होता है: 0.9 + 0.1 x 0.2 = 0.92। इसी ऊपरी सीमा की वजह से लोग समय के साथ epsilon को कम करते हैं।

Q2सभी अनुमान 0 से शुरू होते हैं। क्या होगा अगर आप epsilon = 0 के साथ उन्हें 1.0 से शुरू करें?दिखाएं

इसे optimistic initial values कहा जाता है। हर वह स्टॉल जिसे आज़माया नहीं गया है वह एकदम सही लगता है, इसलिए greedy एजेंट उसे आज़माता है, निराश होता है (औसत 1 से नीचे गिर जाता है), और अगले अन-आज़माए हुए स्टॉल पर बढ़ जाता है। इसलिए वह बिना किसी रैंडमनेस के भी शुरुआत में ही हर स्टॉल को explore कर लेता है। यह आसान समस्याओं के लिए एक बढ़िया तरकीब है, लेकिन यह केवल शुरुआत में ही explore करने के लिए बढ़ावा देती है।

जारी रखने के लिए कृपया साइन इन करें।

अक्सर पूछे जाने वाले सवाल

कुछ देर के लिए explore और फिर हमेशा के लिए exploit क्यों न करें?

यह एक अच्छी रणनीति है, जिसे "explore then commit" कहा जाता है। इसकी कमी यह तय करने में है कि कितनी देर तक explore किया जाए: बहुत कम समय दें तो हो सकता है आप गलत arm चुन लें, और बहुत ज़्यादा समय दें तो आपकी कई बारियाँ बर्बाद हो जाएँगी। Epsilon-greedy हमेशा थोड़ी मात्रा में exploration जारी रखता है, जिससे तब भी मदद मिलती है जब समय के साथ arms बदल रहे हों।

क्या होगा अगर समय के साथ रिवॉर्ड्स बदल जाएँ?

तब एक साधारण औसत बहुत धीमी गति से सीखता है, क्योंकि पुराने रिवॉर्ड्स का महत्व भी नए रिवॉर्ड्स जितना ही होता है। इसका एक आम उपाय है एक निश्चित स्टेप साइज़ रखना, जैसे Q += 0.1 * (reward - Q), जो हाल ही में मिले रिवॉर्ड्स को ज़्यादा महत्व देता है।

क्या 0.1 हमेशा सही epsilon होता है?

नहीं। यह शुरुआत करने के लिए एक सामान्य मान है। लैब आपको अलग-अलग वैल्यूज़ की तुलना करने की सुविधा देती है। अगली यूनिट में बताया जाएगा कि कैसे एक बड़ी वैल्यू से शुरुआत करके समय के साथ epsilon को कम किया जाता है।

इसे 'bandit' क्यों कहा जाता है?

पुरानी स्लॉट मशीनों में एक लीवर (एक "arm") होता था और वे लोगों के पैसे ले लेती थीं, इसलिए लोग उन्हें "one-armed bandits" कहते थे। कई लीवर वाला गेम "multi-armed bandit" बन गया। कृपया इसे असली जुए की मशीनों पर आज़माने की कोशिश न करें।

पाठ का टेस्ट

5 सवाल। पास होने और इस पाठ को पूरा करने के लिए 3 सही होने चाहिए (60%)।

टेस्ट देने और अपनी प्रोग्रेस सेव करने के लिए साइन इन करें