ucb
===

[![Build Status](https://travis-ci.org/kurttheviking/ucb-js.svg?branch=master)](https://travis-ci.org/kurttheviking/ucb-js)

**An upper confidence bounds algorithm for multi-armed bandit problems**

This implementation is based on [<em>Bandit Algorithms for Website Optimization</em>](http://shop.oreilly.com/product/0636920027393.do) and related empirical research in ["Algorithms for the multi-armed bandit problem"](http://www.cs.mcgill.ca/~vkules/bandits.pdf). In addition, this module conforms to the [BanditLab/2.0 specification](https://github.com/kurttheviking/banditlab-spec/releases).


## Get started

### Prerequisites

- Node.js 6.x+ ([LTS track](https://github.com/nodejs/LTS#lts-schedule1))
- npm

### Installing

Install with `npm` (or `yarn`):

```sh
npm install ucb --save
```

### Caveat emptor

This implementation often encounters extended floating point numbers. Arm selection is therefore subject to JavaScript's floating point precision limitations. For general information about floating point issues see the [floating point guide](http://floating-point-gui.de).


## Usage

1. Create an optimizer with `3` arms:

    ```js
    const Algorithm = require('ucb');

    const algorithm = new Algorithm({
      arms: 3
    });
    ```

2. Select an arm (exploits or explores, determined by the algorithm):

    ```js
    algorithm.select().then((arm) => {
      // do something based on the chosen arm
    });
    ```

3. Report the reward earned from a chosen arm:

    ```js
    algorithm.reward(arm, value);
    ```


## API

### `Algorithm(config)`

Creates a new optimization algorithm.

#### Arguments

- `config` (`Object`): algorithm instance parameters

The `config` object supports two optional parameters:

- `arms` (`Number`, Integer): The number of arms over which the optimization will operate; defaults to `2`

Alternatively, the `state` object resolved from [`Algorithm#serialize`](https://github.com/kurttheviking/ucb-js#algorithmserialize) can be passed as `config`.

#### Returns

An instance of the ucb optimization algorithm.

#### Example

```js
const Algorithm = require('ucb');
const algorithm = new Algorithm();

assert.equal(algorithm.arms, 2);
```

Or, with a passed `config`:

```js
const Algorithm = require('ucb');
const algorithm = new Algorithm({ arms: 4 });

assert.equal(algorithm.arms, 4);
```

### `Algorithm#select()`

Choose an arm to play, according to the optimization algorithm.

#### Arguments

_None_

#### Returns

A `Promise` that resolves to a `Number` corresponding to the associated arm index.

#### Example

```js
const Algorithm = require('ucb');
const algorithm = new Algorithm();

algorithm.select().then(arm => console.log(arm));
```

### `Algorithm#reward(arm, reward)`

Inform the algorithm about the payoff from a given arm.

#### Arguments

- `arm` (`Number`, Integer): the arm index (provided from `Algorithm#select()`)
- `reward` (`Number`): the observed reward value (which can be 0 to indicate no reward)

#### Returns

A `Promise` that resolves to an updated instance of the algorithm. (The original instance is mutated as well.)

#### Example

```js
const Algorithm = require('ucb');
const algorithm = new Algorithm();

algorithm.reward(0, 1).then(updatedAlgorithm => console.log(updatedAlgorithm));
```

### `Algorithm#serialize()`

Obtain a plain object representing the internal state of the algorithm.

#### Arguments

_None_

#### Returns

A `Promise` that resolves to a stringify-able `Object` with parameters needed to reconstruct algorithm state.

#### Example

```js
const Algorithm = require('ucb');
const algorithm = new Algorithm();

algorithm.serialize().then(state => console.log(state));
```


## Development

### Contribute

PRs are welcome! For bugs, please include a failing test which passes when your PR is applied. [Travis CI](https://travis-ci.org/kurttheviking/ucb-js) provides on-demand testing for commits and pull requests.

### Workflow

1. Feature development and bug fixing should occur on a non-master branch.
2. Changes should be submitted to master via a [Pull Request](https://github.com/kurttheviking/ucb-js/compare).
3. Pull Requests should be merged via a merge commit. Local "in-process" commits may be squashed prior to pushing to the remote feature branch.

To enable a git hook that runs `npm test` prior to pushing, `cd` into the local repo and run:

```sh
touch .git/hooks/pre-push
chmod +x .git/hooks/pre-push
echo "npm test" > .git/hooks/pre-push
```

### Tests

To run the unit test suite:

```sh
npm test
```

Or, to run the test suite and view test coverage:

```sh
npm run coverage
```