Reinforcement Learning Theory

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// A small finite MDP with 3 states and 2 actions.
5
// Transitions are stored as adjacency lists with probabilities.
6
// We compute V* and the greedy policy via value iteration.
7
8
struct Transition { int next; double prob; double reward; };
9
10
int main(){
11
    ios::sync_with_stdio(false);
12
    cin.tie(nullptr);
13
14
    const int S = 3;       // states: 0,1,2
15
    const int A = 2;       // actions: 0,1
16
    const double gamma = 0.9;
17
    const double theta = 1e-8; // convergence threshold
18
19
    // MDP model: P and R together in transitions[s][a]
20
    vector<vector<vector<Transition>>> transitions(S, vector<vector<Transition>>(A));
21
22
    // Define a simple MDP:
23
    // State 0: a=0 goes to 1 with reward +1 (deterministic)
24
    //          a=1 goes to 2 with reward 0 (deterministic)
25
    transitions[0][0] = { {1, 1.0, 1.0} };
26
    transitions[0][1] = { {2, 1.0, 0.0} };
27
28
    // State 1: a=0 stays with small reward 0.1, a=1 to state 2 with reward 2
29
    transitions[1][0] = { {1, 1.0, 0.1} };
30
    transitions[1][1] = { {2, 1.0, 2.0} };
31
32
    // State 2: terminal-like (self-loop, zero reward)
33
    transitions[2][0] = { {2, 1.0, 0.0} };
34
    transitions[2][1] = { {2, 1.0, 0.0} };
35
36
    vector<double> V(S, 0.0), Vnew(S, 0.0);
37
38
    // Value Iteration loop: apply Bellman optimality operator until convergence
39
    int iters = 0;
40
    while (true) {
41
        iters++;
42
        double delta = 0.0;
43
        for (int s = 0; s < S; ++s) {
44
            double best = -1e100;
45
            for (int a = 0; a < A; ++a) {
46
                double q = 0.0;
47
                for (const auto &t : transitions[s][a]) {
48
                    q += t.prob * (t.reward + gamma * V[t.next]);
49
                }
50
                best = max(best, q);
51
            }
52
            Vnew[s] = best;
53
            delta = max(delta, fabs(Vnew[s] - V[s]));
54
        }
55
        V.swap(Vnew);
56
        if (delta < theta * (1 - gamma) / (2 * gamma + 1e-12)) break; // conservative stopping
57
        if (iters > 100000) break; // safety
58
    }
59
60
    // Derive greedy policy π*(s) = argmax_a Q*(s,a)
61
    vector<int> policy(S, 0);
62
    for (int s = 0; s < S; ++s) {
63
        double best = -1e100; int besta = 0;
64
        for (int a = 0; a < A; ++a) {
65
            double q = 0.0;
66
            for (const auto &t : transitions[s][a]) {
67
                q += t.prob * (t.reward + gamma * V[t.next]);
68
            }
69
            if (q > best) { best = q; besta = a; }
70
        }
71
        policy[s] = besta;
72
    }
73
74
    cout.setf(std::ios::fixed); cout<<setprecision(6);
75
    cout << "Converged in iterations: " << iters << "\n";
76
    for (int s = 0; s < S; ++s) cout << "V*["<<s<<"] = " << V[s] << "\n";
77
    for (int s = 0; s < S; ++s) cout << "pi*["<<s<<"] = action " << policy[s] << "\n";
78
    return 0;
79
}
80

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// 5x5 GridWorld with start at (0,0) and goal at (4,4). Each step has reward -1, reaching goal gives +10 and episode ends.
5
// Actions: 0=up,1=right,2=down,3=left. Moves that hit walls stay in place.
6
// We learn Q(s,a) using epsilon-greedy exploration.
7
8
struct Env {
9
    int H=5, W=5; pair<int,int> start{0,0}; pair<int,int> goal{4,4};
10
    pair<int,int> s;
11
    void reset(){ s = start; }
12
    bool is_goal() const { return s==goal; }
13
    int state_id() const { return s.first*W + s.second; }
14
    tuple<int,double,bool> step(int a){
15
        static int dr[4] = {-1,0,1,0};
16
        static int dc[4] = {0,1,0,-1};
17
        int nr = s.first + dr[a];
18
        int nc = s.second + dc[a];
19
        if(nr<0||nr>=H||nc<0||nc>=W){ nr = s.first; nc = s.second; }
20
        s = {nr,nc};
21
        bool done = is_goal();
22
        double r = done ? 10.0 : -1.0;
23
        return { state_id(), r, done };
24
    }
25
};
26
27
int main(){
28
    ios::sync_with_stdio(false);
29
    cin.tie(nullptr);
30
31
    Env env; const int S = env.H*env.W; const int A = 4;
32
    vector<vector<double>> Q(S, vector<double>(A, 0.0));
33
34
    // Hyperparameters
35
    double alpha = 0.1;    // learning rate
36
    double gamma = 0.99;   // discount
37
    double eps = 0.2;      // epsilon-greedy
38
    int episodes = 4000;   // number of episodes
39
    int max_steps = 200;   // safety cap per episode
40
41
    std::mt19937 rng(123);
42
    std::uniform_real_distribution<double> unif(0.0,1.0);
43
    std::uniform_int_distribution<int> randA(0,A-1);
44
45
    auto greedy = [&](int s){
46
        int besta = 0; double bestq = Q[s][0];
47
        for(int a=1;a<A;++a){ if(Q[s][a] > bestq){ bestq = Q[s][a]; besta = a; } }
48
        return besta;
49
    };
50
51
    for(int ep=0; ep<episodes; ++ep){
52
        env.reset(); int s = env.state_id();
53
        for(int t=0; t<max_steps; ++t){
54
            int a = (unif(rng) < eps) ? randA(rng) : greedy(s);
55
            auto [s2, r, done] = env.step(a);
56
            // Q-learning update: move Q toward r + gamma * max_a' Q(s2, a')
57
            double maxq_next = *max_element(Q[s2].begin(), Q[s2].end());
58
            double td = r + gamma * (done ? 0.0 : maxq_next) - Q[s][a];
59
            Q[s][a] += alpha * td;
60
            s = s2;
61
            if(done) break;
62
        }
63
        // simple epsilon decay
64
        eps = max(0.01, eps * 0.999);
65
    }
66
67
    // Derive greedy policy arrows
68
    const char* arrows = "^>v<";
69
    vector<char> policy(S,'?');
70
    for(int r=0;r<env.H;++r){
71
        for(int c=0;c<env.W;++c){
72
            env.s = {r,c};
73
            int id = env.state_id();
74
            if(env.is_goal()) { policy[id] = 'G'; continue; }
75
            policy[id] = arrows[ (int)(max_element(Q[id].begin(), Q[id].end()) - Q[id].begin()) ];
76
        }
77
    }
78
79
    // Print learned policy grid
80
    for(int r=0;r<env.H;++r){
81
        for(int c=0;c<env.W;++c){
82
            cout << policy[r*env.W + c] << ' ';
83
        }
84
        cout << '\n';
85
    }
86
    return 0;
87
}
88

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Stateless RL: K-armed Bernoulli bandit. We optimize softmax policy via REINFORCE with a baseline.
5
6
int main(){
7
    ios::sync_with_stdio(false);
8
    cin.tie(nullptr);
9
10
    int K = 5; // number of arms
11
    vector<double> p_true = {0.1, 0.3, 0.5, 0.2, 0.8}; // success probabilities (unknown to learner)
12
13
    // Policy parameters: preferences theta for softmax over arms
14
    vector<double> theta(K, 0.0);
15
16
    double alpha = 0.05;    // learning rate
17
    double baseline = 0.0;  // moving average baseline to reduce variance
18
    double beta = 0.01;     // baseline update rate
19
20
    std::mt19937 rng(123);
21
    std::uniform_real_distribution<double> unif(0.0,1.0);
22
23
    auto softmax = [&](const vector<double>& z){
24
        vector<double> p(K);
25
        double m = *max_element(z.begin(), z.end());
26
        double Z = 0.0; for(int i=0;i<K;++i){ p[i] = exp(z[i]-m); Z += p[i]; }
27
        for(int i=0;i<K;++i) p[i] /= Z; return p;
28
    };
29
30
    int steps = 5000;
31
    for(int t=0; t<steps; ++t){
32
        vector<double> pi = softmax(theta);
33
        // sample action
34
        double u = unif(rng), cum = 0.0; int a = 0;
35
        for(int i=0;i<K;++i){ cum += pi[i]; if(u <= cum){ a = i; break; } }
36
        // sample reward from Bernoulli(p_true[a])
37
        double r = (unif(rng) < p_true[a]) ? 1.0 : 0.0;
38
        // Update baseline
39
        baseline = (1.0 - beta) * baseline + beta * r;
40
        // Gradient of log-softmax: grad_i = 1_{i=a} - pi[i]
41
        for(int i=0;i<K;++i){
42
            double grad_log = (i==a ? 1.0 : 0.0) - pi[i];
43
            theta[i] += alpha * (r - baseline) * grad_log; // REINFORCE with baseline
44
        }
45
    }
46
47
    vector<double> pi_final = [&](){ return softmax(theta); }();
48
49
    cout.setf(std::ios::fixed); cout<<setprecision(4);
50
    cout << "Final policy probabilities:" << '\n';
51
    for(int i=0;i<K;++i) cout << "arm "<<i<<": p= "<< pi_final[i] << " (true success="<<p_true[i]<<")\n";
52
    return 0;
53
}
54