सभी चुनौतियाँ
मध्यम 0 हल किए गए 0% स्वीकृति

वैल्यू इटरेशन

बेलमैन ऑप्टिमैलिटी अपडेट को बार-बार लागू करके मार्कोव निर्णय प्रक्रिया की हर अवस्था का मूल्य निकालें।

आप क्या सीखेंगे

  • बेलमैन ऑप्टिमैलिटी अपडेट लागू करना
  • हर स्वीप में अवस्थाओं के मान निकालना
  • निर्णयों को अवस्था, क्रिया और इनाम के रूप में दिखाना

समस्या

वैल्यू इटरेशन मार्कोव निर्णय प्रक्रिया को हल करता है: यह 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

उदाहरण

उदाहरण 1
इनपुट:
next_states = [
    [0, 1],
    [0, 2],
    [-1]
]
rewards = [
    [0.0, 0.0],
    [0.0, 0.0],
    [10.0]
]
gamma = 0.9
iterations = 3

अपेक्षित आउटपुट:
expected = [8.1, 9.0, 10.0]
इनपुट:
std::vector<std::vector<long long>> next_states = {
    {0, 1},
    {0, 2},
    {-1}
};
std::vector<std::vector<double>> rewards = {
    {0.0, 0.0},
    {0.0, 0.0},
    {10.0}
};
double gamma = 0.9;
long long iterations = 3;

अपेक्षित आउटपुट:
std::vector<double> expected = {8.1, 9.0, 10.0};
इनपुट:
long[][] next_states = new long[][] {
    new long[] {0, 1},
    new long[] {0, 2},
    new long[] {-1}
};
double[][] rewards = new double[][] {
    new double[] {0.0, 0.0},
    new double[] {0.0, 0.0},
    new double[] {10.0}
};
double gamma = 0.9;
long iterations = 3;

अपेक्षित आउटपुट:
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]।

उदाहरण 2
इनपुट:
next_states = [
    [1, 0],
    [0, 1]
]
rewards = [
    [1.0, 2.0],
    [3.0, 0.0]
]
gamma = 0.0
iterations = 5

अपेक्षित आउटपुट:
expected = [2.0, 3.0]
इनपुट:
std::vector<std::vector<long long>> next_states = {
    {1, 0},
    {0, 1}
};
std::vector<std::vector<double>> rewards = {
    {1.0, 2.0},
    {3.0, 0.0}
};
double gamma = 0.0;
long long iterations = 5;

अपेक्षित आउटपुट:
std::vector<double> expected = {2.0, 3.0};
इनपुट:
long[][] next_states = new long[][] {
    new long[] {1, 0},
    new long[] {0, 1}
};
double[][] rewards = new double[][] {
    new double[] {1.0, 2.0},
    new double[] {3.0, 0.0}
};
double gamma = 0.0;
long iterations = 5;

अपेक्षित आउटपुट:
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 के लिए अनुकूलित की गई है। ऊपर दिए गए स्टेटमेंट और सीमाओं का पालन करें।

हर कोडर का सबसे अच्छा पास हुआ समाधान। तेज़, कम मेमोरी वाले और बेहतर रेटिंग वाले समाधान ऊपर रहते हैं।

अभी कोई पास हुआ समाधान नहीं है। इसे हल करें और पहला स्थान पाएँ।

दूसरों से सीखें

समुदाय समाधान

अभी तक कोई प्रकाशित समाधान नहीं। पहला साझा करने के लिए इस चुनौती को हल करें।