Embodiments of a system method and computer program product for selecting an advertisement and presenting it to a user are described. Products and services offered by various merchants are read using a merchant specific catalog and stored in a common format. Categories for such products and services are normalized and virtual categories are created using various product attributes. Visual creatives, termed as ad-templates are created to control the visual and interactive aspects of the ad, including ad-size, color, as well as product attributes that are displayed in the ad. Ad-templates may be constrained to specific products or product categories. A learning algorithm uses an adaptive sampling process to sample various products, product categories and ad-templates independently for different learning units such as individual users, groups of users determined by some demographics, individual web pages and groups of web pages grouped using various similarity criteria. The performance of the ad is measured using various learning statistics, such as the click-through-rate, conversion rate, etc. The learning algorithm uses the learning statistics to optimize the return for the advertiser by favoring the products or categories that perform better on one or more specified criteria.