Discount Factor & Return

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute per-time-step discounted returns for a single episode.
5
// rewards[i] corresponds to r_{i+1} in the math notation.
6
vector<double> discountedReturns(const vector<double>& rewards, double gamma) {
7
    int T = (int)rewards.size();
8
    vector<double> G(T, 0.0);
9
    double acc = 0.0; // This will hold G_{i+1} as we move backward
10
    for (int i = T - 1; i >= 0; --i) {
11
        // G_i = r_{i+1} + gamma * G_{i+1}
12
        acc = rewards[i] + gamma * acc;
13
        G[i] = acc;
14
    }
15
    return G;
16
}
17
18
int main() {
19
    // Example: episodic rewards over 5 steps
20
    // r_1=1, r_2=0, r_3=2, r_4=-1, r_5=3
21
    vector<double> rewards = {1.0, 0.0, 2.0, -1.0, 3.0};
22
23
    double gamma1 = 0.9; // patient
24
    double gamma2 = 0.5; // more myopic
25
26
    auto G1 = discountedReturns(rewards, gamma1);
27
    auto G2 = discountedReturns(rewards, gamma2);
28
29
    cout.setf(ios::fixed); cout << setprecision(6);
30
    cout << "Discounted returns with gamma=0.9\n";
31
    for (size_t i = 0; i < G1.size(); ++i) cout << "G[" << i << "] = " << G1[i] << "\n";
32
33
    cout << "\nDiscounted returns with gamma=0.5\n";
34
    for (size_t i = 0; i < G2.size(); ++i) cout << "G[" << i << "] = " << G2[i] << "\n";
35
36
    return 0;
37
}
38

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Episode {
5
    vector<int> states;    // includes nonterminals and terminal at end
6
    vector<double> rewards; // rewards[i] is r_{i+1}
7
};
8
9
mt19937 rng(123);
10
11
// Generate one episode for the 7-state random walk:
12
// States 0 and 6 are terminal. Nonterminals are 1..5.
13
// Start at state 3. Each step moves left/right with prob 0.5.
14
// Reward is +1 only when entering state 6; otherwise 0.
15
Episode generate_episode() {
16
    uniform_real_distribution<double> uni(0.0, 1.0);
17
    Episode ep;
18
    int s = 3; // start
19
    ep.states.push_back(s);
20
    while (s != 0 && s != 6) {
21
        double u = uni(rng);
22
        int a = (u < 0.5 ? -1 : +1); // left or right
23
        int s_next = s + a;
24
        double r = (s_next == 6 ? 1.0 : 0.0);
25
        ep.rewards.push_back(r);
26
        s = s_next;
27
        ep.states.push_back(s);
28
    }
29
    return ep;
30
}
31
32
// Compute per-time-step returns via backward pass
33
vector<double> discountedReturns(const vector<double>& rewards, double gamma) {
34
    int T = (int)rewards.size();
35
    vector<double> G(T, 0.0);
36
    double acc = 0.0;
37
    for (int i = T - 1; i >= 0; --i) {
38
        acc = rewards[i] + gamma * acc;
39
        G[i] = acc;
40
    }
41
    return G;
42
}
43
44
int main() {
45
    const double gamma = 1.0; // episodic, finite-horizon; safe to use γ=1 here
46
    const int S = 7;          // states 0..6
47
    const int episodes = 20000;
48
49
    vector<double> V(S, 0.0);
50
    vector<int> N(S, 0); // visit counts for first-visit MC
51
52
    for (int e = 0; e < episodes; ++e) {
53
        Episode ep = generate_episode();
54
        // Compute returns for each time index in the episode
55
        vector<double> G = discountedReturns(ep.rewards, gamma);
56
57
        // Track first visit times within this episode
58
        vector<int> first_visit_index(S, -1);
59
        for (int t = 0; t < (int)ep.states.size() - 1; ++t) { // exclude terminal state's index for updates
60
            int s = ep.states[t];
61
            if (first_visit_index[s] == -1) first_visit_index[s] = t;
62
        }
63
64
        // First-visit MC updates for nonterminal states 1..5
65
        for (int s = 1; s <= 5; ++s) {
66
            int t = first_visit_index[s];
67
            if (t != -1) {
68
                double Gt = G[t];
69
                N[s] += 1;
70
                // Incremental mean: V[s] <- V[s] + (G - V[s]) / N[s]
71
                V[s] += (Gt - V[s]) / (double)N[s];
72
            }
73
        }
74
    }
75
76
    cout.setf(ios::fixed); cout << setprecision(4);
77
    cout << "Estimated state values (states 1..5):\n";
78
    for (int s = 1; s <= 5; ++s) {
79
        cout << "V[" << s << "] = " << V[s] << "\n";
80
    }
81
    return 0;
82
}
83

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Compute G_t^{(n)} = sum_{k=0}^{n-1} gamma^k r_{t+k+1} + gamma^n * V(S_{t+n})
5
// Given: a window of future rewards starting at time t (rewards[t] = r_{t+1}),
6
// the discount factor gamma, the step size n, and a bootstrap value V(S_{t+n}).
7
double n_step_return(const vector<double>& rewards_from_t, double gamma, int n, double bootstrap_value) {
8
    double acc = 0.0;
9
    double pow_gamma = 1.0;
10
    int K = min(n, (int)rewards_from_t.size());
11
    for (int k = 0; k < K; ++k) {
12
        acc += pow_gamma * rewards_from_t[k];
13
        pow_gamma *= gamma; // prepare for the next step
14
    }
15
    // If we reached fewer than n rewards (due to episode termination),
16
    // the bootstrap typically should NOT be applied in episodic tasks.
17
    // Here we only add bootstrap if we actually have n steps available.
18
    if (n <= (int)rewards_from_t.size()) acc += pow_gamma * bootstrap_value;
19
    return acc;
20
}
21
22
int main() {
23
    // Example: suppose from time t onward we observe rewards: 2, 0, -1, 3, ...
24
    vector<double> future_rewards = {2.0, 0.0, -1.0, 3.0};
25
    double gamma = 0.9;
26
27
    // Assume a value baseline V(S_{t+3}) = 5.0 for n=3
28
    int n = 3;
29
    double V_bootstrap = 5.0;
30
31
    double G_n = n_step_return(future_rewards, gamma, n, V_bootstrap);
32
33
    cout.setf(ios::fixed); cout << setprecision(6);
34
    cout << "n-step return (n=3, gamma=0.9, V_bootstrap=5.0): " << G_n << "\n";
35
36
    // Compare with full (finite) return without bootstrapping (γ^n term omitted)
37
    // This equals the n->infty Monte Carlo target truncated to the episode length.
38
    double full = 0.0, pow_gamma = 1.0;
39
    for (double r : future_rewards) { full += pow_gamma * r; pow_gamma *= gamma; }
40
    cout << "Truncated full return (no bootstrap): " << full << "\n";
41
    return 0;
42
}
43