
Show HN: Gittins, an online bandit engine that enforces log correctness
browserimport * as gittins from "https://esm.sh/gittins/web";
以下正文同步自 Hacker News 最新,版权归原站所有,已转换为易读排版。
Max Pagels
Gittins
Production-grade contextual bandits.
npmnpm install gittins
browserimport * as gittins from "https://esm.sh/gittins/web";
PyPInpmGitHub
Gittins is an opinionated, highly optimised contextual bandit engine that aims to address the practical considerations with such systems, based on my experience working with bandit problems. It stands on the shoulders of giants, in particular Vowpal Wabbit, and adheres strictly to a design in support of real-world production use. Gittins is not a research tool.
Gittins learns one observation at a time, in O(1) work, and in fixed memory as long as open decisions are regularly resolved.
For many real-world problems, the relationship between context and feedback drifts over time. A contextual bandit engine must learn to adapt over time, and never learn something it cannot eventually unlearn.
If you want to choose what banner to display on your website, and the set changes each day, an engine must accept this, and clean up after itself. There should never be a case where you must specify the number of actions beforehand.
The built-in algorithms should be readable by any competent programmer, and work in practice. Sophistication lives in the layering and the API, not in any single component. Users can swap in their own prediction model and/or exploration algorithm, and inherit everything else.
Rewards in bandits may arrive late, or not at all. Constructing invalid training data from logs or external sources must be nigh on impossible by design, not merely discouraged.
Fast decision cycles allow for unexpected use cases. Gittins must have best-in-class single core performance, and rely on few to zero dependencies. Bit-identical results across platforms and language bindings must be guaranteed and enforced by a golden test corpus. Code changes must be validated by tens of thousands of simulations and a large test battery.
Many problems are ranking / multi-position problems; therefore problems with thousands of candidate actions must be practical, fast, and robust.
It must be possible to estimate how a new policy would have performed using only logged decisions from an old policy.
The same model needs to be able to run (a) ephemerally in memory, (b) persisted to a flat file, or (c) used via a shared service. There should be no need for databases; indeed, the model weights should be possible to check in to version control and deploy as part of normal deployment workflows.
These concepts are discussed throughout this document, which serves both as an introduction to bandits and as technical documentation for Gittins. I encourage the reader to read the whole document once; once you have understood the concepts on a broad level, use the contents above to jump to sections you need to reference.
In the contextual bandit setting, you (repeatedly):
The objective is to learn to select the best action for any given context such that you maximise total reward over time. From this problem setting, it follows that contextual bandit algorithms must try out different actions to learn what context/action pairs lead to the best rewards; they must explore the action space using some exploration algorithm, and also exploit their knowledge using some learned model.
Some bandit algorithms explore first, then exploit. Some learn to explore less over time, converging at some point on the optimal action for a given context. Gittins uses a simple algorithm known as epsilon-greedy, where exploration always happens for a small portion of decisions, regardless of how long the bandit has been running. This is a deliberate choice to tackle non-stationarity, an issue I revisit later in this document. It is also a practical choice: epsilon-greedy is surprisingly hard to beat in practice.
The simulation below runs the real engine in your browser on a small problem: two contexts, three actions, and a different best action for each context. Watch the bandit start at random and settle on the right banner per device, while still exploring a small share of the time.
You may be thinking to yourself, "why not use supervised learning instead of bandits?". That is a fair question, and for some problems, it works well. But consider a case of topic recommendation on social media. If you use supervised learning to choose the best topic from a handful of candidates, you must a) have enough cover in your training data to learn the optimal relationships, however obscure, and b) have some way of being able to recommend entirely new topics that you don't have history for. Bandits offer a natural way of introducing new actions by virtue of its explorative design.
Gittins comes in three flavours: a (slow) reference Python implementation, which is not packaged and not recommended outside development of the system; Python bindings, for most data science workflows; and WASM bindings, for in-browser decisions. The bindings call a core written in Rust for performance reasons.
Whichever flavour you pick, the interface is the same eight functions with the same names and the same semantics. A state saved by one loads in the others, bit for bit. The examples on this page default to Python; use the toggle above any code block to switch to the WASM (JavaScript) API, and the whole page follows.
All you need resides in one module, gittins. There is no schema to define, nothing to register, and no background machinery. Start by creating a bandit. What you get back is a handle: decide, learn, and expire update it in place and return just their results. The module holds no state of its own — the handle is the bandit, so you can hold several, snapshot one, or ship one across languages. Passing a handle costs nothing (it is a reference to the one bandit in memory); only serialize ever copies the bandit state.
import gittins import time
state = gittins.create(bits=8, horizon=3600.0)
bits sets how much room the model has for features: it learns in a space of 2^bits slots (here 256), and every feature and action is hashed into it. Nothing needs registering: an action or feature the model has never seen before will be processed without error, and both may vary from decision to decision. horizon answers the question how long do we wait for a reward? — a decision that gets no reward within horizon seconds is treated as having earned default_reward (0.0 unless you say otherwise). There are two more optional settings, epsilon (how much to explore) and forgetfulness (how fast old evidence fades); the defaults are sensible, but tunable with off-policy evaluation.
To make your first decision, describe what you know right now (the context), list what you could do (the candidates: an action id and that action's features), and supply the time. The engine never reads a clock itself — you pass your own t — so any run can be replayed exactly.
context = {"device": "mobile", "hour": 14} candidates = [ ("banner-sale", {"discount": 0.2}), ("banner-new", {"discount": 0.0}), ("banner-plain", {}), ]
ask the bandit which banner to show, right now
record = gittins.decide( state, context, candidates, t=time.time(), salt="bandit-1", )
chosen_action_id = candidates[record.chosen][0] # act on this
Feature values are strings for categories, numbers for quantities (booleans count as 1/0), and null for “not available this time”. The salt is the bandit's name; if you run several bandits, give each its own so their decision ids never collide. Note the return value: a record of the decision, not just a pick: its id, which candidate was chosen including features, and the probability the candidate was chosen with. Gittins will keep this information in a ledger in memory pending for open decisions, but the record is returned to you in case you wish to inspect it or construct an experience log for offline training.
Gittins learns only when you resolve a decision, and each decision can be resolved exactly once. When the reward arrives simply report it by id, along with the current time: the engine checks your t against the decision's own, so a reward that shows up at or past the horizon is not quietly accepted — it resolves as expired and trains as default_reward.
In addition to submitting rewards, remember to call expire regularly with the current time so that decisions which waited past the horizon are trained as default_reward. If you fail to call expire regularly, the memory usage will continue to grow. It is a deliberate choice to pass the expiration responsibility to you, as your application may have reasons not to expire unresolved records at regular intervals. However, for most applications, you will usually want to call expire inside a timer or directly after every decide call to ensure the records in memory never grow too large.
import threading
the user clicked the banner we showed — report the
outcome as a reward for that decision, by its id
resolution = gittins.learn( state, record.decision_id, reward=1.0, t=time.time() )
def sweep():
resolve every decision that has waited past the
horizon with no reward; each one is trained with
default_reward (here: 0.0)
resolutions = gittins.expire(state, t=time.time())
sweep again in a minute
threading.Timer(60.0, sweep).start()
sweep()
That is the whole loop: create once, then decide, act, and resolve, forever. The bandit is learning from the very first decision. To keep what it has learned across restarts (or browser reloads), snapshot the state — the whole thing is one plain string, identical on every platform, small enough for a file, a database column, localStorage, or version control:
from pathlib import Path
Path("bandit.state").write_text(gittins.serialize(state))
... later, or on another machine:
state = gittins.deserialize(Path("bandit.state").read_text())
deserialize validates everything and refuses to load anything corrupt, and the format is shared across implementations: a state saved in the browser will load in Python, and vice versa.
The loop above learns online, and the snapshot saved carries everything the model knows. But a running bandit produces something else of value along the way: a trace of every decision it made, what it chose from, and what happened next. Written down properly, this trace is an experience log. This (optional) log is a dataset that lets you answer questions offline, after the fact. Was epsilon too high? Would forgetting more slowly have earned more reward? How would a different configuration have done on this exact traffic? Answering these questions is the subject of What would have happened?; this chapter is about building a log that such evaluation needs.
A common failure mode of bandits in production settings is that their logs are assembled rather than recorded; typically, a “what we chose” table joined to a “what reward we got” table, with the candidate set reconstructed from a catalogue that has since changed, and the probability of each choice re-derived from a model that has since been retrained. Every join is a place to be subtly wrong, and a subtly wrong log poisons every conclusion drawn from it. Gittins takes the position that an experience log should never be assembled, only appended to: every call in the decision loop already returns exactly what belongs in the log, and log_line turns it into one canonical line. Log the record decide returns, log the resolution learn returns, log what expire returns, and you are done:
log = open("decisions.jsonl", "a")
record = gittins.decide( state, context, candidates, t=time.time(), salt="bandit-1", ) log.write(gittins.log_line(record) + "\n")
...when the reward arrives:
resolution = gittins.learn(state, record.decision_id, reward=1.0, t=time.time()) log.write(gittins.log_line(resolution) + "\n")
...and on every sweep:
for r in gittins.expire(state, t=time.time()): log.write(gittins.log_line(r) + "\n")
Each line is one compact JSON object, in canonical field order, so the log is plain text:
正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。