Heuristics Selection - Context Matching or Probabilistic Selection? Careful or Faster?

We target the problem of selecting proper heuristics for repair of a particular cost. The following things are important here: 1) What features of the current situation are important in selection of heuristic (and need to be stored)?, 2) How to measure the goodness of various heuristics in this situation?, 3) Given the features and goodness of various heuristics, how to select a good heuristic for application?

Availability of limited memory implies only limited number of features of a situation can be stored. Availability of limited computational resources implies only a little computation can be used to match the current situation with the features stored and to evaluate the goodness of various heuristics for updation of heuristic preferences. Also only limited time can be used for selecting good heuristic for application.

Features
A heuristic internally has several choice points. For example, a heuristic to add an action has internally the choices: which action to insert, which parameters to use to instantiate the action, which start time of action to use. Each choice point needs to store:
1) The context of the choice (for example, the current state and the desired state)
2) Evaluated goodness in the context. It may be noted that there may be defined a distance function between contexts.

Goodness
The goodness of a heuristic may be measured using a machine learning technique like Q-Learning.

Selection
The two extremes of implementation of heuristics selection are:
1) We store nothing, only a few simple choices for selection of appropriate class of heuristics. This is close to the current implementation. We choose an appropriate heuristic more or less randomly (actually it is not completely randomly but guided by the past experiences of heuristic selection (link to Alex's paper on this)). In this case, we expect fast reaction (due to simple heuristic selection), but will perform well only in domains where mistakes are tolerable and/or correctable. This is a less careful approach, but faster.
2) We store many features of each situation. Then the investigation of which heuristic to apply in a particular case takes more time. This is a more careful approach, but slower.
It may be argued that the faster approach may not be preferable for huge (exponential) search spaces with non-trivial structure. Randomly and quickly assigning some values for search may not work well when there is a huge space to search.

Indeed one way to approach the problem is to try something trivial. If it works then good, else try more time-taking more careful techniques. The preference values of what do not work may be temporarily reduced.