समस्या
वैल्यू इटरेशन मार्कोव निर्णय प्रक्रिया को हल करता है: यह V(s) खोजता है, यानी अवस्था s से शुरू करके इकट्ठा किया जा सकने वाला सबसे अच्छा कुल डिस्काउंटेड इनाम।
यहाँ ट्रांज़िशन नियतात्मक हैं। अवस्था s में क्रिया a इनाम rewards[s][a] देती है और अवस्था next_states[s][a] पर ले जाती है, जहाँ -1 का अर्थ है एपिसोड ख़त्म। हर अवस्था के लिए V(s) = 0 से शुरू करें, फिर iterations बार दोहराएँ, हर नया मान पिछले स्वीप से निकालें:
V_new(s) = a पर ( rewards[s][a] + gamma × V(next_states[s][a]) ) का अधिकतम
जहाँ अगली अवस्था -1 होने पर gamma × V पद 0 होता है।
value_iteration(next_states, rewards, gamma, iterations) लागू करें।
इनपुट
next_states: हर अवस्था के लिए उसकी हर क्रिया की अगली अवस्था (-1 एपिसोड ख़त्म करता है)। अवस्थाओं में क्रियाओं की संख्या अलग हो सकती है।
rewards: हर क्रिया का इनाम, next_states जैसे ही आकार में।
gamma: डिस्काउंट फ़ैक्टर।
iterations: स्वीप की संख्या।
आउटपुट
आख़िरी स्वीप के बाद V लौटाएँ, हर अवस्था के लिए एक मान।
सीमाएँ
1 ≤ अवस्थाएँ ≤ 200, 1 ≤ प्रति अवस्था क्रियाएँ ≤ 10, 0 ≤ iterations ≤ 1,000
-100 ≤ हर इनाम ≤ 100, 0 ≤ gamma ≤ 1
उदाहरण
इनपुट:
gamma = 0.9
rewards = [
[0.0, 0.0],
[0.0, 0.0],
[10.0]
]
iterations = 3
next_states = [
[0, 1],
[0, 2],
[-1]
]
अपेक्षित आउटपुट:
expected = [8.1, 9.0, 10.0]इनपुट:
double gamma = 0.9;
std::vector<std::vector<double>> rewards = {
{0.0, 0.0},
{0.0, 0.0},
{10.0}
};
long long iterations = 3;
std::vector<std::vector<long long>> next_states = {
{0, 1},
{0, 2},
{-1}
};
अपेक्षित आउटपुट:
std::vector<double> expected = {8.1, 9.0, 10.0};इनपुट:
double gamma = 0.9;
double[][] rewards = new double[][] {
new double[] {0.0, 0.0},
new double[] {0.0, 0.0},
new double[] {10.0}
};
long iterations = 3;
long[][] next_states = new long[][] {
new long[] {0, 1},
new long[] {0, 2},
new long[] {-1}
};
अपेक्षित आउटपुट:
double[] expected = new double[] {8.1, 9.0, 10.0};व्याख्या
स्वीप 1: केवल अवस्था 2 इनाम पा सकती है, V = [0, 0, 10]। स्वीप 2: अवस्था 1 दाएँ जाकर उस तक पहुँचती है, 0.9 × 10 = 9, V = [0, 9, 10]। स्वीप 3: अवस्था 0 को 0.9 × 9 = 8.1 मिलता है। परिणाम: [8.1, 9, 10]।
इनपुट:
gamma = 0.0
rewards = [
[1.0, 2.0],
[3.0, 0.0]
]
iterations = 5
next_states = [
[1, 0],
[0, 1]
]
अपेक्षित आउटपुट:
expected = [2.0, 3.0]इनपुट:
double gamma = 0.0;
std::vector<std::vector<double>> rewards = {
{1.0, 2.0},
{3.0, 0.0}
};
long long iterations = 5;
std::vector<std::vector<long long>> next_states = {
{1, 0},
{0, 1}
};
अपेक्षित आउटपुट:
std::vector<double> expected = {2.0, 3.0};इनपुट:
double gamma = 0.0;
double[][] rewards = new double[][] {
new double[] {1.0, 2.0},
new double[] {3.0, 0.0}
};
long iterations = 5;
long[][] next_states = new long[][] {
new long[] {1, 0},
new long[] {0, 1}
};
अपेक्षित आउटपुट:
double[] expected = new double[] {2.0, 3.0};व्याख्या
gamma = 0 पर भविष्य नहीं गिना जाता, इसलिए हर अवस्था का मूल्य बस उसका सबसे अच्छा तात्कालिक इनाम है: [2, 3]।
कैसे हल करें
पहले खुद कोशिश करें, फिर एक-एक करके संकेत खोलें।
संकेत 1
हर sweep सिर्फ पिछले sweep की values use करता है, same pass में पहले हुए updates नहीं.
संकेत 2
हर state के लिए, immediate reward को next state की discounted value के साथ जोड़कर सभी actions compare करो.
संकेत 3
Terminal actions को ध्यान से handle करो: जब next state missing हो, तब वे सिर्फ अपना immediate reward देती हैं.
अपेक्षित जटिलता
समय O(iterations * total_actions), अतिरिक्त स्थान O(states)
संदर्भ
यह चुनौती CodeUtility के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।