reply_buffer.js

/**
 * Returns a random integer between min (inclusive) and max (inclusive).
 * The value is no lower than min (or the next integer greater than min
 * if min isn't an integer) and no greater than max (or the next integer
 * lower than max if max isn't an integer).
 * Using Math.round() will give you a non-uniform distribution!
 * https://stackoverflow.com/questions/1527803/generating-random-whole-numbers-in-javascript-in-a-specific-range
 */
 const getRandomInt = (min, max)  => {
    min = Math.ceil(min)
    max = Math.floor(max)
    return Math.floor(Math.random() * (max - min + 1)) + min
}

/**
 * Reply Buffer.
 */
class ReplyBuffer {
    /**
     * Constructor.
     * 
     * @param {*} limit maximum number of transitions
     * @param {*} onDiscard callback triggered on discard a transition
     */
    constructor(limit = 500, onDiscard = () => {}) {
        this._limit = limit
        this._onDiscard = onDiscard

        this._buffer = new Array(limit).fill()
        this._pool = []

        this.size = 0
    }

    /**
     * Add a new transition to the reply buffer. 
     * Transition doesn't contain the next state. The next state is derived when sampling.
     * 
     * @param {{id: number, priority: number, state: array, action, reward: number}} transition transition
     */
    add(transition) {
        let { id, priority = 1 } = transition
        if (id === undefined || id < 0 || priority < 1) 
            throw new Error('Invalid arguments')

        id = id % this._limit

        if (this._buffer[id]) {
            const start = this._pool.indexOf(id)
            let deleteCount = 0
            while (this._pool[start + deleteCount] == id)
                deleteCount++

            this._pool.splice(start, deleteCount)
            
            this._onDiscard(this._buffer[id])
        } else
            this.size++

        while (priority--) 
            this._pool.push(id)

        this._buffer[id] = transition
    }

    /**
     * Return `n` random samples from the buffer. 
     * Returns an empty array if impossible provide required number of samples.
     * 
     * @param {number} [n = 1] - number of samples 
     * @returns array of exactly `n` samples
     */
    sample(n = 1) {
        if (this.size < n) 
            return []

        const 
            sampleIndices = new Set(),
            samples = []

        let counter = n
        while (counter--)
            while (sampleIndices.size < this.size) {
                const randomIndex = this._pool[getRandomInt(0, this._pool.length - 1)]
                if (sampleIndices.has(randomIndex))
                    continue

                sampleIndices.add(randomIndex)

                const { id, state, action, reward } = this._buffer[randomIndex]
                const nextId = id + 1
                const next = this._buffer[nextId % this._limit]

                if (next && next.id === nextId) { // the case when sampled the last element that still waiting for next state
                    samples.push({ state, action, reward, nextState: next.state})
                    break
                }
            }

        return samples.length == n ? samples : []
    }
}

/** TESTS */
(() => {
    return

    const rb = new ReplyBuffer(5)
    rb.add({id: 0, state: 0})
    rb.add({id: 1, state: 1})
    rb.add({id: 2, state: 2, priority: 3})
    
    console.assert(rb.size === 3)
    console.assert(rb._pool.length === 5)
    console.assert(rb._buffer[0].id === 0)
    
    rb.add({id: 2, state: 2})
    rb.add({id: 4, state: 4, priority: 2})
    
    console.assert(rb.size === 4)
    console.assert(rb._pool.length === 5)
    console.assert(JSON.stringify(rb._pool) === '[0,1,2,4,4]')
    
    rb.add({id: 5, state: 0, priority: 2}) // 5%5 = 0 => state = 0
    
    console.assert(rb.size === 4)
    console.assert(rb._pool.length === 6)
    console.assert(rb._buffer.length === 5)
    console.assert(rb._buffer[0].id === 5)
    console.assert(JSON.stringify(rb._pool) === '[1,2,4,4,0,0]')

    console.assert(rb.sample(999).length === 0, 'Too many samples')
    
    let samples1 = rb.sample(2)
    console.assert(samples1.length === 2, 'Only two samples possible')
    console.assert(samples1[0].nextState === (samples1[0].state + 1) % 5, 'Next state should be valid', samples1)

    rb.add({id: 506, state: 506, priority: 3})

    let samples2 = rb.sample(1)
    console.assert(samples2.length === 1, 'Only one suitable sample with valid next state')
    console.assert(samples2[0].state === 4, 'Sample with id:4')
    console.assert(rb._buffer[1].id === 506, '506 % 5 = 1')

    console.assert(rb.sample(2).length === 0, 
        'Can not sample 2 transitions since next state is available only for one state')
})()