Methods, systems, and computer program products are provided for the online convex optimization problem, in which the decision maker has knowledge of the all past states and resulting cost functions for his previous choices and attempts to make a new choice that results in minimum regret. The method does not rely upon the structure of the cost function or the characterization of the states and takes advantage of the similarity between successive states to enable the method to converge to a reasonably optimal result.