DynaQ.hpp

Go to the documentation of this file.

#ifndef AI_TOOLBOX_MDP_DYNAQ_HEADER_FILE
#define AI_TOOLBOX_MDP_DYNAQ_HEADER_FILE
 
#include <AIToolbox/MDP/Types.hpp>
#include <AIToolbox/MDP/TypeTraits.hpp>
#include <AIToolbox/MDP/Algorithms/QLearning.hpp>
#include <AIToolbox/Seeder.hpp>
 
#include <boost/functional/hash.hpp>
#include <utility>
#include <unordered_set>
#include <vector>
 
namespace AIToolbox::MDP {
    template <IsGenerativeModel M>
    class DynaQ {
        public:
            explicit DynaQ(const M & m, double alpha = 0.5, unsigned n = 50);
 
            void stepUpdateQ(size_t s, size_t a, size_t s1, double rew);
 
            void batchUpdateQ();
 
            void setLearningRate(double a);
 
            double getLearningRate() const;
 
            void setN(unsigned n);
 
            unsigned getN() const;
 
            const QFunction & getQFunction() const;
 
            const M & getModel() const;
 
        private:
            unsigned N;
            const M & model_;
            QLearning qLearning_;
 
            // We use two structures because generally S*A is not THAT big, and we can definitely use
            // the O(1) insertion and O(1) sampling time.
            std::unordered_set<std::pair<size_t,size_t>, boost::hash<std::pair<size_t, size_t>>> visitedStatesActionsInserter_;
            std::vector<std::pair<size_t,size_t>> visitedStatesActionsSampler_;
 
            // Stuff for batch update
            mutable RandomEngine rand_;
    };
 
    template <IsGenerativeModel M>
    DynaQ<M>::DynaQ(const M & m, const double alpha, const unsigned n) :
            N(n), model_(m), qLearning_(model_, alpha), rand_(Seeder::getSeed())
    {
        visitedStatesActionsInserter_.reserve(model_.getS()*model_.getA());
        visitedStatesActionsSampler_.reserve(model_.getS()*model_.getA());
    }
 
    template <IsGenerativeModel M>
    void DynaQ<M>::stepUpdateQ(const size_t s, const size_t a, const size_t s1, const double rew) {
        qLearning_.stepUpdateQ(s, a, s1, rew);
        // O(1) insertion...
        const auto result = visitedStatesActionsInserter_.insert(std::make_pair(s,a));
        if ( std::get<1>(result) )
            visitedStatesActionsSampler_.push_back(*std::get<0>(result));
    }
 
    template <IsGenerativeModel M>
    void DynaQ<M>::batchUpdateQ() {
        if ( ! visitedStatesActionsSampler_.size() ) return;
        std::uniform_int_distribution<size_t> sampleDistribution_(0, visitedStatesActionsSampler_.size()-1);
 
        for ( unsigned i = 0; i < N; ++i ) {
            // O(1) sampling...
            const auto [s,a] = visitedStatesActionsSampler_[sampleDistribution_(rand_)];
            const auto [s1, rew] = model_.sample(s, a);
 
            qLearning_.stepUpdateQ(s, a, s1, rew);
        }
    }
 
    template <IsGenerativeModel M>
    unsigned DynaQ<M>::getN() const {
        return N;
    }
 
    template <IsGenerativeModel M>
    const QFunction & DynaQ<M>::getQFunction() const {
        return qLearning_.getQFunction();
    }
    template <IsGenerativeModel M>
    const M & DynaQ<M>::getModel() const {
        return model_;
    }
 
    template <IsGenerativeModel M>
    void DynaQ<M>::setLearningRate(const double a) {
        qLearning_.setLearningRate(a);
    }
 
    template <IsGenerativeModel M>
    double DynaQ<M>::getLearningRate() const {
        return qLearning_.getLearningRate();
    }
}
 
#endif