समस्या
मल्टी-आर्म्ड बैंडिट अज्ञात भुगतान वाली स्लॉट मशीनों (आर्म) की एक पंक्ति है। एप्सिलॉन-ग्रीडी खोज और उपयोग में संतुलन बनाता है: epsilon प्रायिकता से यह कोई यादृच्छिक आर्म खींचता है, नहीं तो सबसे ऊँचे अनुमानित मान वाला आर्म खींचता है।
रन को टेस्ट करने लायक बनाने के लिए यादृच्छिक संख्याएँ दी जाती हैं। हर आर्म के लिए अनुमान Q = 0 और गिनती N = 0 से शुरू करें। हर कदम t पर:
- अगर
random_values[t]< epsilon, तो खोजें: arm =random_arms[t]। नहीं तो उपयोग करें: arm = सबसे ऊँचे Q वाला आर्म (बराबरी पर सबसे छोटा इंडेक्स)। - reward =
rewards[t][arm]प्राप्त करें। - N[arm] ← N[arm] + 1 और Q[arm] ← Q[arm] + (reward - Q[arm]) / N[arm], यानी चलता हुआ औसत।
epsilon_greedy(rewards, epsilon, random_values, random_arms) लागू करें।
इनपुट
rewards: हर कदम के लिए एक पंक्ति, जिसमें वह इनाम है जो हर आर्म उस कदम पर देगा।
epsilon: खोज की प्रायिकता।
random_values: हर कदम के लिए [0, 1) में एक यादृच्छिक संख्या।
random_arms: खोज करने पर हर कदम पर खींचा जाने वाला आर्म।
आउटपुट
अंतिम Q अनुमान लौटाएँ, हर आर्म के लिए एक।
सीमाएँ
1 ≤ कदम ≤ 10,000, 1 ≤ आर्म ≤ 100
0 ≤ epsilon ≤ 1, -100 ≤ हर इनाम ≤ 100
उदाहरण
इनपुट:
epsilon = 0.1
rewards = [
[1.0, 3.0],
[1.0, 3.0],
[1.0, 3.0],
[1.0, 3.0]
]
random_arms = [0, 1, 0, 0]
random_values = [0.5, 0.05, 0.7, 0.9]
अपेक्षित आउटपुट:
expected = [1.0, 3.0]इनपुट:
double epsilon = 0.1;
std::vector<std::vector<double>> rewards = {
{1.0, 3.0},
{1.0, 3.0},
{1.0, 3.0},
{1.0, 3.0}
};
std::vector<long long> random_arms = {0, 1, 0, 0};
std::vector<double> random_values = {0.5, 0.05, 0.7, 0.9};
अपेक्षित आउटपुट:
std::vector<double> expected = {1.0, 3.0};इनपुट:
double epsilon = 0.1;
double[][] rewards = new double[][] {
new double[] {1.0, 3.0},
new double[] {1.0, 3.0},
new double[] {1.0, 3.0},
new double[] {1.0, 3.0}
};
long[] random_arms = new long[] {0, 1, 0, 0};
double[] random_values = new double[] {0.5, 0.05, 0.7, 0.9};
अपेक्षित आउटपुट:
double[] expected = new double[] {1.0, 3.0};व्याख्या
कदम 0 उपयोग करता है; दोनों Q 0 हैं, इसलिए आर्म 0 खींचा जाता है और Q = [1, 0]। कदम 1 खोज करता है (0.05 < 0.1) और आर्म 1 आज़माता है: Q = [1, 3]। कदम 2 और 3 बेहतर आर्म 1 का उपयोग करते हैं। परिणाम: [1, 3]।
इनपुट:
epsilon = 0.0
rewards = [
[2.0, 5.0],
[4.0, 5.0],
[0.0, 5.0]
]
random_arms = [1, 1, 1]
random_values = [0.5, 0.5, 0.5]
अपेक्षित आउटपुट:
expected = [2.0, 0.0]इनपुट:
double epsilon = 0.0;
std::vector<std::vector<double>> rewards = {
{2.0, 5.0},
{4.0, 5.0},
{0.0, 5.0}
};
std::vector<long long> random_arms = {1, 1, 1};
std::vector<double> random_values = {0.5, 0.5, 0.5};
अपेक्षित आउटपुट:
std::vector<double> expected = {2.0, 0.0};इनपुट:
double epsilon = 0.0;
double[][] rewards = new double[][] {
new double[] {2.0, 5.0},
new double[] {4.0, 5.0},
new double[] {0.0, 5.0}
};
long[] random_arms = new long[] {1, 1, 1};
double[] random_values = new double[] {0.5, 0.5, 0.5};
अपेक्षित आउटपुट:
double[] expected = new double[] {2.0, 0.0};व्याख्या
epsilon = 0 पर एजेंट कभी खोज नहीं करता। वह आर्म 0 खींचता रहता है, जिसका औसत 2 → 3 → 2 होता है, और कभी नहीं जान पाता कि आर्म 1 5 देता है। परिणाम: [2, 0]।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
हर step पर, या तो forced random arm चुनो या अभी का best estimated arm.
संकेत 2
हर arm की value running average से update करो, ताकि pulls बढ़ने पर पुराने rewards का असर कम हो.
संकेत 3
Tie होने पर smallest-index arm चुनो, और याद रखो कि हर step में सिर्फ chosen arm बदलता है.
अपेक्षित जटिलता
समय O(steps * arms), अतिरिक्त स्थान O(arms)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।