समस्या
Q-लर्निंग केवल अनुभव से सीखती है कि हर अवस्था में हर क्रिया कितनी अच्छी है, यानी Q(s, a)। अवस्था s में क्रिया a करने, reward पाने और अवस्था s' में पहुँचने के बाद:
- target = reward, अगर एपिसोड ख़त्म हो गया (
done= 1) - target = reward + gamma × a' पर Q(s', a') का अधिकतम, अन्यथा
- Q(s, a) ← Q(s, a) + alpha × (target - Q(s, a))
सभी Q मान 0 से शुरू करें और ट्रांज़िशन क्रम से लागू करें।
q_learning(num_states, num_actions, transitions, alpha, gamma) लागू करें।
इनपुट
num_states, num_actions: तालिका का आकार।
transitions: हर कदम के लिए एक पंक्ति [state, action, reward, next_state, done]।
alpha: लर्निंग रेट।
gamma: डिस्काउंट फ़ैक्टर।
आउटपुट
Q तालिका को मैट्रिक्स के रूप में लौटाएँ, जिसमें हर अवस्था के लिए एक पंक्ति और हर क्रिया के लिए एक कॉलम हो।
सीमाएँ
1 ≤ num_states, num_actions ≤ 100, 0 ≤ ट्रांज़िशन की संख्या ≤ 10,000
-100 ≤ reward ≤ 100, done 0 या 1 है
0 < alpha ≤ 1, 0 ≤ gamma ≤ 1
उदाहरण
इनपुट:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[0, 1, 0, 1, 0],
[1, 0, 10, 0, 1]
]
अपेक्षित आउटपुट:
expected = [
[0.0, 0.0],
[5.0, 0.0]
]इनपुट:
double alpha = 0.5;
double gamma = 0.9;
long long num_states = 2;
long long num_actions = 2;
std::vector<std::vector<long long>> transitions = {
{0, 1, 0, 1, 0},
{1, 0, 10, 0, 1}
};
अपेक्षित आउटपुट:
std::vector<std::vector<double>> expected = {
{0.0, 0.0},
{5.0, 0.0}
};इनपुट:
double alpha = 0.5;
double gamma = 0.9;
long num_states = 2;
long num_actions = 2;
long[][] transitions = new long[][] {
new long[] {0, 1, 0, 1, 0},
new long[] {1, 0, 10, 0, 1}
};
अपेक्षित आउटपुट:
double[][] expected = new double[][] {
new double[] {0.0, 0.0},
new double[] {5.0, 0.0}
};व्याख्या
पहले कदम में अभी कोई इनाम नहीं मिलता: target = 0 + 0.9 × max(Q[1]) = 0, इसलिए Q[0][1] 0 ही रहता है। दूसरा कदम इनाम 10 के साथ एपिसोड ख़त्म करता है: Q[1][0] = 0 + 0.5 × (10 - 0) = 5।
इनपुट:
alpha = 0.5
gamma = 0.9
num_states = 2
num_actions = 2
transitions = [
[1, 0, 10, 0, 1],
[0, 1, 0, 1, 0]
]
अपेक्षित आउटपुट:
expected = [
[0.0, 2.25],
[5.0, 0.0]
]इनपुट:
double alpha = 0.5;
double gamma = 0.9;
long long num_states = 2;
long long num_actions = 2;
std::vector<std::vector<long long>> transitions = {
{1, 0, 10, 0, 1},
{0, 1, 0, 1, 0}
};
अपेक्षित आउटपुट:
std::vector<std::vector<double>> expected = {
{0.0, 2.25},
{5.0, 0.0}
};इनपुट:
double alpha = 0.5;
double gamma = 0.9;
long num_states = 2;
long num_actions = 2;
long[][] transitions = new long[][] {
new long[] {1, 0, 10, 0, 1},
new long[] {0, 1, 0, 1, 0}
};
अपेक्षित आउटपुट:
double[][] expected = new double[][] {
new double[] {0.0, 2.25},
new double[] {5.0, 0.0}
};व्याख्या
वही कदम उलटे क्रम में। Q[1][0] पहले 5 बनता है, इसलिए अवस्था 0 से कदम उसे देखता है: target = 0 + 0.9 × 5 = 4.5 और Q[0][1] = 0.5 × 4.5 = 2.25। इनाम एक अवस्था पीछे पहुँच गया।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
हर transition सिर्फ current value और next state के best estimate से एक table entry update करता है.
संकेत 2
Q table को zero से initialize रखो, फिर transitions को order में process करके हर one के बाद तुरंत update करो.
संकेत 3
अगर episode end हो जाए, तो future value add नहीं होती, और next-state maximum use नहीं करना चाहिए.
अपेक्षित जटिलता
समय O(T * A), अतिरिक्त स्थान O(S * A)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।