This is also a `bash` (or rather any `readline` app) builtin.

    $ cat .inputrc
    set editing-mode vi
    set keymap vi-command
    k: history-search-backward
    j: history-search-forward

Type any prefix, press `<esc>k` (or `<up>` in emacs mode) and it'll prefix match on history. Keep pressing `k` for older matches.