Scribd
Upload
803 views4 pages

Q-Learning in C++

The Q-Learning algorithm was proposed to optimize solutions in Markov decision processes by choosing between immediate and delayed rewards. It works by having an agent take actions in a state, receive rewards that influence the Q-value for that state-action pair, and then transition to a new state. The Q-value is updated using the formula: Q(state, action) = Reward + gamma * Max future Q-value. The algorithm iterates through episodes of state transitions until it converges on optimal actions.

Uploaded by

Guru Mekala
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
803 views4 pages

Q-Learning in C++

The Q-Learning algorithm was proposed to optimize solutions in Markov decision processes by choosing between immediate and delayed rewards. It works by having an agent take actions in a state, receive rewards that influence the Q-value for that state-action pair, and then transition to a new state. The Q-value is updated using the formula: Q(state, action) = Reward + gamma * Max future Q-value. The algorithm iterates through episodes of state transitions until it converges on optimal actions.

Uploaded by

Guru Mekala
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 4

Introduction

The Q-Learning algorithm was proposed as a way to optimize solutions in Markov decision
process problems. The distinctive feature of Q-Learning is in its capacity to choose between
immediate rewards and delayed rewards. At each step of time, an agent observes the vector of
state xt, then chooses and applies an action ut. As the process moves to state xt+1, the agent
receives a reinforcement r(xt, ut). The goal of the training is to find the sequential order of
actions which maximizes the sum of the future reinforcements, thus leading to the shortest path
from start to finish.

The transition rule of Q learning is a very simple formula:

Q(state, action) = R(state, action) + gamma * Max[Q(next state, all actions)]

The gamma parameter has a range of 0 to 1 (0 <= gamma > 1), and ensures the convergence of
the sum. If gamma is closer to zero, the agent will tend to consider only immediate rewards. If
gamma is closer to one, the agent will consider future rewards with greater weight, willing to
delay the reward.

The Q-Learning algorithm goes as follows:

1. Set the gamma parameter, and environment rewards in matrix R.

2. Initialize matrix Q to zero.

3. For each episode:

Select a random initial state.

Do While the goal state hasn't been reached.

Select one among all possible actions for the current state.
Using this possible action, consider going to the next state.
Get maximum Q value for this next state based on all possible actions.
Compute: Q(state, action) = R(state, action) + gamma * Max[Q(next state, all actions)]
Set the next state as the current state.
End Do

End For

/ Author: John McCullock


// Date: 11-05-05
// Description: Q-Learning Example 1.
#include <iostream>
#include <iomanip>
#include <ctime>

using namespace std;

const int qSize = 6;


const double gamma = 0.8;
const int iterations = 10;
int initialStates[qSize] = {1, 3, 5, 2, 4, 0};

int R[qSize][qSize] = {{-1, -1, -1, -1, 0, -1},


{-1, -1, -1, 0, -1, 100},
{-1, -1, -1, 0, -1, -1},
{-1, 0, 0, -1, 0, -1},
{0, -1, -1, 0, -1, 100},
{-1, 0, -1, -1, 0, 100}};

int Q[qSize][qSize];
int currentState;

void episode(int initialState);


void chooseAnAction();
int getRandomAction(int upperBound, int lowerBound);
void initialize();
int maximum(int state, bool returnIndexOnly);
int reward(int action);

int main(){

int newState;

initialize();

//Perform learning trials starting at all initial states.


for(int j = 0; j <= (iterations - 1); j++){
for(int i = 0; i <= (qSize - 1); i++){
episode(initialStates[i]);
} // i
} // j

//Print out Q matrix.


for(int i = 0; i <= (qSize - 1); i++){
for(int j = 0; j <= (qSize - 1); j++){
cout << setw(5) << Q[i][j];
if(j < qSize - 1){
cout << ",";
}
} // j
cout << "\n";
} // i
cout << "\n";

//Perform tests, starting at all initial states.


for(int i = 0; i <= (qSize - 1); i++){
currentState = initialStates[i];
newState = 0;
do {
newState = maximum(currentState, true);
cout << currentState << ", ";
currentState = newState;
} while(currentState < 5);
cout << "5" << endl;
} // i

return 0;
}

void episode(int initialState){

currentState = initialState;

//Travel from state to state until goal state is reached.


do {
chooseAnAction();
} while(currentState == 5);

//When currentState = 5, run through the set once more to


//for convergence.
for(int i = 0; i <= (qSize - 1); i++){
chooseAnAction();
} // i
}

void chooseAnAction(){

int possibleAction;

//Randomly choose a possible action connected to the current state.


possibleAction = getRandomAction(qSize, 0);

if(R[currentState][possibleAction] >= 0){


Q[currentState][possibleAction] = reward(possibleAction);
currentState = possibleAction;
}
}

int getRandomAction(int upperBound, int lowerBound){

int action;
bool choiceIsValid = false;
int range = (upperBound - lowerBound) + 1;

//Randomly choose a possible action connected to the current state.


do {
//Get a random value between 0 and 6.
action = lowerBound + int(range * rand() / (RAND_MAX + 1.0));
if(R[currentState][action] > -1){
choiceIsValid = true;
}
} while(choiceIsValid == false);

return action;
}

void initialize(){

srand((unsigned)time(0));

for(int i = 0; i <= (qSize - 1); i++){


for(int j = 0; j <= (qSize - 1); j++){
Q[i][j] = 0;
} // j
} // i
}

int maximum(int state, bool returnIndexOnly){


// if returnIndexOnly = true, a Q matrix index is returned.
// if returnIndexOnly = false, a Q matrix element is returned.

int winner;
bool foundNewWinner;
bool done = false;

winner = 0;

do {
foundNewWinner = false;
for(int i = 0; i <= (qSize - 1); i++){
if((i < winner) || (i > winner)){ //Avoid self-
comparison.
if(Q[state][i] > Q[state][winner]){
winner = i;
foundNewWinner = true;
}
}
} // i

if(foundNewWinner == false){
done = true;
}

} while(done = false);

if(returnIndexOnly == true){
return winner;
}else{
return Q[state][winner];
}
}

int reward(int action){

return static_cast<int>(R[currentState][action] + (gamma *


maximum(action, false)));
}

You might also like