Unfortunately history-search-(forward|backward) is not mapped to a combination in most common configurations.

I prefer to map it to esc-p which coincides with the setting in tcsh. Like that:

"\M-p": history-search-backward

So you basically type something and then press esc p to have the shell complete it.