Is Reinforcement Learning the right choice for painting like Bob Ross? My workplace is having a 2-week code challenge that involves producing an algorithm to reproduce 100 sample Bob Ross paintings as closely as possible given some constraints:


*

*"Paintings" are submitted as a JSON file containing a background color and a series of "brush strokes".

*Brush strokes have a start point, end point, radius, and color.

*There is a 500 stroke limit per painting.

*All 100 reference paintings have the exact same size and aspect ratio: 450x337.



The server "paints" each submission and then does a per-pixel diff with the reference painting. Each pixel in the submitted painting is scored on a scalar 0-1 range based on how similar it is to the value of the source pixel and the score for the painting is an average of all of the pixel scores. The folks running the competition have released libraries for both painting and scoring images that can be run on the command line in MacOS / Linux.
I feel like this problem should be amenable to ML since we have a mechanism for fine-grained scoring of each attempt that the algorithm tries. Generating and scoring a painting only takes about 200ms. Unfortunately, I'm mostly just an ML fanboy (I listen to a lot of podcasts) and don't know how I should model the problem. 
Letting the algorithm make 500 completely random strokes and then grading the output would take forever to converge on something useful. I thought about limiting the color space of the strokes to a set of the 64 most frequent colors in each painting (by running a histogram before I start painting) and also limiting the algorithm's brush size selection.
For the record, simply submitting a image that is a solid field of the most common color earned me a 65% score. The currently winning algorithms are mostly just converting the paintings into grids and putting a dot of the average color in each sector on top of each one.
 A: I would suggest genetic algorithms (GA) or other global optimisers for this search, as your sequential score as you "build" the painting into more complex states is probably not the best guide.
There are a few examples of similar puzzles, such as building Mona Lisa out of circles, and here is a more recent example of the same problem, with code examples.
A GA approach would basically consist of a population of 100s of randomly generated sets of strokes, which you score and assess the best options. Then you select from the population, favouring solutions with the best score (there are lots of options for that, such as only picking from the top fraction, to using a skewed distribution that favours the top). Create pairs of solutions and "breed" them by taking some parts from the first and some from the second parent. Add just a little random noise as a "mutation". When you have done that enough to create a second generation, repeat the whole process. There are lots of variations.
RL should also work, but you may have an uphill task to create a policy or value function that can learn the mapping from stroke actions and the current state to the eventual policy or value. It's definitely feasible from a theoretical standpoint though. The state is the current image. The action is a choice of next stroke. The reward is the improvement in score, and should probably be assessed on each action (but could be done every 10, every 50, or even just at the end - longer delays will challenge the RL more, but might allow faster iteration). Most RL algorithms, such as Q-learning, should be able to cope with avoiding "dead end" results where early good scores are false leads, and need to be revised.
I don't know, but would be very interested to see, whether a GA or RL solves this problem more efficiently . . . my gut feeling is GA would be the way to go.
A: I think your skepticism of RL for this task is well-founded. But there has been some research toward building neural networks to reproduce the style of painters. This work leverages the power of convolutional neural networks.
"A Neural Algorithm of Artistic Style"
Leon A. Gatys, Alexander S. Ecker, Matthias Bethge

In fine art, especially painting, humans have mastered the skill to create unique visual experiences through composing a complex interplay between the content and style of an image. Thus far the algorithmic basis of this process is unknown and there exists no artificial system with similar capabilities. However, in other key areas of visual perception such as object and face recognition near-human performance was recently demonstrated by a class of biologically inspired vision models called Deep Neural Networks.1, 2 Here we introduce an artificial system based on a Deep Neural Network that creates artistic images of high perceptual quality. The system uses neural representations to separate and recombine content and style of arbitrary images, providing a neural algorithm for the creation of artistic images. Moreover, in light of the striking similarities between performance-optimised artificial neural networks and biological vision,3–7 our work offers a path forward to an algorithmic understanding of how humans create and perceive artistic imagery.

